超硬核HashMap底层构成以及扩容原理
HashMap的底层实现
JDK1.8之前
JDK1.8 之前 HashMap 底层是node数组和链表结合在一起使用也就是链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过(n-1)&hash判断当前元素存放的位置(这里的n指的是数组的长度),如果当前位置存在元素的话，就判断该元素与要存入的元素的hash 值以及key 是否相同，如果相同的话，直接覆盖，不相同就通过
解决冲突。
所谓扰动函数指的就是 HashMap 的 hash 方法可以减少碰撞。这点可以看后面
先说下JDK 1.8 HashMap 获取 hash 值的一个寻址优化
JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化（只扰动（异或）了一次），性能更好，但是原理和思想不变。
static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位异或
// >>>:无符号右移，忽略符号位，空位都以0补齐
//这里的操作可以将hash后的结果里低16位是融合了原来高16位和低16位的异或结果的，尽量让不同key获取的hash结果在低16位是不一样的，这样在长度是一定的情况下，可以让key更加分散。
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}对比一下 JDK1.7的 HashMap 的 hash 方法源码.
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);
}相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动（异或）了 4 次。
所谓“
” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
JDK1.8之后
相比于之前的版本， JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。(链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树.为啥这样可以解决冲突呢?因为数组扩容涉及到重新hash的问题.)
TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。
推荐阅读： 《Java 8系列之重新认识HashMap》 ：https://zhuanlan.zhihu.com/p/2167380
Hashmap中的链表大小超过八个时会自动转化为红黑树，当删除小于六时重新变为链表，为啥呢？
根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换，小于等于6的时候就化为链表。
Hashmap中扩容因子选择的是0.75为啥呢？
主要是出于时间和空间上的考虑
- 如果我们选择扩容因子是1,那么每次使用完全部空间再扩容势必造成时间上的等待问题
- 如果我们选择扩容因子是0.5,那么每次使用一半就扩容,造成了每次都有一半的空间是浪费的.
所以最终平衡了一下选择0.75 https://blog.csdn.net/penghao_1/article/details/107631820
HashMap 的长度为什么是2的幂次方
为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash ”。（n代表数组长度）。这也就解释了 HashMap 的长度为什么是2的幂次方。
这个算法应该如何设计呢？
我们首先可能会想到采用%取余的操作来实现。但是，
（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。”
HashMap的put和get方法源码解析
put过程分析,源码请看链接put/get
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}put()方法实际上是调用hash()方法获取到key的hash值 调用putVal()方法存储key-value 核心方法是putVal()方法 下面我会先分析一下hash()方法，因为这个方法涉及到hash值这个关键属性的计算。
hash()方法
static final int hash(Object key) {
int h;
// key为null时，hash值为0
// key不为null时，调用key对象的hashCode()方法并通过位运算异或和无符号右移将高位分散到低位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash()方法指定了null的hash值为0。这样就可以支持key为null。
(h = key.hashCode()) ^ (h >>> 16)这段代码通过位运算异或和无符号右移将高位分散到低位，这样做可以减少哈希碰撞的概率（这块不是很清楚原理，是从方法注释上了解到的）putVal()方法的关键点:
- 若table没有初始化则调用reszie()方法初始化。
- 计算在数组位置，公式为(n - 1) & hash（等价于hash%n）。其中n为数组长度，hash为插入的键值对的key的哈希值。
- 判断数组对应索引中的首节点是否为null，若为null，则创建链表，否则进入下一步。
- 判断该首节点是否与插入的键值对的key和hash一致，若一致则替换该节点的值为value，否则进入下一步
- 判断首节点是否为树节点，若是则调用树节点的putTreeVal()方法遍历红黑树，否则遍历链表。
- 遍历红黑树时，若存在key和hash相同的节点就替换对应节点的值value，若不存在则插入新的树节点。
- 遍历链表时，若存在key和hash相同的节点就替换对应节点的值为value。若找不到key和hash相同的节点，则链表尾部插入节点，同时进入下一步。
- 若当前链表长度大于或等于树化阈值TREEIFY_THRESHOLD(8)时，则将链表转化为红黑树。
get()
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}调用hash()方法获取到key的hash值 调用getNode()方法通过key和hash获取对应的value。不存在则返回null 核心方法是getNode()方法，下面我会先分析一下getNode()方法。
getNode()方法的关键点：
- 若散列表table不为null且长度大于0且其索引为(n - 1) & hash（等价于hash%n）的节点不为null。其中n为散列表长度，hash为插入的键值对的key的哈希值。则进入下一步，否则直接返回null
2 .判断首节点的key和hash是否与入参一致，若相同则返回首节点，否则进入下一步。 3判断节点个数只有1个，若是则返回null，否则进入下一步 4判断首节点是否为树节点，若是则遍历红黑树，否则为链表，进入下一步 5遍历链表，检索key和hash与入参相同的节点，若找到则返回该节点，否则返回null
HashMap 多线程操作导致死循环问题
在多线程下，进行 put 操作会导致 HashMap 死循环，原因在于 HashMap 的扩容 resize()方法。由于扩容是新建一个数组，复制原数据到数组。由于数组下标挂有链表，所以需要复制链表，但是多线程操作有可能导致环形链表。复制链表过程如下: 以下模拟2个线程同时扩容。假设，当前 HashMap 的空间为2（临界值为1），hashcode 分别为 0 和 1，在散列地址 0 处有元素 A 和 B，这时候要添加元素 C，C 经过 hash 运算，得到散列地址为 1，这时候由于超过了临界值，空间不够，需要调用 resize 方法进行扩容，那么在多线程条件下，会出现条件竞争，模拟过程如下：
这个过程为，先将 A 复制到新的 hash 表中，然后接着复制 B 到链头（A 的前边：B.next=A），本来 B.next=null，
到此也就结束了（跟线程二一样的过程），但是，由于线程二扩容的原因，将 B.next=A，所以，这里继续复制A，让
A.next=B，由此，环形链表出现：B.next=A; A.next=B
注意：jdk1.8已经解决了死循环的问题。