1、HasMap 底层实现

JDK 1.8

HashMap 底层设计涉及到三种不同的数据结构，分别是数组、链表、红黑树。

1、基本的存储是数组，根据 key 值求出一个数组下标，将元素（key-value）存入到下标对应的位置。

2、存入的数据过多的话，key 所求出下标就有可能重复，叫做哈希冲突，怎么解决？引入链表，在数组的具体位置发展出一条链表，来存储多个下标一致的元素。

3、如果链表很长的话，会影响到元素的查询速度，为了提高查询速度，引入了红黑树（平衡二叉树），当链表长度大于 8 的时候，自动转换成红黑树。

2、HashMap 加载顺序

创建 HashMap 并不会创建数组，而是定义加载因子（数组扩容使用）

当给 HashMap 添加元素的时候，再来创建数组，懒加载机制，数组长度为 16。

(h = key.hashCode()) ^ (h >>> 16)

如果 key 不为 null，则返回 key 的 hashCode 和自己的高 16 位进行异或（相同为0，不同为1）运算得出的结果。

h >>> 16，无符号右移，取出 h 的高 16 位
0000 0100 1011 0011 1101 1111 1110 0001>>> 160000 0000 0000 0000 0000 0100 1011 0011

问题：既然已经拿到了 key 的 hashCode，为什么不直接返回？而要进行复杂的运算呢？

int 的取值范围是 -21 亿- 21 亿，40 亿种可能，而数组的默认长度为 16，远远小于 hash 可取值的范围，所以很有可能多次求出的下标根本不能用。

所以需要 hashCode 与自己的高 16 位进行异或运算，目的是混合原始 hash 码的高位和低位，以此来加大低位的随机性，尽量让值变小。

尽管如此，取到的值仍然很可能超过数组下标，所以为了保证绝对的安全性，拿到 hash 值之后，再与数组的最大索引（15）进行按位与运算（都为1返回1，否则返回0）得到索引。

hashCode：1111 1111 1111 1111 1111 0000 1110 1010h:			1111 1111 1111 1111 1111 0000 1110 1010
h >>> 16:	0000 0000 0000 0000 1111 1111 1111 1111hash：h^h>>>16:   1111 1111 1111 1111 0000 1111 0001 010115 & hash:		  0000 0000 0000 0000 0000 0000 0000 11111111 1111 1111 1111 0000 1111 0001 01010000 0000 0000 0000 0000 0000 0000 0101 = 5

HashMap 的存值过程

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//创建一个 Node 数组 tab，就是哈希桶Node<K,V>[] tab; Node<K,V> p; int n, i;//判断数组是否为空，如果为空就创建数组//HashMap的数组是延迟创建，这也是一种优化机制if ((tab = table) == null || (n = tab.length) == 0)//resize是创建数组和扩容数组的方法，这里是创建了长度为16的数组，用n记录它的长度,n=16n = (tab = resize()).length;//通过索引取出数组元素，判断是否为nullif ((p = tab[i = (n - 1) & hash]) == null)//如果为null，直接创建一个 Node 存入tab[i] = newNode(hash, key, value, null);else {//如果不为null，判断 key 是否相同Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//如果相同，直接覆盖原来的值e = p;//如果不相同，需要在原 Node 的基础上那个添加新的 Node//首先判断该位置是链表还是红黑树else if (p instanceof TreeNode)//如果是红黑树，将 Node 存入红黑树e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//如果是链表，就遍历链表for (int binCount = 0; ; ++binCount) {//找到最后一位if ((e = p.next) == null) {//将 Node 添加到链表的最后一位p.next = newNode(hash, key, value, null);//如果长度超过 8，需要将链表转成红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);//进入 treeifyBin 方法<!-- start -->if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {<!-- end -->//当数组的长度小于 64 的时候，并不会转换成红黑树，而是对数组进行扩容，能用数组就尽量用数组，因为数组查询效率最高break;}//如果链表中存值重复的 key 值，直接把当前元素赋给 p 进行替换if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);//返回被覆盖的 valuereturn oldValue;}}++modCount;//Node 个数++ //threshold=capacity* loadFactor=16*0.75=12if (++size > threshold)resize();afterNodeInsertion(evict);//如果 key 不重复，则返回 nullreturn null;
}

什么是 Node？

Node 是 Map.Entry 的实现类，就将 key 和 value 封装成一个对象。

1、根据 key 计算 hash 值。
2、在 put 的时候判断数组是否存在，如果不存在用 resize 方法创建长度为 16 的数组。
3、确定要存入的 node 在数组中的位置，根据 hash 与数组最大索引进行按位与运算得到下标。
4、判断该位置是否有元素，如果没有直接创建一个 Node 存入。
5、如果有元素，判断 key 是否相同，如果相同，则覆盖并返回。
6、如果不同，需要在原 Node 基础上添加新的 Node，首先判断该位置是链表还是红黑树。
7、如果是红黑树，将 Node 存入红黑树。
8、如果是链表，遍历链表，找到最后一位将 Node 存入。
9、将 Node 存入之后，需要判断此时链表的长度是否超过 8，如果超过 8 需要将链表转换为红黑树，这里还有一个条件，如果数组的长度小于 64，会再进行一次数组扩容，当数组长度大于 64 的时候才会进行转换。
10、添加完成之后，再判断数组是否需要扩容。