HashMap源码
基础知识
底层数据结构：数组+链表+红黑树
优化：
JDK 1.8开始优化了hashmap的数据结构，链表 -> 红黑树，解决hash冲突的问题。
JDK 1.8以后，如果一个链表的长度超过了8，就会自动将链表转换为红黑树，链表的遍历性能，时间复杂度是O(n)，红黑树是O(logn)，所以如果出现了大量的hash冲突以后，红黑树的性能比链表高得多
红黑树的基础知识
1. 红黑树是二叉查找树，左小右大，根据这个规则可以快速查找某个值
2. 但是普通的二叉查找树，是有可能出现瘸子的情况，只有一条腿，不平衡了，导致查询性能变成O(n)，线性查询了
3. 红黑树，红色和黑色两种节点，有一大堆的条件限制，尽可能保证树是平衡的，不会出现瘸腿的情况
4. 如果插入节点的时候破坏了红黑树的规则和平衡，会自动重新平衡，变色（红 <-> 黑），旋转，左旋转，右旋转
JDK8的优化项
扩容机制和原理
hash冲突后如何解决
链表及红黑树的解决方式
如何减少hash碰撞
如何优化hash寻址
高性能rehash算法
核心方法
对key，进行一个hashCode()的一个运算，获取key的hash值
常规的一个做法，就是用这个hash值对数组的长度进行取模，根据取模的结果，将key-value对方在数组中的某个一个元素上
详见hashmap数据结构图
[](https://www.mdeditor.com/images/logos/markdown.png "hashmap数据结构图")
核心成员变量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 运算得到的值为16 数组的默认的初始大小是16，这个跟ArrayList是不一样的，初始的默认大小是10
static final float DEFAULT_LOAD_FACTOR = 0.75f //负载因子这个参数，默认的负载因子，如果数组里的元素个数达到了数组大小（16） * 负载因子（0.75f），默认是达到12个元素，就会进行数组的扩容
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}这是一个很关键的内部类，他其实是代表了一个key-value对，里面包含了key的hash值，key，value，还有就是可以有一个next的指针，指向下一个Node，也就是指向单向链表中的下一个节点，通过这个next指针，就可以形成一个链表
transient Node<K,V>[] table; Node<K, V>[]，这个数组就是map核心数据结构的数组，数组的元素就可以看到是Node类型的，天然就可以挂成一个链表，单向链表，Node里面只有一个next指针。
transient int size;这个size代表的是就是当前hashmap中有多少个key-value对，如果这个数量达到了指定大小 * 负载因子，那么就会进行数组的扩容。
int threshold;这个值，其实就是说capacity（就是默认的数组的大小），就是说capacity * loadFactory，就是threshold，如果size达到了threshold，那么就会进行数组的扩容。
final float loadFactor;默认就是负载因子，默认的值是0.75f，你也可以自己指定，如果你指定的越大，一般就越是拖慢扩容的速度，一般不要修改。
优化后的降低冲突概率的hash算法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}这个方法是计算出来了key的hash值
h = key.hashCode()：这个就是直接获取了key的hash值，通过的是hashCode()方法
1111 1111 1111 1111 1111 1010 0111 1100
h >>> 16，这个是位运算的操作，这个东西是把32位的二进制的数字，所有的bit往右侧右移了16位
1111 1111 1111 1111 1111 1010 0111 1100
-> h >>> 16
0000 0000 0000 0000 1111 1111 1111 1111
-> h ^ (h >>> 16)
1111 1111 1111 1111 1111 1010 0111 1100
0000 0000 0000 0000 1111 1111 1111 1111
1111 1111 1111 1111 0000 0101 1000 0011
他这么做，其实是考虑到，将他的高16位和低16位进行一个异或运算，必须记住这么一个结论，在面试的时候被问到hashmap的话，必须得说出来这个意思
就是因为，后面在用这个hash值定位到数组的index的时候，也有一个位运算
但是的话呢，一般那个后面的位运算，一般都是用低16位在进行运算，所以说如果你不把hash值的高16位和低16位进行运算的话，那么就会导致你后面在通过hash值找到数组index的时候，只有hash值的低16位参与了运算
提前在hash()函数里面，就会把高16位和低16位进行一下异或运算，就可以保证说，在hash值的低16位里面，可以同时保留他的高16位和低16位的特征，大家一定要记住这个结论
这么做有什么好处呢？为什么要保证同时将高16位和低16位的特征同时纳入运算，考虑到数组index的定位中去呢？因为这样子可以保证降低hash冲突的概率，如果说直接用hash值的低16位去运算定位数组index的话，可能会导致一定的hash冲突
put操作原理以及hash寻址算法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;(n - 1) & hash
n = 16
n - 1 = 15
15 & hash
1111 1111 1111 1111 0000 0101 1000 0011
0000 0000 0000 0000 0000 0000 0000 1111
-> 与操作
就是必须都是1，才是1，否则就是0
0000 0000 0000 0000 0000 0000 0000 0011，转成10进制，就是3，index = 3
他的hash寻址的算法， 并不是说用hash值对数组大小取模，取模就可以将任意一个hash值定位到数组的一个index那儿去，取模的操作性能不是太高
位运算，性能很高，&与操作，来实现取模的效果
他优化以后的一个效果，就是说他的数组刚开始的初始值，以及未来每次扩容的值，都是2的n次方
也就是说他后面每次扩容，数组的大小就是2的n次方，只要保证数组的大小是2的n次方，就可以保证说，(n - 1) & hash，可以保证就是hash % 数组.length取模的一样的效果，也就是说通过(n - 1) & hash，就可以将任意一个hash值定位到数组的某个index里去
i = (n - 1) & hash，i就是最后寻址算法获取到的那个hash值对应的数组的index
hash冲突时的链表处理
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//hash定位到的这个位置是空的，之前没有任何人在这里，此时直接是放一个Node在数组的这个位置即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K, V> e;
K k;
// 如果满足条件，说明是相同的key，覆盖旧的value
// map.put(1, “张三”)
// map.put(1, “李四”)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 这个key值已经转成红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 把旧值的下一个指针指向这个新值
// 单向链表
p.next = newNode(hash, key, value, null);
// 如果当前链表的长度（binCount），大于等于等于8的话，那么此时就需要将这个链表转换为一个红黑树的数据结构
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
// 张三就是oldValue
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}JDK 1.8引入红黑树优化hash冲突
如果说出现大量的hash冲突之后，假设某给位置挂的一个链表特别的长，就很恶心了，如果链表长度太长的话，会导致有一些get()操作的时间复杂度就是O(n)，
但是如果链表，大量的key冲突，会导致get()操作，性能急剧下降，导致很多的问题
所以说JDK 1.8以后人家优化了这块东西，会判断，如果链表的长度达到8的时候，那么就会将链表转换为红黑树，如果用红黑树的话，get()操作，即使对一个很大的红黑树进行二叉查找，那么时间复杂度会变成O(logn)，性能会比链表的O(n)得到大幅度的提升
链表转红黑树是怎么搞的
当你遍历一个链表达到第7个节点的时候，binCount是6
当你遍历到第8个节点，此时binCount是7，同时你挂上了第9个节点，然后就会发现binCount >= 7，达到了临界值，也就是说，当你的链表节点的数量超过8的时候，此时就会将链表转换为红黑树
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K, V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);上面那个do while循环执行完了以后，先是将单向链表转换为了TreeNode类型组成的一个双向链表
if ((tab[index] = hd) != null)
hd.treeify(tab);
接下来针对双向链表，将双向链表转换为一颗红黑树，直接记住这个结论就ok了，当链表的长度超过8的时候，链表就先是变成双向链表，然后是变成红黑树
基于数组的扩容原理图解
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
}扩容的新长度为旧长度左移一位，即原先的两倍
JDK 1.8的高性能rehash算法
DK 1.8以后，为了提升rehash这个过程的性能，不是说简单的用key的hash值对新数组.length取模，取模给大家讲过，性能较低，所以JDK 1.8以后hash寻址这块，统一都是用的这个位操作
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash1 1111 1111 1111 1111 0000 1111 0000 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash2 1111 1111 1111 1111 0000 1111 0001 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
此时，上面两个hash值会出现hash碰撞的问题，使用链表，或者是红黑树来解决
如果数组的长度扩容之后 = 32，重新对每个hash值进行寻址，也就是用每个hash值跟新数组的length - 1进行与操作
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash1 1111 1111 1111 1111 0000 1111 0000 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash2 1111 1111 1111 1111 0000 1111 0001 0101
&结果 0000 0000 0000 0000 0000 0000 0001 0101 = 21（index = 21的位置）
00101 = 5
10101 = 21
hash2的位置，从原来的5变成了21，规律是什么？
也就是说，JDK 1.8，扩容一定是2的倍数，从16到32到64到128
就可以保证说，每次扩容之后，你的每个hash值要么是停留在原来的那个index的地方，要么是变成了原来的index（5） + oldCap（16） = 21
所以说，这个就是JDK 1.8以后，数组扩容的时候，元素重新寻址的一个过程和原理
hashmap的底层原理
hash算法：为什么要高位和低位做异或运算？
hash寻址：为什么是hash值和数组.length - 1进行与运算？
hash冲突的机制：链表，超过8个以后，红黑树
扩容机制：数组2倍扩容，重新寻址（rehash），hash & n - 1。 判断二进制结果中是否多出一个bit的1，如果没多，那么就是原来的index，如果多了出来，那么就是index+oldCap，通过这个方式，就避免了rehash的时候，用每个hash对新数组.length取模，取模性能不高，位运算的性能比较高
