HashMap的存储结构
说到这里大家都能脱口而出存储的是键值对，可是键值对是怎么存储的很多人都不太了解。
我们需要对HashMap内部三种数据结构进行了解。
- 普通节点（链表）
- 红黑树节点
- 节点数组（桶）
普通节点
HashMap中维护的这个内部类实现了Entry接口，其实就是我们所熟悉的键值对，并且由于该类里面有指向下一个节点的引用，所以可以把这个节点理解为一个链表
// 这个节点就是我们使用的键值对
static class Node<K,V> implements Map.Entry<K,V> {
// 键值对key值的hash(这里面的hash是经过处理过的)
final int hash;
// 键值对的key值
final K key;
// 键值对的value值
V value;
// 下一个节点
Node<K,V> next;
}
红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
// 父节点
TreeNode<K,V> parent; // red-black tree links
// 左孩子
TreeNode<K,V> left;
// 又孩子
TreeNode<K,V> right;
// 删除时取消连接用的
TreeNode<K,V> prev; // needed to unlink next upon deletion
// 标识是红节点还是黑节点
boolean red;
}
节点数组
该数组里面存放的是普通节点的头结点，或者红黑树的根节点。
因为TreeNode继承于LinkedHashMap.Entry，而LinkedHashMap.Entry继承于HashMap.Node
总结
- HashMap内部维护了一个桶，桶内存放的是若干链表及红黑树。
HashMap的存操作
该操作可以分为下面几个步骤：
- 计算key值hash,判断应该存放在桶内哪个位置
- 将该键值对放在对应位置链表的末尾
- 判断该链表长度大于等于8时，将该链表转化为红黑树
- 判断桶内链表及红黑树的个数和是否大于当前桶的大小*加载因子（默认0.75）
- 大于则rehash扩容桶的大小
下面我们针对这几个步骤了解一下里面的处理逻辑
计算key值hash
下面是计算hash的源码
static final int hash(Object key) {
int h;
// 从这里可以说明hashmap的key值可以为null，为null的hash默认为0
// hashtable取hash是用的下面两句话，这也解释了为什么hashtablekey值不能为空
// Entry<?,?> tab[] = table;
// int hash = key.hashCode();
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以分为下面几个步骤
- 计算key的hash值
- 将hash值向右无符号位移16位
- 原hash与右移过的hash位异或运算
第一步到第三步称为hashmap中的扰动函数，为了就是减少hash碰撞
为什么要右移16位
结论：因为右移16位可以让高位参与运算。
原理：
- hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。
- int类型为2进制32位的，右移16位看好是的前16位高半区设0，高半区设到后16位低半区
为什么要原hash与右移过的hash位异或运算
结论：使得低半区同时具有高半区和低半区的特性。
原理：
- 位移过后低半区的值不在保留，所有只有高半区的特性。
- 只有经过异或运算才可以加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
判断应该存放在桶内哪个位置
HashMap是通过将经过扰动算法计算出的hash值与当前桶的大小减一再进行与运算得出来的一个数组下标
为什么要与运算
其实这个没啥原理啥的。。。就因为内存不够大，上面也提到过hashcode是个表值范围是从-2147483648到2147483648。前后加起来大概40亿的映射空间如果你内存足够大能发下40亿长度的数组，鬼才做扰动。所以只能尽可能的减少碰撞，出现碰撞再转化为链表或者红黑树。
顺便说一下，这也正好解释了为什么HashMap的数组长度要取2的整次幂。因为这样（数组长度-1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。
将该键值对放在对应位置链表的末尾
在1.8之前都是从头部开始插入的，但是从头部开始插入，会使得扩容时该表链表的位置在并发情况下会形成环，所以从1.8之后改成了从尾部开始。
判断该链表长度大于等于8时，将该链表转化为红黑树
因为链表如果太长的话会会降低查询效率，因为链表平均查找长度为n/2。
红黑树平均查找长度为logn。
所以如果链表长度过长的话为了增加查询效率则需要转化为红黑树。而选择8这个阈值是因为
log8 = 3。 8/2 =4。超过8红黑树的查询效率就要高于数组。
并且红黑树还需要左旋右旋，所以节点的少的时候链表更优。
判断是否需要扩容
当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过160.75=12的时候，就把数组的大小扩展为216=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.751000 < 1000, 也就是说为了让0.75 * size>1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题。
转载：https://blog.csdn.net/baidu_29609961/article/details/106114017