HashMap底层机制及数据结构
如下图，HashMap底层其实是一个k-v结构的Entry数组，同时为了解决hash冲突问题，也存在链表结构。另外在1.8版本之后，为了优化链表结构，又引入红黑树，使得数据存储更加合理。
| 名词 | 解释 | 补充 |
|---|---|---|
| Entry | 是一种数据结构单元，存储key-value类型，key不可以重复，value可以重复。还有，entry持有一个指向下一个元素的引用，这就构成了链表。 | |
| HashCode | 哈希码并不是完全唯一的，它是一种算法，让同一个类的对象按照自己不同的特征尽量的有不同的哈希码，但不表示不同的对象哈希码完全不同。 | |
| 红黑树 | 是一种自平衡二叉查找树，是对链表结构的优化，是一种在更删改查的效率方面更为均衡的数据结构。 | |
| Hash冲突 | 当数据经过hashcode得出来的hash值一样，在entry中就会映射同一个key值对应的index位置，就会出现”冲突“。但是通过链表结构可以解决这个问题，当一个index有多个数据时，就会将数据通过链表的方式存储，但是链表长度过长会削弱链表结构的优势。jdk1.8之后为了解决这个问题，将链表结构优化成红黑树。 | |
| 扩容（负载）因子 | 在jdk1.7中，默认为0.75，是决定是否扩容的一个参考因素，但并非达到扩容阈值threshold（数组长度*负载因子）就会扩容。扩容条件是(size >= threshold) && (null != table[bucketIndex])，表示不但要满足已有键值对数量达到扩容阀值，还得确定数组位置已存在数据，发生hash冲突。反过来说就是，如果数组位置是空的，没有hash冲突，该位置可用，那么即使达到了扩容阀值也不会扩容。也就是说，未达到阀值或未发生hash冲突时是不会扩容的。 |
几点介绍：
-
jdk1.8之前，hashmap的默认数组长度为16，扩容机制如下
（1）、就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。
（2）、当然也有可能存储更多值（超多16个值，最多可以存26个值）都还没有扩容。原理：前11个值全部hash碰撞，存到数组的同一个位置（这时元素个数小于阈值12，不会扩容），后面所有存入的15个值全部分散到数组剩下的15个位置（这时元素个数大于等于阈值，但是每次存入的元素并没有发生hash碰撞，所以不会扩容），前面11+15=26，所以在存入第27个值的时候才同时满足上面两个条件，这时候才会发生扩容现象。
-
jdk1.8及其以后，hashmap的默认数组长度为64，扩容机制如下
（1）、因为扩容比较消耗资源，所以应该尽量避免。但是在链表结构中，如果链表长度过长，会极大影响数据的查改效率，因此引入性能更加均衡的红黑树。
（2）、扩大数组长度也是为了减少扩容机制的触发，其负载因子与jdk1.8之前一样为0.75。但是不同于jdk1. 7，放入key之前先扩容，放入后不重新判断是否扩容。达到阀值且hash冲突时才扩容。不发生hash冲突，可超过阀值。因此jdk1.7最多存个数：threshold+table.length-1，如介绍1。jdk1.8中，放入key之后再判断是否达到阈值，超过阈值就扩容，与是否hash冲突无关，因此最多存放key个数与阀值相同。
-
jdk1.8中hash“冲突”时的解决方案
（1）、如果冲突数量小于8，则是以链表方式解决冲突。
（2）、而当冲突大于等于8时，就会将冲突的Entry转换为红黑树进行存储。
（3）、而又当数量小于6时，则又转化为链表存储。