-
为什么map的容量是 2 n 2^n 2n
-
我们知道，散列是将键值映射为一个索引（散列方法），以此来加快检索速度。那么将键值映射就需要一个有效的数组下标，通常情况我们会使用取余数的方法。如果这时候数组的大小为n，那么索引取值范围是[0…n-1]，取余数操作就是
i n d e x = h a s h % n index = hash % n index=hash%n
如果是 2 n 2^n 2n的大小，我们可以使用&操作
i n d e x = h a s h & ( n − 1 ) index = hash & (n-1) index=hash&(n−1)
假设数组大小是n=8，hash为9，取余数索引值必然是0~7。 2 n 2^n 2n-1的二进制必然全是1，与全1进行&操作，1保留下来，0被置0，这样子的操作等同与取余且速度更快。1001 = 9 0111 = 8-1 ----------- 0001 = 1
-
-
为什么树化阈值是8，逆树化为6？
- 在加载因子为0.75的情况下，使用0.5的参数使用泊松分布。一个链表长度为8的情况已经是非常低了。
- 逆树化主要是避免8，9之间来回树化带来的损耗。
-
初始化大小？
- 16
-
最小树化容量？
- 如果map的capacity容量小于64，就会进行resize操作，而避免树化。
-
hash()方法使用hashCode的低16位与高16进行异或，来计算hash值
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }- 在capacity的容量偏低的情况下，掩码去除高位字节，只保留低位的字节计算，从而常常导致冲突。例如：在小表中，使用Float作为key，并保留着连续的整数。
- 目的：减少碰撞
- 大概意思：table使用2的幂次作为掩码，散列只在一些字节上计算，就会导致常常发生冲突。又因为很多的散列集都很合理的分布了，所以使用了这个最简易的方式去减少系统的损失，并结合高位（前16）的影响来计算索引。否则那些高位索引由于边界限制，永远都不会参与到索引的计算中。
-
计算cap算法
static final int tableSizeFor(int cap) { int n = cap - 1; //保证cap刚好是2的幂次时，不用增长 n |= n >>> 1; //最高第二位必然为1（这里指，从第一个1开始称最高） n |= n >>> 2; //最高的四位必然是1 n |= n >>> 4; //同理8位 n |= n >>> 8; //同理16位 n |= n >>> 16; //同理32位 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
-
putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node -
resize：初始化或者是将容量扩倍
//map不为空情况 if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //翻倍，后一个判断是因为初始容量小于default的resize操作 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //map为空，但存在初始化容量 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 (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node
resize导致的列表中元素重新分配。由于容量加倍，也就是说8加倍到16，进行&操作也就是多了一个1。
以hash=[1, 9, 25]，oldCap = 8，newCap = 16举例。
那么情况就是两种：
hash值：00001(1)，01001(9)，11001(25)。
旧索引： 00001(1)，00001(9)，00001(25)
新索引： 00001(1)，00001(9)，01001(25)。
多一位操作，意味着要么是0，要么是1。0的保持在原位，1的索引就刚好偏移的oldCap的大小
- treeifyBin：树化容器，同时将节点进行前后关联。
final void treeifyBin(Node
