爱站程序员基地本文可以让你学到：
1.HashMap resize原理 重要知识点
2.HashMap 特性总结
回顾
上篇中讲了HashMap的特点、常用方法、工作原理以及hash值是怎样计算的；
上篇《知识点： 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;}
关键常量参数
-
DEFAULT_INITIAL_CAPACITY
初始化时默认容量；大小为
1<<4
（16）
-
MAXIMUM_CAPACITY
最大容量；大小为
1<<30
-
DEFAULT_LOAD_FACTOR
默认填充系数 大小为0.75
resize() 分析
什么情况下需要resize()操作
- 初始化时指定容量为0
- 容量超过临界点时
扩容流程如下图：
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_VALUEif (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 thresholdnewCap = 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赋值给老的tabletable = 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长度的二进制高位为0Node<K,V> hiHead = null, hiTail = null;//元素hash中在原table长度的二进制高位为1Node<K,V> next;do {//遍历链表中的所有元素，通过老table长度的高位对链表拆分next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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<<302.中的结点
Node有链表与红黑树两种类型（Java 1.8后加入链表）
3.每次扩容后的容量均为2的次幂
4.是线程不安全的集合类
5.有最大索引值1<<30；但理论上可以存储无限数量的对象
6.计算hash值会调用对象的hashCode()方法
7.查找值时会调用对象的equal()方法
8.允许存在空的key与value值
9.元素是无序的，且会随容量的变化而变化
10.遍历整个 Map 需要的时间与 桶(数组) 的长度成正比，因此初始化时桶的容量不宜过大
公众号阅读 码农杰森
