面试题：说说HashMap的扩容过程？

  这是一道阿里的面试题&＃xff0c;考察你对HashMap源码的了解情况&＃xff0c;废话不多说&＃xff0c;咱们就直接上源码吧&＃xff01;

jdk 1.7 源码

void resize(int newCapacity) {Entry[] oldTable &＃61; table;//保存旧数组int oldCapacity &＃61; oldTable.length;if (oldCapacity &＃61;&＃61; MAXIMUM_CAPACITY) {//判断当前数组大小是否达到最大值threshold &＃61; Integer.MAX_VALUE;return;}Entry[] newTable &＃61; new Entry[newCapacity];//创建一个新数组boolean oldAltHashing &＃61; useAltHashing;useAltHashing |&＃61; sun.misc.VM.isBooted() &&(newCapacity >&＃61; Holder.ALTERNATIVE_HASHING_THRESHOLD);boolean rehash &＃61; oldAltHashing ^ useAltHashing;//是否需要重新计算hash值transfer(newTable, rehash);//将oldTable的元素迁移到newTabletable &＃61; newTable;//将新数组重新赋值//重新计算阈值threshold &＃61; (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY &＃43; 1);
}
void transfer(Entry[] newTable, boolean rehash) {int newCapacity &＃61; newTable.length;for (Entry<K,V> e : table) {//遍历oldTable迁移元素到newTablewhile(null !&＃61; e) {//①处会导致闭环&＃xff0c;从而导致e永远不为空&＃xff0c;然后死循环&＃xff0c;内存直接爆了Entry<K,V> next &＃61; e.next;if (rehash) {//是否需要重新计算hash值e.hash &＃61; null &＃61;&＃61; e.key ? 0 : hash(e.key);}int i &＃61; indexFor(e.hash, newCapacity);e.next &＃61; newTable[i];//①newTable[i] &＃61; e;//①e &＃61; next;//①}}
}


jdk 1.8 源码(比较长&＃xff0c;慢慢品哈)

final Node<K,V>[] resize() {Node<K,V>[] oldTab &＃61; table;//保存旧数组int oldCap &＃61; (oldTab &＃61;&＃61; null) ? 0 : oldTab.length;int oldThr &＃61; threshold;//保存旧阈值int newCap, newThr &＃61; 0;//创建新的数组大小、新的阈值if (oldCap > 0) {if (oldCap >&＃61; MAXIMUM_CAPACITY) {//判断当前数组大小是否达到最大值threshold &＃61; Integer.MAX_VALUE;return oldTab;}else if ((newCap &＃61; oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >&＃61; DEFAULT_INITIAL_CAPACITY)newThr &＃61; oldThr << 1; //扩容两倍的阈值}else if (oldThr > 0) // 初始化新的数组大小newCap &＃61; oldThr;else {//上面条件都不满足&＃xff0c;则使用默认值newCap &＃61; DEFAULT_INITIAL_CAPACITY;newThr &＃61; (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr &＃61;&＃61; 0) {//初始化新的阈值float ft &＃61; (float)newCap * loadFactor;newThr &＃61; (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold &＃61; newThr;//将新阈值赋值到当前对象&＃64;SuppressWarnings({"rawtypes","unchecked"})//创建一个newCap大小的数组NodeNode<K,V>[] newTab &＃61; (Node<K,V>[])new Node[newCap];table &＃61; newTab;if (oldTab !&＃61; null) {for (int j &＃61; 0; j < oldCap; &＃43;&＃43;j) {//遍历旧的数组Node<K,V> e;if ((e &＃61; oldTab[j]) !&＃61; null) {oldTab[j] &＃61; null;//释放空间if (e.next &＃61;&＃61; null)//如果旧数组中e后面没有元素&＃xff0c;则直接计算新数组的位置存放newTab[e.hash & (newCap - 1)] &＃61; e;else if (e instanceof TreeNode)//如果是红黑树则单独处理((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { //链表结构逻辑&＃xff0c;解决hash冲突Node<K,V> loHead &＃61; null, loTail &＃61; null;Node<K,V> hiHead &＃61; null, hiTail &＃61; null;Node<K,V> next;do {next &＃61; e.next;if ((e.hash & oldCap) &＃61;&＃61; 0) {if (loTail &＃61;&＃61; null)loHead &＃61; e;elseloTail.next &＃61; e;loTail &＃61; e;}else {if (hiTail &＃61;&＃61; null)hiHead &＃61; e;elsehiTail.next &＃61; e;hiTail &＃61; e;}} while ((e &＃61; next) !&＃61; null);//原索引放入数组中if (loTail !&＃61; null) {loTail.next &＃61; null;newTab[j] &＃61; loHead;}//原索引&＃43;oldCap放入数组中if (hiTail !&＃61; null) {hiTail.next &＃61; null;newTab[j &＃43; oldCap] &＃61; hiHead;//jdk1.8优化的点}}}}}return newTab;}


总结

  jdk1.7扩容是重新计算hash&＃xff1b;jdk1.8是要看看原来的hash值新增的那个bit是1还是0好了&＃xff0c;如果是0则索引没变&＃xff0c;如果是1则索引变成"原索引&＃43;oldCap".这是jdk1.8的亮点&＃xff0c;设计的确实非常的巧妙&＃xff0c;即省去了重新计算hash值得时间&＃xff0c;又均匀的把之前的冲突的节点分散到新的数组bucket上

  jdk1.7在rehash的时候&＃xff0c;旧链表迁移到新链表的时候&＃xff0c;如果在新表的数组索引位置相同&＃xff0c;则链表元素会倒置&＃xff0c;但是jdk1.8不会倒置