读读源码|【源码】HashMap源码学习笔记单元测试|spring|intellij-idea|Jav

楔子
基本数据结构
核心成员变量解析
hash算法
- 从put看JDK优化后的hash算法
- hash寻址算法
hash冲突
- hash冲突时的链表处理
- hash冲突时的红黑树优化
扩容与rehash算法

楔子 HashMap作为Java集合里重要的一环，不仅在生产中有着超高频率的使用，在面试中更是被经常问起，所以学习Hash的源码对Java开发人员来说是很有必要的。
基本数据结构 JDK 1.8以后，hashmap的数据结构是，数组 + 链表 + 红黑树。
核心成员变量解析

/** * The default initial capacity - MUST be a power of two. * 默认初始容量是16，且必须是2的幂等 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. * 最大容量 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. * 扩容因子，默认0.75 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * The bin count threshold for using a tree rather than list for a * bin.Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. * 默认链表长度为8时，转换成红黑树 */ static final int TREEIFY_THRESHOLD = 8; /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. * 默认链表高度降为6时，取消红黑树 */ static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. * 默认最小树容量为64 */ static final int MIN_TREEIFY_CAPACITY = 64;

这是一个关键内部类，单向链表

static class Node implements Map.Entry { final int hash; final K key; V value; // next的指针，指向下一个Node，也就是指向单向链表中的下一个节点 Node next; }

// 单向链表构成的数组 transient Node[] table;

// 这个size代表的是就是当前hashmap中有多少个key-value对， // 如果这个数量达到了指定大小 * 负载因子，那么就会进行数组的扩容 transient int size;

// threshold表示当HashMap的size大于threshold时会执行resize操作。 // threshold=capacity*loadFactor int threshold;

// 负载因子，默认0.75F final float loadFactor

hash算法才开始学Java的时候，很多人应该都学过取模运算，这也是一种简单的hash算法，而HashMap中的hash算法是优化过的，性能很高，这一节小七就准备从此展开。
从put看JDK优化后的hash算法

public V put(K key, V value) { // putVal这个方法做的事情很多，我们暂时先不关注 // 先把重点放在hash(key)上 return putVal(hash(key), key, value, false, true); }

static final int hash(Object key) { int h; // ①如果key 为空，那么就把hash设为0 // ②如果key不为空，那么就通过key.hashCode()方法获取hash // ③然后获取将它向右侧移16位的值 // ④最后将这两个值做^运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

为什么要这么做呢？因为在定位数组的index时，会用到这个hash值做位运算，并且该位运算主要是针对后16位的。如果你不把hash值的高16位和低16位进行运算的话，那么就会导致你后面在通过hash值找到数组index的时候，只有hash值的低16位参与了运算。
hash寻址算法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // 刚开始table数组是空的，所以会分配一个默认大小的一个数组 // 数组大小是16，负载因子是0.75，threshold是12 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // hash为空，放在数组里 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; // 满足条件，说明是相同的key，覆盖旧的value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果已经是一棵红黑树了，需要做的事情（变色、旋转） else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); // key不一样，出现了hash冲突，然后此时还不是红黑树的数据结构， // 还是链表的数据结构，在这里，就会通过链表来处理 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 链表的总长度达到8的话， // 那么此时就需要将这个链表转换为一个红黑树的数据结构 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 = https://www.it610.com/article/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size> threshold) // 下一个知识点resize resize(); afterNodeInsertion(evict); return null; }

以上代码相对复杂，但是我们是带着目的去看的，所以关注点应该在类似于取模的运算上，也就是(n - 1) & hash这行关键代码。
假设，hashmap是空的，数组大小就是默认的16，负载因子就是默认的12。
(n - 1) & hash = （16-1）& hash
假设hash为：
1111 1111 1111 1111 0000 0101 1000 0011
15二进制对应：
0000 0000 0000 0000 0000 0000 0000 1111
&运算后为：
0000 0000 0000 0000 0000 0000 0000 0011
要保证和【hash % 数组.length】取模的一样的效果，(n - 1) & hash中的n必须是2的幂等，也就是说以后的每一次扩容都必须是2的幂等。
hash冲突 hash冲突时的链表处理

for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 链表的总长度达到8的话， // 那么此时就需要将这个链表转换为一个红黑树的数据结构 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; }

hash冲突时的红黑树优化

final void treeifyBin(Node[] tab, int hash) { int n, index; Node e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { // 以下是红黑树的核心代码 TreeNode hd = null, tl = null; do { TreeNode p = replacementTreeNode(e, null); if (tl == null) hd = p; else { // 前指针 p.prev = tl; // 后指针 tl.next = p; } tl = p; } while ((e = e.next) != null); // do while循环执行完了以后， // 先是将单向链表转换为了TreeNode类型组成的一个双向链表if ((tab[index] = hd) != null) // 接下来针对双向链表，将双向链表转换为一颗红黑树 hd.treeify(tab); } }

扩容与rehash算法因为HashMap的底层是数组，所以他和ArrayList一样，也有扩容的问题。
【读读源码|【源码】HashMap源码学习笔记】HashMap扩容的原理是，2倍扩容 + rehash，每个key-value对，都会基于key的hash值重新寻址找到新数组的新的位置，源代码如下：

if (++size > threshold) resize();

final Node[] resize() { Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 新数组的大小等于老数组的2倍 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[] newTab = (Node[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; // 如果e.next是null的话，这个位置的元素不是链表，也不是红黑树 // 那么此时就是用e.hash & newCap（新数组的大小） - 1，进行与运算 // 直接定位到新数组的某个位置，然后直接就放在新数组里了 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 如果是红黑树的话 // 那么会循环遍历这棵树，重新进行hash寻址 else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); // 以下为链表 // 判断二进制结果中是否多出一个bit的1， // 如果没多，那么就是原来的index， // 如果多了出来，那么就是index + oldCap else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node 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; newTab[j + oldCap] = hiHead; } } } } } return newTab; }