前置知识点
源码逐行解析
优化技巧总结
1、整数乘法使用移位运算代替乘法运算提高效率
2、n为2的幂次时，可用(n – 1) & hash位运算实现取模运算hash % n
3、rehash时，二次幂扩容机制使其可根据奇偶因子快速定位新散列位置，详见下述resize()方法
4、无符号右移>>>和或运算|结合可在对数复杂度时间复制位，详见下述tablesizefor()方法
默认初始值
// 哈希表的默认初始容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 哈希表默认最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; // 哈希表默认负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 哈希冲突拉链法转红黑树的阈值 static final int TREEIFY_THRESHOLD = 8; // 链表树化时最小哈希表容量 static final int MIN_TREEIFY_CAPACITY = 64;
构造方法
无参构造指定默认负载因子0.75
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; }
单参构造自定义初始容量，后续首次调用put()方法时，会将容量设定为不小于指定数的最小二次幂，默认负载因子0.75
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
校验参数合法性，并限制最大容量MAXIMUM_CAPACITY
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
tableSizeFor()方法通过位运算获取不小于当前数的最小二次幂数，通过对数次复制最高位1获得低位全1，+1获得二次幂数
static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
其中n=cap-1保证二次幂数运算后是自身（见example=128）
cap=0时，n=cap-1 = -1，
$\scriptsize -1=[1000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000]_2$，
位运算后 $\scriptsize [1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111]_2$，
$\scriptsize n+1 = [1\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000]_2$ 丢弃高位仍是0
put()方法
put()时计算key的哈希值，转去执行putVal()
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
hash()值计算，使用默认或覆写的hashCode()值，将低16位和高16位异或获得hash，同时利用高低位信息以减少冲突（见源码注释）
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
putVal()主要将值插入哈希表，需要判空、判已存在、判新插入节点、解决哈希冲突
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i; // 首次put()初始化默认容量为16，阈值12 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 { HashMap.Node<K,V> e; K k; // 已存在节点则记录该节点，供后续更新为新值 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 插入位置为树节点，若树已存在节点则返回该节点供后续更新新值，否则为平衡插入新节点到红黑树，调整新root为哈希冲突链表入口 else if (p instanceof HashMap.TreeNode) e = ((HashMap.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) treeifyBin(tab, hash); break; } // 若链表已存在节点则记录该节点供后续更新新值 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 已存在的节点更新新值，返回旧值 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; // 供linkedHashMap子类覆写，本结构内为空方法体 afterNodeAccess(e); return oldValue; } } // 本次若插入新节点则需更新节点数量，并判断是否超过阈值引起扩容 ++modCount; if (++size > threshold) resize(); // 供linkedHashMap子类覆写，本结构内为空方法体 afterNodeInsertion(evict); // 插入新节点一律返回null return null; }
resize()
final HashMap.Node<K,V>[] resize() { HashMap.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; } // 无数据的哈希表扩容（有参构造首次调用put）指定容量为扩容阈值 else if (oldThr > 0) newCap = oldThr; // 无数据的哈希表扩容（无参构造首次调用put）设定默认容量16，默认扩容阈值12 else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 已达最大容量限制设置阈值Integer.MAX_VALUE，有参构造首次调用时计算扩容后阈值 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"}) HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap]; table = newTab; // 执行rehash if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { HashMap.Node<K,V> e; // 旧节点置空，可被GC回收 if ((e = oldTab[j]) != null) { oldTab[j] = null; // 单节点重新hash至扩容后的新位置 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 红黑树节点拆分重新hash至扩容后的新位置 else if (e instanceof HashMap.TreeNode) ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 链表节点快速重新hash至扩容后的新位置 else { HashMap.Node<K,V> loHead = null, loTail = null; HashMap.Node<K,V> hiHead = null, hiTail = null; HashMap.Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { // 重新组成lo链表 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // 重新组成hi链表 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // hash[j]槽中放lo链表 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // hash[j + oldCap]槽中放hi链表 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
以下说明扩容后快速计算散列位置的原理
$\scriptsize {}
扩容前后容量\
oldCap = capacity\
newCap = 2 * capacity\
扩容前散列至同一位置的hash可能包含奇数个或偶数个capacity\
oddHash= (2n+1) * capacity + i\
evenHash= (2n) * capacity + i\
oddHash \mod oldCap = i\
evenHash \mod oldCap = i\
扩容后包含奇数个capacity的hash散列至新位置，偶数个capacity的散列值不变\
oddHash \mod newCap = i + capacity = i + oldCap\
evenHash \mod newCap = i\
所以判定奇偶即可判定位置，判定方法如下\
[(2n+1) * capacity + i]_2中，capacity对应位必为1\
[(2n) * capacity]_2，capacity对应位必为0
$
putTreeVal
treeifyBin
split