HashMap链表转为红黑树的临界值为8的原因
HashMap原理
// 这是一个阈值，当桶(bucket)上的链表数大于这个值时会转成红黑树，put方法的代码里有用到。put的时候如果两个值
// 经过hash后都落在同一个bucket上这叫发生一次hash碰撞，往里不断put数据，当一个bucket发生8次碰撞就转成红黑树。
static final int TREEIFY_THRESHOLD = 8;
// 也是阈值同上一个相反，当桶(bucket)上的链表数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
TREEIFY_THRESHOLD = 8的原因
理想状态下哈希表的每个“箱子”中，元素的数量遵守泊松分布:
泊松分布的参数λ是单位时间(或单位面积)内随机事件的平均发生率。 泊松分布适合于描述单位时间内随机事件发生的次数。（来自百度百科）
理想来说，在负载因子为0.75的条件下，bin中Node出现的频率满足参数为0.5的泊松分布。
当负载因子为 0.75 时，上述公式中 λ 约等于 0.5，因此箱子中元素个数和概率的关系如下:
| 数量 | 概率 |
|---|---|
| 0 | 0.60653066 |
| 1 | 0.30326533 |
| 2 | 0.07581633 |
| 3 | 0.01263606 |
| 4 | 0.00157952 |
| 5 | 0.00015795 |
| 6 | 0.00001316 |
| 7 | 0.00000094 |
| 8 | 0.00000006 |
从概率来看，之所以链表长度超过 8 以后要变成红黑树，因为在正常情况下出现这种现象的几率小到忽略不计。一旦出现，几乎可以认为是哈希函数设计有问题导致的。
HashMap的大小要设置为2的n次幂的原因
HashMap中的数据结构是数组+单链表的组合，我们希望的是元素存放的更均匀，最理想的效果是，Entry数组中每个位置都只有一个元素，这样，查询的时候效率最高，不需要遍历单链表，也不需要通过equals去比较K，而且空间利用率最大。
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
h:为插入元素的hashcode
length:为map的容量大小
&：与操作 比如 1101 & 1011=1001
//计算key的hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。最终的bucketIndex是通过取余来运算,总是可以得到在bucket长度区间内的结果。
h的计算是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。
HashMap加载因子默认为0.75的原因
HashMap的插入和搜索，复杂度都是O(1)，是非常快速的跟你的容量大小通常是没有直接关系的但是这是理想的情况。 这里说的理想，是在你所存储的对象的hashcode这个方法写的非常有效的情况下。根据hash的原理，存放一个对象是根据他的hashcode来计算的，如果没有哈希冲突，那么他的存储效率是最高，最完美的。
当通过HashCode计算地址存放，发现当前位置已经有元素，则称为元素的碰撞，需要重新计算或者其他方式放置该元素。
哈希表为了避免这种冲突，会有一点优化。简单的说，原本可以放100个数据的空间，当放到80个的时候，根据经验，接下去冲突的可能性会更加高，就好比一个靶子上80%都是箭的时候你再射一箭出去，射中箭的可能性很大。因此就自动增加空间来减小冲突可能性。
个数与碰撞几率服从柏松分布，发现在0.75处几率最小。
默认加载因子在时间和空间成本上寻求一种折衷,是对空间和时间效率的一个平衡选择。
解决hash冲突的办法
- 开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
- 再哈希法
- 链地址法
- 建立一个公共溢出区
HashMap允许null值的原因
ConcurrentHashmap和Hashtable都是支持并发的，这样会有一个问题，当你通过get(k)获取对应的value时，如果获取到的是null时，你无法判断，它是put（k,v）的时候value为null，还是这个key从来没有做过映射。HashMap是非并发的，可以通过contains(key)来做这个判断。
多线程下HashMap的resize()为什么会出现死循环?
存在的问题：HashMap为数组+链表结构，链表结构容易形成闭合的链路，这样在循环的时候只要有线程对这个HashMap进行get操作就会产生死循环。
只有在多线程并发的情况下才会出现这种情况，那就是在put操作的时候，如果size>initialCapacity*loadFactor，那么这时候HashMap就会进行rehash操作，随之HashMap的结构就会发生翻天覆地的变化。很有可能就是在两个线程在这个时候同时触发了rehash操作，产生了闭合的回路。
/* 初始化或者是将table大小加倍。如果为空，则按threshold分配空间，否则，加倍后，每个容器中的元素在新table中要么呆在原索引处，要么有一个2的次幂的位移
* @return the table
*/
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; // 阈值加倍
} else if (oldThr > 0) // 如果oldCap<=0，初始容量为阈值threshold
newCap = oldThr;
else { // 零初始化阈值表明使用默认值
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) {
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K, V>)e).split(this, newTab, j, oldCap); //红黑树分裂
else { // 保持原有顺序
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) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//新表索引：hash & (newCap - 1)---》低x位为Index
//旧表索引：hash & (oldCap - 1)---》低x-1位为Index
//newCap = oldCap << 1
//举例说明：resize()之前为低x-1位为Index，resize()之后为低x位为Index
//则所有Entry中，hash值第x位为0的，不需要哈希到新位置，只需要呆在当前索引下的新位置j
//hash值第x位为1的，需要哈希到新位置，新位置为j+oldCap
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。
/**
* 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;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
我们会发现转移的时候是逆序的。假如转移前链表顺序是1->2->3，那么转移后就会变成3->2->1。
当我们用线程一调用map.get(11)时，悲剧就出现了——Infinite Loop。
网友评论