知识点:Java HashMap 原理与源码分析(下)

本文可以让你学到:

1.HashMap resize原理     重要知识点
2.HashMap 特性总结

回顾

上篇中讲了HashMap的特点、常用方法、工作原理以及hash值是怎样计算的;
上篇《知识点: Java HashMap 原理与源码分析(上)》

数据结构

知识点:Java HashMap 原理与源码分析(下)

HashMap索引使用数组结构进行管理(图中的table字段),数组的类型为Node<K,V>[];Node是interface;Node实际有两个类型,分别为链表与红黑树;
Node中存储key、value、hash以及指向下一个元素的next。
Node定义如下:

static class Node<K,V> implements Map.Entry<K,V> {         final int hash;         final K key;         V value;         Node<K,V> next; } 

关键常量参数

  1. DEFAULT_INITIAL_CAPACITY 初始化时默认容量;大小为1<<4(16)
  2. MAXIMUM_CAPACITY 最大容量;大小为1<<30
  3. DEFAULT_LOAD_FACTOR 默认填充系数 大小为0.75

resize() 分析

什么情况下需要resize()操作
  1. 初始化时指定容量为0
  2. 容量超过临界点时

扩容流程如下图:

知识点:Java HashMap 原理与源码分析(下)
final Node<K,V>[] resize() {         Node<K,V>[] oldTab = table;         int oldCap = (oldTab == null) ? 0 : oldTab.length;         int oldThr = threshold;         int newCap, newThr = 0;         //判断当前容量大小         if (oldCap > 0) {             //是否已经超过最大容量;超过则不扩容;但临界值修改为Integer.MAX_VALUE             if (oldCap >= MAXIMUM_CAPACITY) {                 threshold = Integer.MAX_VALUE;                 return oldTab;             }             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                      oldCap >= DEFAULT_INITIAL_CAPACITY)                      //进行两倍的扩容                 newThr = oldThr << 1; // double threshold         }         // 老的临界点大于0 扩容到老的临界点         else if (oldThr > 0) // initial capacity was placed in threshold             newCap = oldThr;         else {               // zero initial threshold signifies using defaults         //老的容量为0临界值也为0时扩容至默认容量             newCap = DEFAULT_INITIAL_CAPACITY;             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);         }         //新临界值为0时,通过新的容量*填充系数获得新的临界值         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];         //将新的tab赋值给老的table         table = newTab;         //老的table中有数据是对老的数据进行分裂         if (oldTab != null) {             //循环老的table,将老的数据通过hash值重新在新的table中找出索引位置             for (int j = 0; j < oldCap; ++j) {                 Node<K,V> e;                 if ((e = oldTab[j]) != null) {                     oldTab[j] = null;                     //e.next==null 表中结点上只有一个对象;没有hash冲突的情况                     if (e.next == null)                         newTab[e.hash & (newCap - 1)] = e;                     else if (e instanceof TreeNode)                     //老的节点为红黑树时重新分裂到新的table上;分裂的方式和链接基本相同                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);                     else { // preserve order                     //将链表中的元素重新分配到新的table中                         Node<K,V> loHead = null, loTail = null;//元素hash中在原table长度的二进制高位为0                         Node<K,V> hiHead = null, hiTail = null;//元素hash中在原table长度的二进制高位为1                         Node<K,V> next;                         do {                         //遍历链表中的所有元素,通过老table长度的高位对链表拆分                             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);                         //将高位为0的放到新table中,索引和原来相同                         if (loTail != null) {                             loTail.next = null;                             newTab[j] = loHead;                         }                         //将高位为1的放到新table中,索引为j+oldCap;                         if (hiTail != null) {                             hiTail.next = null;                             newTab[j + oldCap] = hiHead;                         }                     }                 }             }         }         return newTab;     } 

扩容时使用二次幂进行;每次将当前table容量大小size向右移位;比如16、32、64、128;这样在进行扩容时也可以使用二分法减少数据的移动;
例1:
当前容量大小为16,现进行扩容;一次扩容后的容量大小为32
如有一个对象的hash值二进制为:
e.hash的二进制值
1111 1010 0000 1111 0000 1111 1100 1111
table.size的二进制值
0000 0000 0000 0000 0000 0000 0001 0000
这时e对象的索引就会保持在原来的位置上

例2:
当前容量大小为16,现进行扩容;一次扩容后的容量大小为32
如有一个对象的hash值二进制为:
e.hash的二进制值
1111 1010 0000 1111 0000 1111 1101 1111
table.size的二进制值
0000 0000 0000 0000 0000 0000 0001 0000
这时e对象的索引将会是原来的索引加上原tabal.size,结果为newIndex=j+oldCap

总结

1.使用数组存储结点Node,最大容量为1的30次幂1<<30
2.中的结点Node有链表与红黑树两种类型(Java 1.8后加入链表)
3.每次扩容后的容量均为2的次幂
4.是线程不安全的集合类
5.有最大索引值1<<30;但理论上可以存储无限数量的对象
6.计算hash值会调用对象的hashCode()方法
7.查找值时会调用对象的equal()方法
8.允许存在空的key与value值
9.元素是无序的,且会随容量的变化而变化
10.遍历整个 Map 需要的时间与 桶(数组) 的长度成正比,因此初始化时桶的容量不宜过大

公众号阅读 码农杰森

知识点:Java HashMap 原理与源码分析(下)
版权声明:玥玥 发表于 2021-04-25 9:51:55。
转载请注明:知识点:Java HashMap 原理与源码分析(下) | 女黑客导航