共计 5316 个字符，预计需要花费 14 分钟才能阅读完成。
1. 考查 HashMap
1.1 HashMap 的底层数据结构
解答：在 jdk1.8 以前，HashMa 采纳链表 + 数组，自 Jdk1.8 当前，HashMap 采纳链表 + 数组 + 红黑树。在下图中横链 (0-15) 表中示意数组，竖 (1-8) 示意链表，在数组长度超过 8 之后，hashmap 将数组主动转为红黑树。
1.2 JDK1.8 对 hash 算法和寻址算法如何优化的？
1.2.1 对 Hash 值算法的优化
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}有一个 key 的 Hash_1 值：
Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100h >>> 16 // 示意对该 hash 值右移 16 位右移后的后果 Hash_2 为：
Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111对上述 Hash_1 和 Hash_2 的两个值进行异或
Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100
Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111
=====>: 1111 1111 1111 1111 0000 0101 1000 0011 =====> 转为 10 进制 int 值，这个值就是这个 key 的 hash 值hash 算法的优化：对每个 hash 值，在它的低 16 位中，让高下 16 位进行异或，让它的低 16 位同时放弃了高下 16 位的特色，尽量避免一些 hash 值后续呈现抵触，大家可能会进入数组的同一地位。
1.2.2 对寻址算法的优化
(p = tab[i = (n - 1) & hash]
// (n-1) & hash ==> 数组里的一个地位hash & (n-1) 成果是跟 hash 对 n 取模是一样的，然而与运算的性能要比 hash 对 n 取模要高很多。数组的长度会始终是 2 的 n 次方，只有他放弃数组长度是 2 的 n 次方。
-
- 寻址为什么不必取模？
对于下面寻址算法，因为计算机比照取模，与运算会更快。所以为了效率，HashMap 中规定了哈希表长度为 2 的 k 次方，而 2^k-1 转为二进制就是 k 个间断的 1，那么 hash & (k 个间断的 1) 返回的就是 hash 的低 k 个位，该计算结果范畴刚好就是 0 到 2^k-1，即 0 到 length – 1，跟取模后果一样。
也就是说，哈希表长度 length 为 2 的整次幂时，hash & (length - 1) 的计算结果跟 hash % length 一样，而且效率还更好。
-
- 为什么不间接用 hashCode() 而是用它的高 16 位进行异或计算新 hash 值？#
int 类型占 32 位，能够示意 2^32 种数（范畴：-2^31 到 2^31-1），而哈希表长度个别不大，在 HashMap 中哈希表的初始化长度是 16（HashMap 中的 DEFAULT_INITIAL_CAPACITY），如果间接用 hashCode 来寻址，那么相当于只有低 4 位无效，其余高位不会有影响。这样如果几个 hashCode 别离是 210、220、2^30，那么寻址后果 index 就会一样而发生冲突，所以哈希表就不均匀分布了。
寻址算法的优化：用与运算代替取模，晋升性能。（因为计算机比照取模，与运算会更快）
1.3 HashMap 是如何解决 hash 碰撞问题
hash 抵触问题，链表 + 红黑树，O(n)和 O(logN)
hashmap 采纳的就是链地址法（拉链法），jdk1.7 中，当抵触时，在抵触的地址上生成一个链表，将抵触的元素的 key，通过 equals 进行比拟，雷同即笼罩，不同则增加到链表上，此时如果链表过长，效率就会大大降低，查找和增加操作的工夫复杂度都为 O(n)；然而在 jdk1.8 中如果链表长度大于 8，链表就会转化为红黑树，工夫复杂度也降为了 O(logn)，性能失去了很大的优化。
1.4 HashMap 是如何进行扩容的
HashMap 底层是一个数组，当这个数组满了之后，他就会主动进行扩容，变成一个更大数组。
1.4.1 JDK1.7 下的扩容机制
void resize(int newCapacity) {Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}代码中能够看到，如果原有 table 长度曾经达到了下限，就不再扩容了。如果还未达到下限，则创立一个新的 table，并调用 transfer 办法：
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {while(null != e) {
Entry<K,V> next = e.next; // 正文 1
if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity); // 正文 2
e.next = newTable[i]; // 正文 3
newTable[i] = e; // 正文 4
e = next; // 正文 5
}
}
}transfer 办法的作用是把原 table 的 Node 放到新的 table 中，应用的是 头插法，也就是说，新 table 中链表的程序和旧列表中是相同的，在 HashMap 线程不平安的状况下，这种头插法可能会导致环状节点。
1.4.2 JDK1.8 下的扩容机制
源码如下：
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) {if (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 // 从新计算 TREEIFY_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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) { // 从新计算原来链表中的值的 hash 值在新表对应的 hash 值
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {oldTab[j] = null;
if (e.next == null) // 如果元素 e 的下一个地位没有值，则阐明能够寄存元素
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 如果曾经是红黑树的节点，那就对其从新划分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// loHead: 下标不变状况下的链表头
// loTail: 下标不变状况下的链表尾
// hiHead: 下标扭转状况下的链表头
// hiTail: 下标扭转状况下的链表尾
// 如果
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 元素 e 的最新 hash 如果与原来的值与计算之后如果值为 0，就阐明是应用原来的 index
// 尾插法插入元素 e
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 与运算不等于 0 则阐明应用新的 index
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;
}失常状况下，计算节点在 table 中的下标的办法是：hash&(oldTable.length-1)，扩容之后，table 长度翻倍，计算 table 下标的办法是 hash&(newTable.length-1)，也就是 hash&(oldTable.length*2-1)，于是咱们有了这样的论断：这新旧两次计算下标的后果，要不然就雷同，要不然就是新下标等于旧下标加上旧数组的长度。
e.g.
数组长度为 16 时，有两个 keyA 和 keyB
KeyA：n-1: 0000 0000 0000 0000 0000 0000 0000 1111
hash1: 1111 1111 1111 1111 0000 1111 0000 0101
& 后果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5
KeyB:
n-1: 0000 0000 0000 0000 0000 0000 0000 1111
hash1: 1111 1111 1111 1111 0000 1111 0001 0101
& 后果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5在数组长度为 16 的时候，他们两个 hash 值抵触会应用拉链法解决抵触。
当数组长度扩容到 32 之后，须要从新对每个 hash 值进行寻址，也就是每个 hash 值跟新的数组 length-1 进行操作。
KeyA：n-1: 0000 0000 0000 0000 0000 0000 000*1* 1111
hash1: 1111 1111 1111 1111 0000 1111 0000 0101
& 后果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5
KeyB:
n-1: 0000 0000 0000 0000 0000 000*1* 0000 1111
hash1: 1111 1111 1111 1111 0000 1111 0001 0101
& 后果: 0000 0000 0000 0000 0000 000*1* 0000 0101 = 21判断二进制后果是否多出一个 bit 的 1，如果没有多，那就用原来的 index，如果多进去了那就用 index+oldCap，通过这个形式，防止了 rehash 的时候，用每个 hash 对新数组的 length 取模，取模性能不高，位运算性能比拟高。
