关于HashMap，这一篇就够了
目录
HashMap基本结构
HashMap的存储结构是数组+链表+红黑树(JDK1.8+)。数组是HashMap 的主体，链表则是为了解决哈希冲突 (两个对象调用的hashCode方法计算的哈希码一致，导致都需要存放在同一个数组下标下) 而存在的（“拉链法”解决冲突）。
当链表长度大于阈值（默认为 8）并且当前数组的长度大于64时，此链表上的所有数据改为使用红黑树存储。
我们看源码：
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
* 最小链表容量
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
* 最小树容量
*/
static final int MIN_TREEIFY_CAPACITY = 64;当元素不断remove，元素数量小于阈值(默认为6)，会将红黑树再转回链表
// 当元素小于此值时，会从红黑树转成链表
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;为什么使用红黑树？
当链表过长时会严重影响HashMap的性能，而红黑树具有快速增删改查的特点。
因为Map中桶的元素初始化是链表保存的，其查找性能是O(n)，而树结构能将查找性能提升到O(log(n))。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。
为什么链表中元素个数超过8(数组长度大于64)才转为红黑树
如果链表长度大于8，但是数组长度小于64，此时不会直接转为红黑树，和上面回答一样，当链表长度很小的时候，即使遍历，速度也非常快。如果这时就转化成红黑树，红黑树之间保持平衡需要进行左旋，右旋，变色等操作，反而会更慢。
所以综上所述为了提高性能和减少搜索时间，底层在阈值大于8并且数组长度大于64时，链表才转换为红黑树。
HashMap源码中 Implementation notes的部分介绍如下：
This map usually acts as a binned (bucketed) hash table,
but when bins get too large, they are transformed into bins of TreeNodes
each structured similarly to those in java.util.TreeMap.大概含义是当bin变得很大的时候，就会被转换成TreeNodes中的bin，其结构和TreeMap相似，也就是红黑树
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 millionTreeNodes占用空间是普通Nodes的两倍，所以只有当bin包含足够多的节点时才会转成TreeNodes，而是否足够多就是由TREEIFY_THRESHOLD(默认为8)的值决定的。当bin中节点数变少时，又会转成普通的bin。并且我们查看源码的时候发现，链表长度达到8就转成红黑树，当长度降到6就转成普通bin。
这样就解析了为什么不是一开始就将其转换为TreeNodes，而是需要一定节点数才转为TreeNodes，说白了就是trade-off，空间和时间的权衡。
这段内容还说到：当hashCode离散性很好的时候，树型bin用到的概率非常小，因为数据均匀分布在每个bin中，几乎不会有bin中链表长度会达到阈值。但是在随机hashCode下，离散性可能会变差，然而JDK又不能阻止用户实现这种不好的hash算法，因此就可能导致不均匀的数据分布。不过理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布，我们可以看到，一个bin中链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。所以，之所以选择8，是根据概率统计决定的。
至于为什么转化为红黑树的阈值8和转化为链表的阈值6不一样，我想应该是为了避免频繁来回转化导致的效率降低。
关于HashMap的扩容
HashMap的初始容量，默认是16，加载因子默认为0.75。
/**
* The default initial capacity - MUST be a power of two.
* 解释:默认初始容量，必须是2的幂次方 2的4次方=16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
* 解释:最大容量2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
* 解释:当我们未在构造函数中指定大小时，默认使用0.75，也就是说，可以自定义加载因此大小
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The next size value at which to resize (capacity * load factor).
* 阈值，容量x加载因子
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;加载因子主要作用是用来判断什么时候进行扩容，一般情况下，当元素数量超过阈值时便会触发扩容。拿默认值举例，当HashMap中超过16 * 0.75 = 12个元素时，HashMap就会进行扩容，每次扩容的容量都是之前容量的2倍。
虽然可以扩容，但也不能无限扩容，HashMap容量是有上限的，MAXIMUM_CAPACITY(最大容量2的30次方)就是上限值 。如果容量超出了这个数，则不再增长，且阈值会被设置为Integer.MAX_VALUE（ 2的31次方-1，即永远不会超出阈值了）。
若加载因子较大，扩容进行的越晚，发生hash冲突的概率就会增高，查询效率就会变慢。
若加载因子较小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成浪费。
所以应该取个相对平衡合理的值。
个人认为默认0.75是有原因的，扩容后容量都是2的次方，当加载因子为0.75时，容量和加载因子的乘积为整数。
需要注意的几点：
- 空参数的构造函数：实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。如果不是首次put，则不会进行初始化，直接存入数据，然后判断是否需要扩容。
- 有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数设置赋值给阈值（threshold）。第一次调用put方法时，会将阈值赋值给容量，然后让 (阈值 = 容量 x 加载因子 )，因此并不是手动设置了HashMap容量就一定不会触发扩容，当元素超过阈值后一样会进行扩容。
- 如果不是第一次扩容，则容量变为原来的2倍，阈值也变为原来的2倍。（容量和阈值都变为原来的2倍时，负载因子还是不变）
持续更新中。。
参考：
-
为什么链表中元素个数超过8(数组长度大于64)才转为红黑树参考：阿里面试题：为什么Map桶中个数超过8才转为红黑树
-
https://baijiahao.baidu.com/s?id=1708031060871791967&wfr=spider&for=pc
-
https://www.cnblogs.com/dennyzhangdd/p/6745282.html