HashMap的底层数据结构 _HashMap

在 JDK1.8 中， HashMap 还引入了一个新的概念，叫做负载因子(load factor)，它是指哈希表中键值对的数量与数组长度的比值。当键值对的数量超过了负载因子与数组长度的乘积时，就会触发扩容操作，HashMap 会自动将数组长度扩大一倍，并将原来的键值对重新分配到新的数组中。这样做的目的是为了保证散列表的性能，因为当负载因子过高时，散列表的性能会急剧下降。

文章插图
一、HashMap基础机构HashMap 由数组和链表（或红黑树）组成。数组是 HashMap 的主体，链表和红黑树则是为了解决哈希冲突而存在的。数组中的每个元素都是一个单向链表的头结点，每个链表都是由若干个 Node 节点组成的，每个节点都包含了键值对的信息，以及指向下一个节点的指针。当多个键映射到同一个位置时，它们会被存储在同一个链表中（或者是同一个红黑树中）。当链表长度超过阈值（默认为 8）时，链表就会被转换成红黑树，这样可以提高查找效率。
在 JDK1.8 中，HashMap 还引入了一个新的概念，叫做负载因子(load factor)，它是指哈希表中键值对的数量与数组长度的比值。当键值对的数量超过了负载因子与数组长度的乘积时，就会触发扩容操作，HashMap 会自动将数组长度扩大一倍，并将原来的键值对重新分配到新的数组中。这样做的目的是为了保证散列表的性能，因为当负载因子过高时，散列表的性能会急剧下降。
二、HashMap的底层数据结构解答：在jdk1.8以前， HashMa采用链表+数组，自Jdk1.8以后，HashMap采用链表+数组+红黑树。在下图中横链(0-15)表中表示数组，竖(1-8)表示链表，在数组长度超过8之后， hashmap将数组自动转为红黑树。

文章插图
HashMapJDK1.8链表和红黑树转化
三、JDK1.8对hash算法和寻址算法如何优化的？1、对Hash值算法的优化static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}有一个key的Hash_1值：
【HashMap的底层数据结构】Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100 h >>> 16 // 表示对该hash值右移16位右移后的结果Hash_2为：
Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111对上述Hash_1和Hash_2的两个值进行异或

Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111=====>: 1111 1111 1111 1111 0000 0101 1000 0011 =====> 转为10进制int值，这个值就是这个key的hash值

hash算法的优化：对每个hash值，在它的低16位中，让高低16位进行异或，让它的低16位同时保持了高低16位的特征，尽量避免一些hash值后续出现冲突，大家可能会进入数组的同一位置。
2、对寻址算法的优化

文章插图
(p = tab[i = (n - 1) & hash]// (n-1) & hash ==> 数组里的一个位置hash & (n-1) 效果是跟hash对n取模是一样的，但是与运算的性能要比hash对n取模要高很多。数组的长度会一直是2的n次方，只要他保持数组长度是2的n次方。

寻址为什么不用取模？

对于上面寻址算法，由于计算机对比取模，与运算会更快。所以为了效率，HashMap 中规定了哈希表长度为 2 的 k 次方，而 2^k-1 转为二进制就是 k 个连续的 1，那么 hash & (k 个连续的 1) 返回的就是 hash 的低 k 个位，该计算结果范围刚好就是 0 到 2^k-1 ，即 0 到 length - 1，跟取模结果一样。
也就是说，哈希表长度 length 为 2 的整次幂时，hash & (length - 1) 的计算结果跟 hash % length 一样，而且效率还更好。

为什么不直接用 hashCode() 而是用它的高 16 位进行异或计算新 hash 值？#

int 类型占 32 位，可以表示 2^32 种数（范围：-2^31 到 2^31-1），而哈希表长度一般不大，在 HashMap 中哈希表的初始化长度是 16（HashMap 中的 DEFAULT_INITIAL_CAPACITY），如果直接用 hashCode 来寻址，那么相当于只有低 4 位有效，其他高位不会有影响。这样假如几个 hashCode 分别是 210、220、2^30，那么寻址结果 index 就会一样而发生冲突，所以哈希表就不均匀分布了。
寻址算法的优化：用与运算替代取模，提升性能。（由于计算机对比取模，与运算会更快）