HashMap容量和负载因子使用说明
更新:HHH   时间:2023-1-7


HashMap底层数据结构是数组+链表,JDK1.8中还引入了红黑树,当链表长度超过8个时,会将链表转成红黑树,以提升其查找性能。

那么,给出一个<key, value>节点,HashMap是如何确定这个节点应该放在具体哪个位置呢?(以JDK1.8为例)

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  // HashMap没有被初始化,则先进行初始化
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  // 节点所在index = (n - 1) & hash,该位置没有数据,则直接将新节点放在数组的index位置上
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  else { // index上已经有节点了
    Node<K,V> e; K k;
    // 如果新key与原来的key一样,则e指向原节点p(后面会用新value替换e所指向的value)
    if (p.hash == hash &&
      ((k = p.key) == key || (key != null && key.equals(k)))) 
      e = p;
    // 如果该节点是树节点,则采用树的插入算法,插入新节点
    else if (p instanceof HashMap.TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else { // 该节点是链表节点
      for (int binCount = 0; ; ++binCount) {
        // 将新节点插入到index所在链表的末端
        if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          // 链表节点超过8个,则进行链表转树处理
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        // 同样的,如果key已经存在的话,则不进行插入操作,而是后面进行value替换
        if (e.hash == hash &&
          ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    // e != null的情况,就是key已经存在了,这里统一进行了新值value,替换旧值e.value的操作
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  // 插入后数组size 大于阈值的话,需要进行扩容
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

看源码,节点落在数组中的index = (数组长度 - 1) & key的hashcode,如果该index上没有数据,则直接插到该index上,如果节点已经有数据了,则把新节点插入该index对应的链表中(如果链表节点大于8个,会进行链表转树,之后的插入算法就变成了树的插入算法)。

每次put之后,会检测一下是否需要扩容,size超过了 总容量 * 负载因子,则会扩容。默认情况下,16 * 0.75 = 12个。

1、为什么初始容量是16

当容量为2的幂时,上述n -1 对应的二进制数全为1,这样才能保证它和key的hashcode做&运算后,能够均匀分布,这样才能减少hash碰撞的次数。至于默认值为什么是16,而不是2 、4、8,或者32、64、1024等,我想应该就是个折中处理,过小会导致放不下几个元素,就要进行扩容了,而扩容是一个很消耗性能的操作。取值过大的话,无疑会浪费更多的内存空间。因此在日常开发中,如果可以预估HashMap会存入节点的数量,则应该在初始化时,指定其容量。

2、为什么负载因子是0.75

也是一个综合考虑,如果设置过小,HashMap每put少量的数据,都要进行一次扩容,而扩容操作会消耗大量的性能。如果设置过大的话,如果设成1,容量还是16,假设现在数组上已经占用的15个,再要put数据进来,计算数组index时,发生hash碰撞的概率将达到15/16,这违背的HashMap减少hash碰撞的原则。

补充知识:HashMap只有容量达到阀值才发生扩容吗?大错特错!

看了网上很多文章,说HashMap在元素达到负载因子对应数的时候就发生扩容。如果你看过源码就会发现,其实还有一种情况也可能会发生扩容:树形化的时候。

对象最终是如何放入HashMap中的?

HashMap底层是由数组+链表组成的,为了方便不懂的人更容易理解,那我们就先假设HashMap底层就是数组,先不管链表。

当一个对象add到HashMap中,此时HashMap的add方法是如何来确定这个对象是放在数组中的哪个位置的呢?

拿JDK1.8来说(其他JDK版本稍有不同,但大同小异),大家应该知道每一个对象天生都继承了或程序员自己覆盖了Object类的 hashCode()方法,此方法返回对象的hashcode值。

HashMap会有一个方法,先拿到要add进HashMap中的对象的hashCode,再将这个hashCode异或上对象自身hashCode右移16位(是不是感觉说的不是人话?这个步骤叫扰乱,这样做的目的是为了让hashCode每一位都尽可能用到,如果不理解没关系并不影响接下来的阅读),hashCode经过上述步骤之后再&(数组长度-1),计算的结果就是这个对象在数组中的位置了。我自己都觉得说的不是人话,下面举个例子,便于理解:

这里有一个Student对象的hashCode是:a

先把这个a右移16位 , b=a>>>16;

然后a=a&b;

数组中的位置等于: a&(数组长度-1);

上述源码如下:

h=key.hashCode();

h = key.hashCode()) ^ (h >>> 16)

数组位置=h&(数组长度-1);

好了, 我们已经知道元素是如何在hashMap中的数组上如何定位了,现在假设一个极端情况(不可能发生,但是我用这个举例子):

假设数组长度为1,根据源码:

数组位置=h&(数组长度-1)

那么有:

数组位置=h&(1-1)=0 ,无论什么对象,都定位到数组的第0个位置。

这个很好理解吧。无论元素是否一样,由于数组长度为1,所以元素通通定位到数组中第0个位置。大家都知道一个数组只能放一个元素啊?那怎么办呢?我们用链表来解决这个问题,把定位到这个位置的元素通过链表连接。这就是我一开始说的:hashMap是数组+链表。

那树形化又是什么东东呢?

想一下我们为什么要用HashMap,是因为通过Hash算法在理想情况下时间复杂度O(1)就能找到元素,特别快,但是我都说了是理想情况,如果遇到上述发生hash碰撞(谁jb取的名字,就是上面我才说的,两个元素定位到数组中同一个位置),且hash碰撞比较频繁的话,那么当我们get一个元素的时候,定位到了这个数组,还需要在数组中遍历一次链表最终才能找到要get的元素,是不是已经失去一部分使用HashMap的初心了?(因为需要遍历链表,所以时间复杂度就比之前高了)

所以JDK1.8使用红黑树这种数据结构来解决链表过长的问题(可以简单理解为用红黑树遍历比链表遍历速度快,时间复杂度低,不懂红黑树的可以去搜搜看),默认链表长度达到8就将链表树形化(变为红黑树)。

回到最最开始我提到的,那为什么树形化的时候可能会发生扩容呢?

想想刚刚的例子数组长度为1,所有元素全部在数组的第0个位置形成一条链表,这例子是一种极端情况,数组长度过小,那自然就会经常发生hash碰撞,那形成长链表是肯定的,这个时候树形化其实是治标不治本,因为引起链表过长的根本原因是数组过短,所以在JDK1.8源码中,执行树形化之前,会先检查数组长度,如果长度小于64,则对数组进行扩容,而不是进行树形化。

所以发生扩容的时候有两种情况,一种是元素达到阀值了,一种是HashMap准备树形化但又发现数组太短,这两种情况均可能发生扩容。

以上这篇HashMap容量和负载因子使用说明就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持天达云。

返回开发技术教程...