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 1100Hash_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 1111hash1: 1111 1111 1111 1111 0000 1111 0000 0101&后果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5KeyB: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* 1111hash1: 1111 1111 1111 1111 0000 1111 0000 0101&后果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5KeyB: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取模，取模性能不高，位运算性能比拟高。