面试题04 HashMap实现原理
1. HashMap实现原理
JDK7： 数组 + 链表
JDK8： 数组 + 链表 + 红黑树
2. java7： put(key,value)源码概览
Entry< K,V>[] table;
public V put(K key, V value) {
//计算key的哈希值
int hash = hash(key);
//计算该哈希值在哈希表的下标
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//.....
return oldValue;
}
}
//......
}
JDK7_put(key,value)_step1：新put的元素要放在链表的head的前面最快速（不用遍历链表）
JDK7_put(key,value)_step2：头部插入后，向下移动
3. 为什么数组的长度必须是2的次幂？
1.计算hashCode整数，太大无法做数组下标
int hash = "key".hashCode();方法的值超级大：46730161
无法作为HashMap数组+链表结构中数组的下标
2. 解决办法：对hashCode取模
int i = hash % table.length;
如果table[]长度是8， 那么i 肯定介于0~7之间
3. 取模效率慢，用位运算
（1）计算机的计算效率：位运算 > 加法 > 乘法 > 除法 > 取模
（2）要想使位运算达到和取模同样的效果（结果值介于0和arr.length之间），需要使数组的长度是2n。
（3）即便在初始化HashMap的时候手动设定的数组长度不是2的次幂数，但在put(key,value)方法中也会重置这个长度。
static int indexFor(int h, int length) {
return h & (length-1);
}
if (length == 2的次幂) {
hash % length == hash & (length-1);
} else {
hash % length != hash & (length-1);
}
entry源码示例，典型的链表结构
3. 什么是加载因子?
是指HashMap数组元素使用率达到某一值时，数组进行扩容。
3.1. 加载因子变大（eg：1）
理论上： 数组的使用率是高了，最大化利用了空间，
实际上： 不可能最大化（100%）利用空间的，很多元素会因hash碰撞而放到了链表里
3.2. 加载因子变小（eg：0.5）
因为：数组的未使用空间（比例）变大（数组元素被占用不大比例的时候就扩容了），所以当put新元素的时候：
（1） 计算hash值
（2） 按位取模获取数组下标
导致：获取的下标值 已经被使用过的概率就变小了，未被使用过的概率变大
结果：
（1）会尽可能地避免hash碰撞（新key的数组下标被使用过的概率变小）
（2）链表的长度也会越小（未等放置更多的元素，数组就扩容了）
（3）链表深度浅，查询效率很高，节省时间，提高效率
（4）浪费空间，典型的拿（内存）空间换（查询）时间。
4. 加载因子为什么是0.75？
HashMap要在时间复杂度、空间复杂度、性能 上进行平衡，就需要在时间、空间上折中。折中的结果就是：负载因子是0.75。
5. 泊松分布之于HashMap：
HashMap.put(key,value)，本次一个<key,value>被put到某个桶位上，下次再put一个<key,value>依然是被put到本桶位上的概率遵循泊松分布。
泊松分布是一个概率统计学公式，当加载因子为0.75时，x: 链表长度；y：发生hash碰撞的概率呈指数级下降趋势
前提：负载因子为0.75时
x轴：链表元素个数。当为8时，y值接近1/亿。
y轴： <key,value>被put到上次put的桶位的概率。（hash碰撞的概率）
总结：随着链表长度的增加，<key,value>被put到同一个桶位的概率会越来越低，呈指数级下降趋势。
当加载因为为0.75，桶位的链表元素个数达到8时，再新增元素到HashMap时，被放置到本桶位的概率几乎为0。
6. java8红黑树
- 链表长度 > 8时，链表转红黑树
- 根据泊松定律，HashMap新增元素被放到元素个数为8的链表桶位的概率几乎为0
- 综上所述：Java8虽然增加了红黑树支持，但产生红黑树结构的概率也不大
- Java8 比 Java7 的性能有提升，但并不多，大概也就是8% ~ 10%
红黑树是近乎平衡的二叉树，当put元素多的时候，可能打破平衡，红黑树需要再平衡：树的左旋、右旋以及重新着色
7. JDK8中HashMap的链表为什么要转换成红黑树？
因为Map中桶的元素初始化是链表保存的，其查找性能是O(n)，而树结构能将查找性能提升到O(log(n))。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。
8. 为什么java8链表的长度为8的时候链表转红黑树？
[JDK1.8以后的hashmap为什么在链表长度为8的时候变为红黑树]
在JDK1.8以及以后的版本中，hashmap的底层结构，由原来单纯的的数组+链表，更改为链表长度为8时，开始由链表转换为红黑树，为何大刀阔斧的对hashmap采取这个改变呢，以及为何链表长度为8才转变为红黑树呢，下面结合源码一起来分析一下。
我们都知道，链表的时间复杂度是O(n)，红黑树的时间复杂度O(logn)，很显然，红黑树的复杂度是优于链表的，既然这么棒，那为什么hashmap为什么不直接就用红黑树呢，请看下图
image.png
源码中的注释写的很清楚，因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。
那为什么选择8才会选择使用红黑树呢？看下图
image.png
源码上说，为了配合使用分布良好的hashCode，树节点很少使用。并且在理想状态下，受随机分布的hashCode影响，链表中的节点遵循泊松分布，而且根据统计，链表中节点数是8的概率已经接近千分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。也就是大部分情况下，hashmap还是使用的链表，如果是理想的均匀分布，节点数不到8，hashmap就自动扩容了。为什么这么说呢，再看下图
image.png
在链表转变为红黑树方法中，有这样一个判断，数组长度小于MIN_TREEIFY_CAPACITY，就会扩容，而不是直接转变为红黑树，可不是什么链表长度为8就变为红黑树，要仔细看代码，还有别的条件，
image.png
现在回头想想，为啥用8？因为通常情况下，链表长度很难达到8，但是特殊情况下链表长度为8，哈希表容量又很大，造成链表性能很差的时候，只能采用红黑树提高性能，这是一种应对策略。
9. Java7的HashMap扩容死锁演示与环链行程分析。
HashMap的容量一旦达到扩容阈值的时候，会对HashMap扩容，并且把旧的内容移到新的数组中去。在移动过程中，Java7会产生死锁。这个死锁的本质就是环链的产生导致的。
