JDK8中的HashMap

/ 算法和数据结构 / 2 条评论 / 815人围观

前言

来年第一篇,认真研究一下HashMap。

PUT方法

首先跟着源码大致走一遍

        // 在jdk1.8中,HashMap刚初始化还未put值的时候,容量是0,只有在put值的时候,且未指定初始化
	// 容量的时候,才会进行resize调整大小,默认是16
	final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 这儿就是初始化容量16
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 找到具体的数组下标,如果此位置没有值,那么直接初始化一下Node并放置在这个位置就可以了
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else { // 该数组下标位置有值
            Node<K,V> e; K k;
            // 1. 判断该位置的第一个数据和我们要插入的数据,key 是不是相等,并取出这个节点
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 2. 如果该节点是代表红黑树的节点(TreeNode),调用红黑树的插值方法
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 3. 以上两者都不是,那这个地方挂了一个链表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        // 插入到链表的最后面,1.8之前应该是插入到链表头部(bucketIndex)
                        p.next = newNode(hash, key, value, null);
                        // 如果新插入的值是链表中的第8个会触发下面的treeifyBin方法
                        // 也就是将链表转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果在该链表中找到了"相等"的 key(== 或 equals)
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // existing mapping for key说明有相同的key
            // 覆盖旧的值,并且返回旧值
            if (e != null) { 
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 如果因为插入新值,导致超过了阈值,就会进行resize,也就是扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

以上源码可以整理成一张图,如下:

请输入图片描述 put的过程文字描述如下:

①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;

②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;

④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

通过分析put源码,我们知道了:

GET方法

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判断第一个节点是不是就是需要的
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 判断是否是红黑树
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 链表遍历
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

get方法大致分析:

  1. 计算 key 的 hash 值,根据 hash 值找到对应数组下标: hash & (length-1)
  2. 判断数组该位置处的元素是否刚好就是我们要找的,如果不是,走第三步
  3. 判断该元素类型是否是 TreeNode,如果是,用红黑树的方法取数据,如果不是,走第四步
  4. 遍历链表,直到找到相等(==或equals)的 key

扩容操作

        // 数组的扩容操作
	final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // capacity * load factor也就是容量*负载因子
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) { // 开始扩容
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 原始容量向右位移一位后还小于最大容量,且原始容量大于默认的16
            // 就将阈值扩大一倍,比如说原阈值为16*0.75=12变为24,也就是32*0.75
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        // 用新的数组大小初始化新的数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        // 如果是初始化数组,到这里就结束了,返回 newTab 即可
        table = newTab;
        // 到这里,对原数组的数据进行迁移
        if (oldTab != null) {
            // 开始遍历原数组,进行数据迁移
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    // 释放原有数据
                    oldTab[j] = null;
                    // 1. 如果该数组位置上只有单个元素,简单迁移这个元素就可以了
                    if (e.next == null)
                        // 重新计算确定新数组元素下标,并将原值赋上去
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // 2. 如果是红黑树,后续再仔细研究
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { 
                        // 3. 这里就是处理链表了
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            // 第一条链表
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            // 第二条链表的新的位置是 j + oldCap
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

问题汇总

  1. 为什么扩容大小都是2的几次幂?

这就跟如何快速且均匀的确定下标位置有关系了,在1.8中,如下:

  1. 何时需要扩容?

HashMap的size大于等于(容量*加载因子)的时候,会触发扩容的操作,这个是个代价不小的操作。

  1. 如何进行扩容,如何进行数据的迁移?
  void resize(int newCapacity) {   //传入新的容量
      Entry[] oldTable = table;    // 引用扩容前的Entry数组
      int oldCapacity = oldTable.length;         
      // 扩容前的数组大小如果已经达到最大(2^30)了
      if (oldCapacity == MAXIMUM_CAPACITY) {  
          // 修改阈值为int的最大值(2^31-1)这样以后就不会扩容了
          threshold = Integer.MAX_VALUE; 
          return;
      }
      // 初始化一个新的Entry数组
     Entry[] newTable = new Entry[newCapacity];  
     // 将数据转移到新的Entry数组里
     transfer(newTable);   
     // HashMap的table属性引用新的Entry数组                      
     table = newTable; 
     // 修改阈值                          
     threshold = (int)(newCapacity * loadFactor);
 }

transfer方法是对元素的拷贝操作:

  void transfer(Entry[] newTable) {
      Entry[] src = table;                   //src引用了旧的Entry数组
      int newCapacity = newTable.length;
      for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
          Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
          if (e != null) {
              src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
              do {
                  Entry<K,V> next = e.next;
                 int i = indexFor(e.hash, newCapacity); // 重新计算每个元素在数组中的位置
                 e.next = newTable[i]; //标记[1]
                 newTable[i] = e;      //将元素放在数组上
                 e = next;             //访问下一个Entry链上的元素
             } while (e != null);
         }
     }
 }

newTable[i]的引用赋给了e.next,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置(1.8是直接放到了链表尾部);这样首先放在索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话),这一点和Jdk1.8有区别,下文详解。在旧数组中同一条Entry链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上。

假设了我们的hash算法就是简单的用key模一下表的大小(取余)。其中的哈希桶数组table的size=2, 所以key = 3、7、5,put顺序依次为 5、7、3。在mod 2以后都冲突在table1这里了。这里假设负载因子 loadFactor=1,即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4,然后所有的Node重新rehash的过程。 请输入图片描述

经过观测可以发现,我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思,n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。 请输入图片描述 元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化: 请输入图片描述 因此,我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为16扩充为32的resize示意图: 请输入图片描述 这个设计非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别,JDK1.7中rehash的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8不会倒置。

  1. 为什么链表长度达到8个会转换成红黑树?

理想情况下使用随机的哈希码,容器中节点分布在hash桶中的频率遵循泊松分布(具体可以查看维基百科,泊松分布),按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表,可以看到链表中元素个数为8时的概率已经非常小,再多的就更少了,所以原作者在选择链表元素个数时选择了8,是根据概率统计而选择的。

  1. 如果我指定初始化容量为19,那实际容量是多少?

实际是32

  1. 如何计算下标?

一般情况下是用key的hashcode模数组的长度length,但为了提高速度,并且提高数据的离散程度分成了两步,第一步是计算hash值,用的是key的hashcode异或hashcode无符号右移16位,表达式为key.hashCode()^(key.hashCode()>>>16),第二步是用第一步得到的hash值跟数组长度-1做与运算,这样得出来的结果跟直接用hashcode模length结果一样,但保证了速度的同时,离散程度也提高了。

  1. 什么是hash碰撞,如何解决它?

就是求出来的hash值一样,通常有两种方法,一种是开放地址法,第二种就是链式法(数组+链表的组合),也叫拉链法。HashMap就是采用的拉链法。

  1. HashMap为什么线程不安全?

  2. 关于负载因子threshold

通过调节负载因子,可使 HashMap 时间和空间复杂度上有不同的表现。当我们调低负载因子时,HashMap 所能容纳的键值对数量变少。扩容时,重新将键值对存储新的桶数组里,键的键之间产生的碰撞会下降,链表长度变短。此时,HashMap 的增删改查等操作的效率将会变高,这里是典型的拿空间换时间。相反,如果增加负载因子(负载因子可以大于1),HashMap 所能容纳的键值对数量变多,空间利用率高,但碰撞率也高。这意味着链表长度变长,效率也随之降低,这种情况是拿时间换空间。

  1. 关于变量table被transient修饰的原因

阅读 HashMap 的源码,会发现桶数组 table 被声明为 transient。transient 表示易变的意思,在 Java 中,被该关键字修饰的变量不会被默认的序列化机制序列化。我们再回到源码中,考虑一个问题:桶数组 table 是 HashMap 底层重要的数据结构,不序列化的话,别人还怎么还原呢?其实 HashMap 并没有使用默认的序列化机制,而是通过实现readObject/writeObject两个方法自定义了序列化的内容。我们知道 HashMap 中存储的是键值对,其它都属于辅助属性。所以只要我们把键值对序列化了,我们就可以根据键值对数据重建 HashMap。又有疑问,那么序列化 table 不是可以一步到位,后面直接还原不就行了吗?这样一想,倒也是合理。但序列化 talbe 存在着两个问题:

以上两个问题中,第一个问题比较好理解,第二个问题解释一下。HashMap 的get/put/remove等方法第一步就是根据 hash 找到键所在的桶位置,但如果键没有覆写 hashCode 方法,计算 hash 时最终调用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的,不同的 JVM 下,可能会有不同的实现,产生的 hash 可能也是不一样的。也就是说同一个键在不同平台下可能会产生不同的 hash,此时再对在同一个 table 继续操作,就会出现问题。综上所述,就是 HashMap 不序列化 table 的原因了。

文章参考:https://tech.meituan.com/

  1. 学习了,大佬

    回复
  2. 123123

    回复