共计 6414 个字符，预计需要花费 17 分钟才能阅读完成。
送大家以下 java 学习材料，支付形式看文章开端
一、HashMap 结构器
HashMap 总共给咱们提供了三个结构器来创立 HashMap 对象。
1. 无参构造函数public HashMap()：应用无参构造函数创立的 hashmap 对象，其默认容量为 16，默认的负载因子为 0.75。
2. 有参构造函数public HashMap(int initialCapacity，float loadFactor)：应用该构造函数，咱们能够指定 hashmap 的初始化容量和负载因子，然而在 hashmap 底层不肯定会初始化成咱们传入的容量，而是会初始化成大于等于传入值的最小的 2 的幂次方，比方咱们传入的是 17，那么 hashmap 会初始化成32（2^5）。那么 hashmap 是如何高效计算大于等于一个数的最小 2 的幂次方数的呢，源码如下：
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;
}
它的设计能够说很奇妙，其根本思维是如果一个二进制数低位全是 1，那么这个数 + 1 则必定是一个 2 的幂次方数。举个例子看一下：
能够看到，它的计算过程是：首先将咱们指定的那个数 cap 减 1（减 1 的起因是，如果 cap 正好是一个 2 的幂次方数，也能够正确计算），而后对 cap- 1 别离无符号右移 1 位、2 位，4 位、8 位、16 位(加起来正好是 31 位)，并且每次移位后都与上一个数做按位或运算，通过这样的运算，会使得最终的后果低位都是 1。那么最终对后果加 1，就会失去一个 2 的幂次方数。
3. 另一个有参构造函数就是有参构造函数public HashMap(int initialCapacity), 该构造函数和上一个构造函数惟一不同之处就是不能指定负载因子。
二、HashMap 插入机制
1. 插入方法源码
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
// 初始化桶数组 table，table 被提早到插入新数据时再进行初始化
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 {
Node<K,V> e; K k;
// 如果 hash 相等，并且 equals 办法返回 true，这阐明 key 雷同，此时间接替换 value 即可，并且返回原值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果第一个节点是树节点，则调用 putTreeVal 办法，将以后值放入红黑树中
else if (p instanceof TreeNode)
e = ((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);
// 判断链表中节点树是否超多了阈值 8，如果超过了则将链表转换为红黑树（当然不肯定会转换，treeifyBin 办法中还有判断）if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果在链表中找到，完全相同的 key，则间接替换 value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//e!=null 阐明只是遍历到两头就 break 了，该种状况就是在链表中找到了齐全相等的 key, 该 if 块中就是对 value 的替换操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 退出 value 之后，更新 size，如果超过阈值，则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
2. 插入流程图
（1）在 put 一个 k - v 时，首先调用 hash()办法来计算 key 的 hashcode, 而在 hashmap 中并不是简略的调用 key 的 hashcode 求出一个哈希码，还用到了扰动函数来升高哈希抵触。源码如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
从源码中能够看到，最终的哈希值是将原哈希码和原哈希码右移 16 位失去的值进行异或运算的后果。16 正好是 32 的一半，因而 hashmap 是将 hashcode 的高位挪动到了低位，再通过异或运算将高位散播的低位，从而升高哈希抵触。
至于为什么可能升高抵触呢，咱们能够看看作者对 hash 办法的正文：
Computes key.hashCode() and spreads (XORs) higher bits of hash to lower.
Because the table uses power-of-two masking,
sets of hashes that vary only in bits above the current mask will always collide.
(Among known examples are sets of Float keys holding consecutive whole numbers in small tables.)
So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed,
utility, and quality of bit-spreading.
Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading),
and because we use trees to handle large sets of collisions in bins,
we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage,
as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.从正文中咱们能够得出，作者进行高位向低位散播的起因是：因为 hashmap 在计算 bucket 下标时，计算方法为 hash&n-1,n 是一个 2 的幂次方数，因而 hash&n- 1 正好取出了 hash 的低位，比方 n 是 16，那么 hash&n- 1 取出的是 hash 的低四位，那么如果多个 hash 的低四位正好齐全相等，这就导致了 always collide（抵触），即便 hash 不同。因而将高位向低位散播，让高位也参加到计算中，从而升高抵触，让数据存储的更加散列。
（2）在计算出 hash 之后之后，调用 putVal 办法进行 key-value 的存储操作。在 putVal 办法中首先须要判断 table 是否被初始化了（因为 hashmap 是提早初始化的，并不会在创建对象的时候初始化 table），如果 table 还没有初始化，则通过 resize 办法进行扩容。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
（3）通过(n-1)&hash 计算出以后 key 所在的 bucket 下标，如果以后 table 中以后下标中还没有存储数据，则创立一个链表节点间接将以后 k - v 存储在该下标的地位。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
（4）如果 table 下标处曾经存在数据，则首先判断以后 key 是否和下标处存储的 key 齐全相等，如果相等则间接替换 value，并将原有 value 返回，否则持续遍历链表或者存储到红黑树。
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
（5）以后下标处的节点是树节点，则间接存储到红黑树中
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
（6）如果不是红黑树，则遍历链表，如果在遍历链表的过程中，找到相等的 key，则替换 value，如果没有相等的 key，就将节点存储到链表尾部（jdk8 中采纳的是尾插法），并查看以后链表中的节点树是否超过了阈值 8，如果超过了 8，则通过调用 treeifyBin 办法将链表转化为红黑树。
for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
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;
}
（7）将数据存储实现之后，须要判断以后 hashmap 的大小是否超过扩容阈值 Cap*load_fact, 如果大于阈值，则调用resize() 办法进行扩容。
f (++size > threshold)
resize();
HashMap 在扩容后的容量为原容量的 2 倍，起根本机制是创立一个 2 倍容量的 table，而后将数据转存到新的散列表中，并返回新的散列表。和 jdk1.7 中不同的是，jdk1.8 中多转存进行了优化，能够不再须要从新计算 bucket 下标，其实现源码如下：
从源码中咱们能够看出，如果一个 key hash 和原容量 oldCap 按位与运算后果为 0，则扩容前的 bucket 下标和扩容后的 bucket 下标相等，否则扩容后的 bucket 下标是原下标加上 oldCap。
应用的基本原理总结如下：
1、如果一个数 m 和一个 2 的幂次方数 n 进行按位与运算不等于 0，则有：m&(n2-1)=m&(n-1)+n了解：一个 2 的幂次方数 n，在二进制中只有一位为 1（假如第 k 位是 1），其余位均为 0，那个如果一个数 m 和 n 进行按位与运算后果为 0 的话，则阐明 m 的二进制第 k 位必定为 0，那么 m 的前 n 位和前 n - 1 位所示意的值必定是相等的。
2、如果一个数 m 和一个 2 的幂次方数 n 进行按位与运算等于 0，则有：m&(n2-1)=m&(n-1)了解：一个 2 的幂次方数 n，在二进制中只有一位为 1（假如第 k 位是 1），其余位均为 0，那个如果一个数 m 和 n 进行按位与运算后果不为 0 的话，则阐明 m 的二进制第 k 位必定为 1，那么 m 的前 n 位和前 n - 1 位所示意的值的差恰好是第 k 位上的 1 所示意的数，二这个数正好是 n。
原理图：
