Java集合之HashMap存储

要理解HashMap说简单简单，说难也难，简单来说，你只要知道以下属性的含义

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;
    transient Node<K,V>[] table;

说难，你得理解这些属性值设计的合理性
我们先从属性的含义了解下吧
DEFAULT_INITIAL_CAPACITY： table的初始容量，也就是默认会创建 16 个箱子，箱子的个数不能太多或太少。如果太少，很容易触发扩容，如果太多，遍历哈希表会比较慢。
MAXIMUM_CAPACITY ：数组的最大长度
DEFAULT_LOAD_FACTOR ：默认的负载因子。因此初始情况下，当键值对的数量大于 16 * 0.75 = 12 时，就会触发扩容。
TREEIFY_THRESHOLD: 如果哈希函数不合理，即使扩容也无法减少箱子中链表的长度，因此 Java 的处理方案是当链表太长时，转换成红黑树。这个值表示当某个箱子中，链表长度大于 8 时，有可能会转化成树。
UNTREEIFY_THRESHOLD: 在哈希表扩容时，如果发现链表长度小于 6，则会由树重新退化为链表。
MIN_TREEIFY_CAPACITY: 在转变成树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
有了以上概念，我们就可以来探讨探讨以上属性值设计的合理性；
DEFAULT_LOAD_FACTOR负载因子为什么是0.75
通常，加载因子需要在时间和空间成本上寻求一种折衷。加载因子过高，例如为1，虽然减少了空间开销，提高了空间利用率，但同时也增加了查询时间成本；加载因子过低，例如0.5，虽然可以减少查询时间成本，但是空间利用率很低，同时提高了rehash操作的次数。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少rehash操作次数，所以，一般在使用HashMap时建议根据预估值设置初始容量，减少扩容操作。
选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择，至于为什么不选择0.5或0.8，笔者没有找到官方的直接说明，在HashMap的源码注释中也只是说是一种折中的选择
TREEIFY_THRESHOLD 为什么大于等于8之后链表会转红黑树
HashMap存储结构是数组+链表或者数组+红黑树及数组单元里面存的可能是个链表也可能是个红黑树
HashMap在JDK1.8及以后的版本中引入了红黑树结构

image.png

HashMap中的注释有一段Implementation notes，大致说明了我们的问题，我们来看看。

Tree bins (i.e., bins whose elements are all TreeNodes) are ordered primarily by hashCode, but in the case of ties, if two elements are of the same “class C implements Comparable<C>”, type then their compareTo method is used for ordering. (We conservatively check generic types via reflection to validate this – see method comparableClassFor). The added complexity of tree bins is worthwhile in providing worst-case O(log n) operations when keys either have distinct hashes or are orderable, Thus, performance degrades gracefully under accidental or malicious usages in which hashCode() methods return values that are poorly distributed, as well as those in which many keys share a hashCode, so long as they are also Comparable. (If neither of these apply, we may waste about a factor of two in time and space compared to taking no precautions. But the only known cases stem from poor user programming practices that are already so slow that this makes little difference.)
这一段说明了为什么要使用红黑树:

红黑树的插入、删除和遍历的最坏时间复杂度都是log(n)，因此，在意外或者恶意使用导致hashCode()方法返回值的分布很糟糕，以及在那些许多key共享一个hashCode的情况下，只要Key具有可比性，性能的下降将会是"优雅"的。(如果这两种方法都不适用，与不采取预防措施相比，我们可能会浪费大约两倍的时间和空间。但目前所知的唯一案例来自于糟糕的用户编程实践，这些实践已经非常缓慢，以至于没有什么区别。)

接下来看另外一段：

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:

0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
这一段解释了我们的问题：

由于TreeNodes的大小大约是常规节点的两倍，因此我们仅在容器包含足够的节点以保证使用时才使用它们（参见 TREEIFY_THRESHOLD 值）。当它们变得太小（由于移除或调整大小）时，它们会被转换回普通的bin。理想情况下，在随机哈希代码下，bin中的节点频率遵循泊松分布，下面就是list size k 的频率表。
结论：
由频率表可以看出，桶的长度超过8的概率是非常小的，结合上一段提到的恶意使用，我想，加入红黑树的其中一个主要原因是为了防止恶意使用带来的性能骤降。作者根据概率统计而选择了8作为阀值，由此可见，将阈值定为8这个选择是非常严谨和科学的一个决定。
UNTREEIFY_THRESHOLD 为什么为6的时候红黑树要转链表
若桶中链表元素个数大于等于8时，链表转换成树结构；若桶中链表元素个数小于等于6时，树结构还原成链表。因为红黑树的平均查找长度是log(n)，长度为8的时候，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，这才有转换为树的必要。链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
还有选择6和8，中间有个差值7可以有效防止链表和树频繁转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
JDK1.8 HashMap 散列算法的优化
可以先参考：
https://www.jianshu.com/p/e1d3ba0c733a
https://blog.csdn.net/qq_42034205/article/details/90384772
附

Java集合关系图.png