Java8 中的 HashMap

2016-11-07 13:56:51   最后更新: 2018-06-12 17:10:21   访问数量:653




在此前的日志中,我们介绍了 java1.8 版本以前的 hashmap 源码及工作原理:

java HashMap 源码解析

java8 对 HashMap 结构和算法都进行了很大的优化,本节我们就来探究一下 java8 做了哪些改动,又带来了哪些提升

 

打开 HashMap 的源码,最直观的变化是多了很多成员,此前用来存储元素数据的 Entry 内部类不见了,由一个同样继承自 Map.Entry<K,V> 接口的 Node 内部类取代,而二者几乎没有任何区别,但是从名字上看,似乎新版本的 HashMap 和树结构有了什么关系

与此前一样,根据 Node 的 next 成员,让相同 hash 值的元素在哈希表中组成链表,这也就是解决冲突的链地址法

 

果然,接下来我们就看到了 TreeNode 内部类,新版本 HashMap 最大的优化就是在冲突链表的长度达到 8 以后自动转换为红黑树

 

除此以外,有五个成员是最重要的:

  1. threshold -- HashMap 所能容纳的最大 k-v 对数
  2. length -- Node[] 的长度,默认为 16
  3. loadFactor -- 负载因子,默认值为 0.75,threshold = loadFactor * length,一旦达到 threshold,HashMap 就会执行 resize 进行扩容
  4. modCount -- 记录 HashMap 内部结构发生的变化次数,用于迭代的快速失败
  5. size -- 当前实际存储的 k-v 对数

 

可以证明,length 大小为素数碰撞概率会低于 length 设为合数的情况,但出于取模、扩容时的效率考虑,HashMap 选择了将 length 设为 2 的 n 次方

 

下面我们来看下 put 方法的执行流程,这是 HashMap 最重要的操作之一,也是 java8 重要改动的一个地方

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

 

 

 

可以看到,蓝色底色的流程就是新增的红黑树的创建和更新操作,当链表长度达到 TREEIFY_THRESHOLD 时,默认 TREEIFY_THRESHOLD 值为 8,HashMap 就会将链表结构转换为红黑树结构

众所周知,虽然哈希表的平均查询时间复杂度是常数级的,但在不均匀的情况下,哈希表的查询时间复杂度就会显著上升,而红黑树则并不会受到这一限制,这就是 java8 对 HashMap 做的最大的优化

 

扩容是 HashMap 最常见的操作之一,当 HashMap 中不断地加入新元素,很快 Table 无法容纳更多元素时,就需要扩大 Table 的长度来容纳更多元素

java 中的数组是不能自动扩容的,只能够通过创建新的更大容量的数组,同时进行数据的移动才可以实现扩容功能

 

JDK1.7 中的 resize -- void resize(int newCapacity)

在 java1.7 中,扩容机制非常简单:

void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }

 

 

  1. 首先,判断容量是否已经达到最大阈值不能再次扩容
  2. 调用 initHashSeedAsNeeded 方法创建新的数组
  3. 调用 transfer 方法将原哈希表中元素放入新的数组
  4. 更新 table、threshold 成员

 

这个流程最重要的就是 transfer 方法了:

void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }

 

这一过程遍历并重新计算了每个 key 的 hash 值,放入新的 table 中,由于 newTable[i] = e; e = next; 两步操作,将导致如果元素 A 和元素 B 在原 table 中 hash 值相同,并且处于 A->B 的位置,如果他们在新的 table 中 hash 值同样相同,将会变成 B->A 的位置,也就是发生了倒置

 

并发环境下使用 HashMap 造成的成环问题

需要注意的是,在并发环境下执行时,如果线程1执行前,线程2已经完成了上述 transfer 的过程,那就有可能造成成环的问题

具体过程如下:

  • 初始状态

 

 

  • 并发写入扩容前状态

此时,线程1执行 put(3, "A"),线程2执行 put(7, "B"),假设 3、7、5 的哈希值相同,那么扩容前状态如下:

 

 

  • 扩容后状态

 

 

  • 并发环境下扩容引起成环

假设线程1执行 transfer 方法的 Entry<K,V> next = e.next; 后,线程2完成了 transfer 的执行,那么 HashMap 的结构如下图所示

 

此时线程1执行 transfer 方法的 e.next = newTable[i];

HashMap 成环

 

JDK1.8 中的 resize -- final Node<K,V>[] resize()

JDK1.8 中,resize 操作不再能够指定 resize 后的大小,而是每次扩容固定为原大小的 2 倍,由于 n 变为了原来的 2 倍,元素在重新计算 hash 后,被用于计算的 mask 范围多了高位的 1 位,因此元素可能进入的桶只有两种可能:原位置或原位置+oldCap

 

这样就巧妙地避免了 hash 值的反复计算,同时,这一流程也巧妙避免了上文提到的 JDK1.7 中存在的倒置问题

 

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧 table 长度 int oldThr = threshold; // 旧的 table 容量 int newCap, newThr = 0; if (oldCap > 0) { // 超过最大阈值则不再扩容 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 如果不超过阈值,新的 table 长度及容量变为原有的 2 倍 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); } // 计算新的resize上限 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]; table = newTab; if (oldTab != null) { // 遍历原 table,将所有元素移动到新 table 中 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order 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; } // 新元素位于原位置 + oldCap 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; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

 

 

Hash 均匀的情况

首先我们使用系统时间作为元素 hash 值,来保证 hash 的相对均匀,getKey 的平均时间统计如下:

 

通过观测测试结果可知,JDK1.8的性能要高于JDK1.7 15%以上,在某些size的区域上,甚至高于100%。由于Hash算法较均匀,JDK1.8引入的红黑树效果不明显

 

Hash 不均匀的情况

我们让所有元素的 hash 函数都返回 1,来让 hash 极不均匀,getKey 的平均时间统计如下:

 

从表中结果中可知,随着size的变大,JDK1.7的花费时间是增长的趋势,而JDK1.8是明显的降低趋势,并且呈现对数增长稳定。当一个链表太长的时候,HashMap会动态的将它替换成一个红黑树,这话的话会将时间复杂度从O(n)降为O(logn)。hash算法均匀和不均匀所花费的时间明显也不相同,这两种情况的相对比较,可以说明一个好的hash算法的重要性。

 

JDK1.7 与 JDK1.8 源码

Java 8系列之重新认识HashMap -- http://tech.meituan.com/java-hashmap.html

 






技术帖      技术分享      源码      java      jdk      map      hashmap     


京ICP备15018585号