HashMap实现原理分析及实现

一.hashMap实现原理分析

  1. HashMap底层实现方式：散列链表，即数组+链表
  2. hash表：也叫散列表,是通过关键码值(key-value)而直接进行访问的数据结构 。
  • 原理： 通过把关键码值映射到表中一个位置来访问记录
  • 好处：这种数据结构可以加快查找的速度。

这里就需要将几种数据结构的优缺点进行比较了。

  • 数组
    优点：查询快，随机访问快
    缺点：插入，删除慢

  • 链表
    优点：插入，删除慢
    缺点：随机访问慢

  • hash表：通过索引的方式使得查询的时候提高查询的效率
    优点：插入快，删除快，查找快
    缺点：基于数组的，数组创建后难于拓展，当hash表被基本填满后，性能下降非常严重。因此在使用hash表的时候需要提前预估表中要存多少个数据，避免扩展。

    /**
 * hashMap是将key-value看成一个数据实体entry来存储的，而且每个实体的索引值只与key有关，与value无关
 */
public class HashMap<K, V> {
  //hashMap长度
  private int size;
  //数组最小长度
  private static final int MINIMUM_CAPACITY = 4;
  //数组最大长度
  private static final int MAXIMUM_CAPACITY = 1 << 30;

  //空表的数组长度为2，意味着一建立就要强制扩容，这个是自己指定的
   private static final Map.Entry[] EMPTY_TABLE = new HashMapEntry[MINIMUM_CAPACITY >> 1];
  //装填因子，即数组扩容的阈值
    private int threshold;

    private HashMapEntry<K, V>[] table;//核心数组
    //在hashmap中允许key为空，而且只能有一个，并且单独存储，没有存储在核心数组里面
    private HashMapEntry<K, V> entryForNullKey;

    @SuppressWarnings("unchecked")
    public HashMap() {//空参构造函数
        table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
        threshold = -1;
    }

  @SuppressWarnings("unchecked")
  public HashMap(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException();
        }
        if (capacity == 0) {
          table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
        threshold = -1;
            return;
      }
  //如果传进来的数组参数比最小数组长度还小，那数组长度就为最小长度
      if (capacity < MINIMUM_CAPACITY) {
            capacity = MINIMUM_CAPACITY;
      } else if (capacity > MAXIMUM_CAPACITY) {
            capacity = MAXIMUM_CAPACITY;
      } else {
          capacity = roundUp2PowerOf2(capacity);
      }
      makeTable(capacity);
  }

  /**
   * 插入一个元素
   * @param key
   * @param value
   * @return
   */
    public V put(K key, V value) {
          if (key == null) {
              return putValueForNullKey(value);
          } else {
          /**
           * 如果键值对不为空，则先要找到key-value的位置
           * 1.先生成key的hash值
           * 2.根据hash值找到数组的角标
           * 3.根据角标插入对应的位置
           */
          //键的hash值
          int hash = secondaryHash(key.hashCode());
          HashMapEntry<K, V>[] tab = table;
          /**
           * 得到数组的角标
           * &运算的作用：0~min(a,b),可以取到最小值的最大值
           */
            int index = hash & (tab.length - 1);
          //如果存在指定的元素则覆盖，不存在则插入
          //对羊肉串进行遍历
          for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
          /**
           * key与hash值之间的关系
           * key相同，hash值一定相同；反之，hash值相同，key不一定相同
           */
          if (e.hash == hash && key.equals(e.key)) {
              //同一个元素，则覆盖
              V oldValue = e.getValue();
              e.setValue(value);
              return oldValue;
          }
      }
      //没有覆盖，直接插入元素,但不一定是在数组中增加一个元素，可能是在某个羊肉串后面添加一个节点
      /**
       * @see makeTable(int capacity)
       * @link{makeTable(int capacity) }
       * 虽然阈值定义的是capacity的3/4，但是capacity是个正数，所以threshold一个整数
       */
      if (size++ > threshold) {
          //假如一个元素插入成功，但是超过了阈值，就需要扩容
          /**
           * 1.创建一个新的容量的数组
           */
          tab = doubleCapacity();
          index = hash & (tab.length - 1);
        }
        addNewEntry(key, value, hash, index);
    }
    return value;
}

public V get(Object key){
  if (key == null) {
      HashMapEntry<K,V> e=entryForNullKey;
      return e==null?null:e.getValue();
  }else {
      int hash=secondaryHash(key.hashCode());
      HashMapEntry<K,V>[] tab=table;
      int index=hash&(tab.length-1);
      for (HashMapEntry<K,V> e=tab[index];e!=null;e=e.next){
            K eKey = e.key;
            if (eKey==key||(e.hash==hash&&key.equals(eKey))) {
                return e.value;
            }
        }
        return null;
    }
}

/**
 * 将key-value键值对添加到index的位置
 * @param key
 * @param value
 * @param hash
 * @param index
 */
  private void addNewEntry(K key, V value, int hash, int index) {
  //添加到队头的位置
  table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
  }

/**
 * 双倍扩容
 * @return
 */
@SuppressWarnings("unchecked")
private HashMapEntry<K, V>[] doubleCapacity() {
  HashMapEntry<K, V>[] oldTable = table;
  int oldCapacity = oldTable.length;
  if (oldCapacity == MAXIMUM_CAPACITY) {
      return oldTable;
  } else {
      int newCapacity = oldCapacity << 1;
      // TODO: 这里是否要判断newCapacity>MAXIMUM_CAPACITY?
      if (newCapacity >= MAXIMUM_CAPACITY) {
          newCapacity = MAXIMUM_CAPACITY;
      }
      //这里不能采用new的方式，因为这样就与旧的table产生不了联系
      HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
      /**
       * 双倍扩容时，表有可能是空表，即
       * @link{<code>EMPTY_TABLE</code>}， 此时数组长度为4，但是size为0
       */
      if (size == 0) {
          return newTable;
      }
      /**
       * 双倍扩容之后，需要重新散列
       */
      for (int j = 0; j < oldTable.length; j++) {
          //拿到每个羊肉串
          HashMapEntry<K, V> e = oldTable[j];
          if (e == null) {
              continue;
          }
          /**
           * e.hash & oldCapacity <===> e.hash & oldTable.length===>结果的范围：[0,oldTable.length]
           * 对比：
           * int index = hash & (tab.length - 1)===>结果的范围：[0,oldTable.length-1]
           * “|”的作用：2*max（a，b）> a|b >max(a,b)
           */
          int highBit = e.hash & oldCapacity;//0-oldTable.length
          //断链标志位
          HashMapEntry<K, V> broken = null;
          newTable[j | highBit] = e;//重新散列成功oldTable.length-2*oldTable.length-1
          /**
           * e=n： 每次指针后移的时候，都保留当前结点的前一个元素
           **/
          for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
              int nextHighBit = n.hash & oldCapacity;
              if (nextHighBit != highBit) {
                  if (broken == null) {
                      int nextNewIndex = j | nextHighBit;//新的索引
                      newTable[nextNewIndex] = n;
                  } else {
                      broken.next = n;
                  }
                  broken = e;
                  highBit = nextHighBit;
              }
              if (broken != null) {
                  broken.next = null;
              }
          }
      }
      return newTable;
   }
}

/**
 * hashMap 键的hash算法
 * 可以看到：对键进行单独的hash运算
 * @param h key的hash值
 * @return 算法的意义：目的就是为了将h打散，而且在0到max 之间均匀分布
 * 异或算法的作用：补位，多样化
 */
private int secondaryHash(int h) {
    //拿到高12位，      拿到高20位
    h ^= (h >>> 20) ^ (h >>> 12);
    //  拿到自己  拿到高25位， 拿到高28位
    return h ^ (h >>> 7) ^ (h >>> 4);
}

/**
 * 给放空key的键值对赋值
 * @param value
 * @return
 */
private V putValueForNullKey(V value) {
  HashMapEntry<K, V> newEntry = entryForNullKey;
  //如果空键的键值对不存在，则重新创建
  if (newEntry == null) {
      addEntryForNullKey(value);
      //虽然空键键值对单独存放，但是也是hashmap集合中的一个元素，所以要size++
      size++;
      return null;
  } else {
      V oldValue = newEntry.getValue();
      newEntry.setValue(value);
      return oldValue;
    }
}

/**
 * 创建空键键值对,hash值只与key有关，键为null的键值对单独存放，所以next为空
 * @param value
 */
private void addEntryForNullKey(V value) {
  entryForNullKey = new HashMapEntry<>(null, value, 0, null);
}

/**
 * 根据容量创建核心数组
 * @param capacity
 */
private HashMapEntry<K, V>[] makeTable(int capacity) {
//table=new HashMapEntry[capacity];//不要这么写
  HashMapEntry<K, V>[] newTable = new HashMapEntry[capacity];
  table = newTable;//尽量不要操作全局变量，把全局变量转成局部变量，通过操作局部变量达到操作全局变量的目的，防止bug
  threshold = (capacity >> 1) + (capacity >> 2);//3/4;
  return newTable;
}

/**
 * 将任意一个数转换成2的幂次方
 * 是2的幂次方的数的特点：
 * 2 =10=1+1
 * 4 =100=11+1
 * 8 =1000=111+1
 * 16=10000=1111+1
 * 32=100000=11111+1
 * <p>
 * @param i
 * @return
 */
private int roundUp2PowerOf2(int i) {
    i--;
    i = i >>> 1;
    i = i >>> 2;
    i = i >>> 4;
    i = i >>> 8;
    i = i >>> 16;
    return i;
}


/**
 * 1. 成员变量可以是任意数据类型，基本数据类型，引用数据类型，类就属于引用数据类型，
 * 因此内部类的另一种理解方式就是将其看成外部类的成员变量，
 * <code>成员变量</code>也是<code>全局变量</code>，是整个类中都要使用的变量
 * 成员变量表示一个类的属性，这个属性自然在这个类中都成立，自然全局可用
 * <p>
 * 2.hashMap是将key-value看成一个数据实体entry来存储的，而且每个实体的索引值只与key有关，与value无关
 * 因此在entry中需要一个构造函数将key和value封装成entry
 */
private static class HashMapEntry<K, V> implements Map.Entry<K, V> {
  //每个键值对的键是唯一的，一旦被赋值，就不能被修改了，通过final修饰来达到这个目的
  final K key;
  V value;
  final int hash;//hash是有key有关的hash算法生成的，因此也不能被被外界修改
  HashMapEntry<K, V> next;//指向下一个节点的指针

  public HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
      this.key = key;
      this.value = value;
      this.hash = hash;
      this.next = next;
  }

  @Override
  public K getKey() {
      return key;
  }

  @Override
  public V getValue() {
      return value;
  }

  @Override
  public V setValue(V value) {
      V oldValue = this.value;
      this.value = value;
      return oldValue;
  }

  /**
   * 任何一个对象都有hashcode方法，这个是从Object类继承过来的，hash算法是自己指定的
   * @return
   */
  @Override
  public int hashCode() {
      return (key == null ? 0 : key.hashCode()) ^ (value == null ? 0   : value.hashCode());
    }
  }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,491评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,856评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,745评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,196评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,073评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,112评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,531评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,215评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,485评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,578评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,356评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,215评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,583评论 3赞 299
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,898评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,174评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,497评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,697评论 2赞 335