一、初窥 HashMap
HashMap 是应用更广泛的 哈希表 实现，而且大部分情况下，都能在常数时间性能的情况下进行 put 和 get 操作。要掌握 HashMap，主要从如下几点来把握：
- jdk1.7 中底层是由数组（也有叫做“位桶”的）+ 链表实现；jdk1.8 中底层是由数组 + 链表/红黑树实现
- 可以存储 null 键和 null 值，线程不安全。在 HashMap 中，null 可以作为键，这样的键只有一个，但可以有一个或多个键所对应的值为 null。
当get()方法返回null值时，即可以表示HashMap中没有该key，也可以表示该key所对应的value为null。因此，在 HashMap 中不能由 get()方法来判断 HashMap 中是否存在某个 key，应该用containsKey()方法来判断。而在 Hashtable 中，无论是 key 还是 value 都不能为 null。 - 初始 size 为 16，扩容：newsize = oldsize*2，
size一定为2的n次幂 - 扩容针对整个 Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
- 插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
- 当 Map 中元素总数超过 Entry 数组的 75%，触发扩容操作，为了减少链表长度，元素分配更均匀
- 1.7 中是先扩容后插入新值的，1.8 中是先插值再扩容
为什么说HashMap是线程不安全的？ 在接近临界点时，若此时两个或者多个线程进行 put 操作，都会进行 resize（扩容）和 reHash（为 key 重新计算所在位置），而 reHash 在并发的情况下可能会形成 链表环。总结来说就是在多线程环境下，使用 HashMap 进行 put 操作会引起死循环，导致 CPU 利用率接近 100%，所以在并发情况下不能使用 HashMap。为什么在并发执行 put 操作会引起死循环？是因为多线程会导致 HashMap 的 Entry 链表形成环形数据结构，一旦形成环形数据结构，Entry 的 next 节点永远不为空，就会产生死循环获取 Entry。jdk1.7 的情况下，并发扩容时容易形成链表环，此情况在 1.8 时就好太多太多了。因为在 1.8 中当链表长度大于阈值（默认长度为 8）时，链表会被改成树形（红黑树）结构。
二、jdk1.7 中 HashMap 的实现
HashMap 底层维护的是数组 + 链表，我们可以通过一小段源码来看看：
/**
* The default initial capacity - MUST be a power of two.
* 即 默认初始大小，值为16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 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 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.
* 大致意思就是说hash冲突默认采用单链表存储，当单链表节点个数大于8时，会转化为红黑树存储
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 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.
* hash冲突默认采用单链表存储，当单链表节点个数大于8时，会转化
为红黑树存储。
* 当红黑树中节点少于6时，则转化为单链表存储
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 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.
* hash冲突默认采用单链表存储，当单链表节点个数大于8时，会转化为红黑树存储。
* 但是有一个前提：要求数组长度大于64，否则不会进行转化
*/
static final int MIN_TREEIFY_CAPACITY = 64;
通过以上代码可以看出初始容量（16）、负载因子以及对数组的说明。数组中的每一个元素其实就是 Entry<K,V>[] table，Map 中的 key 和 value 就是以 Entry 的形式存储的。Entry 包含四个属性：key、value、hash 值和用于单向链表的 next。关于 Entry<K,V> 的具体定义参看如下源码：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
HashMap 的初始值要考虑负载因子:
- 哈希冲突：若干 Key 的哈希值按数组大小取模后，如果落在同一个数组下标上，将组成一条 Entry 链，对 Key 的查找需要遍历 Entry 链上的每个元素执行 equals()比较。
- 加载因子：为了降低哈希冲突的概率，默认当 HashMap 中的键值对达到数组大小的 75% 时，即会触发扩容。因此，如果预估容量是 100，即需要设定 100/0.75＝134 的数组大小。
- 空间换时间：如果希望加快 Key 查找的时间，还可以进一步降低加载因子，加大初始大小，以降低哈希冲突的概率。
HashMap 和 Hashtable 都是用 hash 算法来决定其元素的存储，因此 HashMap 和 Hashtable 的 hash 表包含如下属性： - 容量（capacity）：hash 表中桶的数量
- 初始化容量（initial capacity）：创建 hash 表时桶的数量，HashMap 允许在构造器中指定初始化容量
- 尺寸（size）：当前 hash 表中记录的数量
- 负载因子（load factor）：负载因子等于“size/capacity”。负载因子为 0，表示空的 hash 表，0.5 表示半满的散列表，依此类推。轻负载的散列表具有冲突少、适宜插入与查询的特点（但是使用 Iterator 迭代元素时比较慢）
除此之外，hash 表里还有一个“负载极限”，“负载极限”是一个 0～1 的数值，“负载极限”决定了 hash 表的最大填满程度。当 hash 表中的负载因子达到指定的“负载极限”时，hash 表会自动成倍地增加容量（桶的数量），并将原有的对象重新分配，放入新的桶内，这称为 rehashing。
HashMap 和 Hashtable 的构造器允许指定一个负载极限，HashMap 和 Hashtable 默认的“负载极限”为 0.75，这表明当该 hash 表的 3/4 已经被填满时，hash 表会发生 rehashing。
“负载极限”的默认值（0.75）是时间和空间成本上的一种折中： 较高的“负载极限”可以降低 hash 表所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的操作（HashMap 的 get()与 put()方法都要用到查询）较低的“负载极限”会提高查询数据的性能，但会增加 hash 表所占用的内存开销
程序猿可以根据实际情况来调整“负载极限”值。
当向 HashMap 中 put 一对键值时，它会根据 key 的 hashCode 值计算出一个位置， 该位置就是此对象准备往数组中存放的位置。 该计算过程参看如下代码：
transient int hashSeed = 0;
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
通过 hash 计算出来的值将会使用 indexFor 方法找到它应该所在的 table 下标。当两个 key 通过 hashCode 计算相同时，则发生了 hash 冲突(碰撞)，HashMap 解决 hash 冲突的方式是用链表(拉链法)。当发生 hash 冲突时，则将存放在数组中的 Entry 设置为新值的 next（这里要注意的是，比如 A 和 B 都 hash 后都映射到下标 i 中，之前已经有 A 了，当 map.put(B)时，将 B 放到下标 i 中，A 则为 B 的 next，所以新值存放在数组中，旧值在新值的链表上）。即将新值作为此链表的头节点，为什么要这样操作？据说后插入的 Entry 被查找的可能性更大（因为 get 查询的时候会遍历整个链表），此处有待考究，如果有哪位大神知道，请留言告知。有一种说法就是链表查找复杂度高，可插入和删除性能高，如果将新值插在末尾，就需要先经过一轮遍历，这个时间复杂度高，开销大，如果是插在头结点，省去了遍历的开销，还发挥了链表插入性能高的优势。
如果该位置没有对象存在，就将此对象直接放进数组当中；如果该位置已经有对象存在了，则顺着此存在的对象的链开始寻找(为了判断是否值相同，map 不允许 <key,value> 键值对重复)， 如果此链上有对象的话，再去使用 equals 方法进行比较，如果对此链上的每个对象的 equals 方法比较都为 false，则将该对象放到数组当中，然后将数组中该位置以前存在的那个对象链接到此对象的后面。
添加节点到链表中：找到数组下标后，会先进行 key 判重，如果没有重复，就准备将新值放入到链表的表头。
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果当前 HashMap 大小已经达到了阈值，并且新值要插入的数组位置已经有元素了，那么要扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容
resize(2 * table.length);
// 扩容以后，重新计算 hash 值
hash = (null != key) ? hash(key) : 0;
// 重新计算扩容后的新的下标
bucketIndex = indexFor(hash, table.length);
}
// 往下看
createEntry(hash, key, value, bucketIndex);
}
// 这个很简单，其实就是将新值放到链表的表头，然后 size++
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
这个方法的主要逻辑就是先判断是否需要扩容，需要带的话先扩容，然后再将这个新的数据插入到扩容后的数组的相应位置处的链表的表头。
扩容就是用一个新的大数组替换原来的小数组，并将原来数组中的值迁移到新的数组中。由于是双倍扩容，迁移过程中，会将原来 table[i]中的链表的所有节点，分拆到新的数组的 newTable[i]和 newTable[i+oldLength]位置上。如原来数组长度是 16，那么扩容后，原来 table[0]处的链表中的所有元素会被分配到新数组中 newTable[0]和 newTable[16]这两个位置。扩容期间，由于会新建一个新的空数组，并且用旧的项填充到这个新的数组中去。所以，在这个填充的过程中，如果有线程获取值，很可能会取到 null 值，而不是我们所希望的、原来添加的值。
图中，左边部分即代表哈希表，也称为哈希数组（默认数组大小是 16，每对 key-value 键值对其实是存在 map 的内部类 entry 里的），数组的每个元素都是一个单链表的 头节点，跟着的蓝色链表是用来解决冲突的，如果不同的 key 映射到了数组的同一位置处，就将其放入单链表中。
前面说过 HashMap 的 key 是允许为 null 的，当出现这种情况时，会放到 table[0]中。
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
当 size>=threshold（ threshold 等于“容量*负载因子”）时，会发生 扩容。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
特别提示：jdk1.7中resize，只有当 size>=threshold并且 table中的那个槽中已经有Entry时，才会发生resize。即有可能虽然 size>=threshold，但是必须等到相应的槽至少有一个 Entry 时，才会扩容,可以通过上面的代码看到每次 resize 都会扩大一倍容量（2 * table.length）。
三、jdk1.8 中 HashMap 的实现
在 jdk1.8 中 HashMap 的内部结构可以看作是数组(Node<K,V>[] table)和链表的复合结构，数组被分为一个个桶（bucket），通过哈希值决定了键值对在这个数组中的寻址（哈希值相同的键值对，则以链表形式存储。有一点需要注意，如果链表大小超过阈值（TREEIFY_THRESHOLD,8），图中的链表就会被改造为树形（红黑树）结构。
transient Node<K,V>[] table;
Entry 的名字变成了 Node，原因是和红黑树的实现 TreeNode 相关联。1.8 与 1.7 最大的不同就是利用了红黑树，即由数组 + 链表（或红黑树）组成。
在分析 jdk1.7 中 HashMap 的 hash 冲突时，不知大家是否有个疑问就是万一发生碰撞的节点非常多怎么办？如果说成百上千个节点在 hash 时发生碰撞，存储一个链表中，那么如果要查找其中一个节点，那就不可避免的花费 O(N)的查找时间，这将是多么大的性能损失。这个问题终于在 JDK1.8 中得到了解决，在最坏的情况下，链表查找的时间复杂度为 O(n),而红黑树一直是 O(logn),这样会提高 HashMap 的效率。
dk1.7 中 HashMap 采用的是位桶 + 链表的方式，即我们常说的散列链表的方式，而 jdk1.8 中采用的是位桶 + 链表/红黑树的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阀值的时候，这个链表就将转换成红黑树。
jdk1.8 中，当同一个 hash 值的节点数不小于 8 时，将不再以单链表的形式存储了，会被调整成一颗红黑树（上图中 null 节点没画）。这就是 jdk1.7 与 jdk1.8 中 HashMap 实现的最大区别。
HashMap 根据链地址法（拉链法）来解决冲突，在 jdk1.8 中，如果 链表长度大于8且节点数组长度大于64的时候，就把链表下所有的节点转为红黑树。
通过分析 put 方法的源码，可以让这种区别更直观：
static final int TREEIFY_THRESHOLD = 8;
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
//如果当前map中无数据，执行resize方法。并且返回n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果要插入的键值对要存放的这个位置刚好没有元素，那么把他封装成Node对象，放在这个位置上即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//否则的话，说明这上面有元素
else {
Node<K,V> e; K k;
//如果这个元素的key与要插入的一样，那么就替换一下。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//1.如果当前节点是TreeNode类型的数据，执行putTreeVal方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//还是遍历这条链子上的数据，跟jdk7没什么区别
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//2.完成了操作后多做了一件事情，判断，并且可能执行treeifyBin方法
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) //true || --
e.value = value;
//3.
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判断阈值，决定是否扩容
if (++size > threshold)
resize();
//4.
afterNodeInsertion(evict);
return null;
}
以上代码中的特别之处如下：
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
treeifyBin() 就是将链表转换成红黑树。
树化操作的过程有点复杂，可以结合源码来看看。将原本的单链表转化为双向链表，再遍历这个双向链表转化为红黑树。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//树形化还有一个要求就是数组长度必须大于等于64，否则继续采用扩容策略
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;//hd指向首节点，tl指向尾节点
do {
TreeNode<K,V> p = replacementTreeNode(e, null);//将链表节点转化为红黑树节点
if (tl == null) // 如果尾节点为空，说明还没有首节点
hd = p; // 当前节点作为首节点
else { // 尾节点不为空，构造一个双向链表结构，将当前节点追加到双向链表的末尾
p.prev = tl; // 当前树节点的前一个节点指向尾节点
tl.next = p; // 尾节点的后一个节点指向当前节点
}
tl = p; // 把当前节点设为尾节点
} while ((e = e.next) != null); // 继续遍历单链表
//将原本的单链表转化为一个节点类型为TreeNode的双向链表
if ((tab[index] = hd) != null) // 把转换后的双向链表，替换数组原来位置上的单向链表
hd.treeify(tab); // 将当前双向链表树形化
}
}
大家要特别注意一点，树化有个要求就是数组长度必须大于等于 MIN_TREEIFY_CAPACITY（64），否则继续采用扩容策略。
总的来说，HashMap 默认采用数组 + 单链表方式存储元素，当元素出现哈希冲突时，会存储到该位置的单链表中。但是单链表不会一直增加元素，当元素个数超过 8 个时，会尝试将单链表转化为红黑树存储。但是在转化前，会再判断一次当前数组的长度，只有数组长度大于 64 才处理。否则，进行扩容操作。
将双向链表转化为红黑树的实现：
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null; // 定义红黑树的根节点
for (TreeNode<K,V> x = this, next; x != null; x = next) { // 从TreeNode双向链表的头节点开始逐个遍历
next = (TreeNode<K,V>)x.next; // 头节点的后继节点
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x; // 头节点作为红黑树的根，设置为黑色
}
else { // 红黑树存在根节点
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) { // 从根开始遍历整个红黑树
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) // 当前红黑树节点p的hash值大于双向链表节点x的哈希值
dir = -1;
else if (ph < h) // 当前红黑树节点的hash值小于双向链表节点x的哈希值
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) // 当前红黑树节点的hash值等于双向链表节点x的哈希值，则如果key值采用比较器一致则比较key值
dir = tieBreakOrder(k, pk); //如果key值也一致则比较className和identityHashCode
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) { // 如果当前红黑树节点p是叶子节点，那么双向链表节点x就找到了插入的位置
x.parent = xp;
if (dir <= 0) //根据dir的值，插入到p的左孩子或者右孩子
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x); //红黑树中插入元素，需要进行平衡调整(过程和TreeMap调整逻辑一模一样)
break;
}
}
}
}
//将TreeNode双向链表转化为红黑树结构之后，由于红黑树是基于根节点进行查找，所以必须将红黑树的根节点作为数组当前位置的元素
moveRootToFront(tab, root);
}
然后将红黑树的根节点移动端数组的索引所在位置上：
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash; //找到红黑树根节点在数组中的位置
TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; //获取当前数组中该位置的元素
if (root != first) { //红黑树根节点不是数组当前位置的元素
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null) //将红黑树根节点前后节点相连
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null) //将数组当前位置的元素，作为红黑树根节点的后继节点
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
putVal 方法处理的逻辑比较多，包括初始化、扩容、树化，近乎在这个方法中都能体现，针对源码简单讲解下几个关键点：
- 如果 Node<K,V>[] table 是 null，resize 方法会负责初始化，即如下代码：
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
- resize 方法兼顾两个职责，创建初始存储表格，或者在容量不满足需求的时候，进行扩容（resize）。
在放置新的键值对的过程中，如果发生下面条件，就会发生扩容。
if (++size > threshold)
resize();
- 具体键值对在哈希表中的位置（数组 index）取决于下面的位运算：
i = (n - 1) & hash
仔细观察哈希值的源头，会发现它并不是 key 本身的 hashCode，而是来自于 HashMap 内部的另一个 hash 方法。为什么这里需要将高位数据移位到低位进行异或运算呢？ 这是因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的，那么这种处理就可以有效避免类似情况下的哈希碰撞。
在 jdk1.8 中取消了 indefFor()方法，直接用(tab.length-1)&hash，所以看到这个，代表的就是数组的下角标。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
为什么 HashMap 为什么要树化？
之前在极客时间的专栏里看到过一个解释。本质上这是个安全问题。因为在元素放置过程中，如果一个对象哈希冲突，都被放置到同一个桶里，则会形成一个链表，我们知道链表查询是线性的，会严重影响存取的性能。而在现实世界，构造哈希冲突的数据并不是非常复杂的事情，恶意代码就可以利用这些数据大量与服务器端交互，导致服务器端 CPU 大量占用，这就构成了哈希碰撞拒绝服务攻击，国内一线互联网公司就发生过类似攻击事件。
用哈希碰撞发起拒绝服务攻击(DOS，Denial-Of-Service attack),常见的场景是攻击者可以事先构造大量相同哈希值的数据，然后以 JSON 数据的形式发送给服务器，服务器端在将其构建成为 Java 对象过程中，通常以 Hashtable 或 HashMap 等形式存储，哈希碰撞将导致哈希表发生严重退化，算法复杂度可能上升一个数据级，进而耗费大量 CPU 资源。
为什么要将链表中转红黑树的阈值设为 8？
我们可以这么来看，当链表长度大于或等于阈值（默认为 8）的时候，如果同时还满足容量大于或等于 MIN_TREEIFY_CAPACITY（默认为 64）的要求，就会把链表转换为红黑树。同样，后续如果由于删除或者其他原因调整了大小，当红黑树的节点小于或等于 6 个以后，又会恢复为链表形态。每次遍历一个链表，平均查找的时间复杂度是 O(n)，n 是链表的长度。红黑树有和链表不一样的查找性能，由于红黑树有自平衡的特点，可以防止不平衡情况的发生，所以可以始终将查找的时间复杂度控制在 O(log(n))。最初链表还不是很长，所以可能 O(n) 和 O(log(n)) 的区别不大，但是如果链表越来越长，那么这种区别便会有所体现。所以为了提升查找性能，需要把链表转化为红黑树的形式。
还要注意很重要的一点，单个 TreeNode 需要占用的空间大约是普通 Node 的两倍，所以只有当包含足够多的 Nodes 时才会转成 TreeNodes，而是否足够多就是由 TREEIFY_THRESHOLD 的值决定的。而当桶中节点数由于移除或者 resize 变少后，又会变回普通的链表的形式，以便节省空间。
默认是链表长度达到 8 就转成红黑树，而当长度降到 6 就转换回去，这体现了 时间和空间平衡的思想，最开始使用链表的时候，空间占用是比较少的，而且由于链表短，所以查询时间也没有太大的问题。可是当链表越来越长，需要用红黑树的形式来保证查询的效率。
在理想情况下，链表长度符合 泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，是最理想的值。
事实上，链表长度超过 8 就转为红黑树的设计，更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长，从而导致查询效率低，而此时转为红黑树更多的是一种保底策略，用来保证极端情况下查询的效率。
通常如果 hash 算法正常的话，那么链表的长度也不会很长，那么红黑树也不会带来明显的查询时间上的优势，反而会增加空间负担。所以通常情况下，并没有必要转为红黑树，所以就选择了概率非常小，小于千万分之一概率，也就是长度为 8 的概率，把长度 8 作为转化的默认阈值。
如果开发中发现 HashMap 内部出现了红黑树的结构，那可能是我们的哈希算法出了问题，所以需要选用合适的 hashCode 方法，以便减少冲突。
四、分析 Hashtable、HashMap、TreeMap 的区别
HashMap是继承自AbstractMap类，而HashTable是继承自Dictionary类。不过它们都同时实现了 map、Cloneable（可复制）、Serializable（可序列化）这三个接口。存储的内容是基于 key-value 的键值对映射，不能有重复的 key，而且一个 key 只能映射一个 value。HashSet 底层就是基于 HashMap 实现的。- Hashtable 的 key、value 都不能为 null；HashMap 的 key、value 可以为 null，不过只能有一个 key 为 null，但可以有多个 null 的 value；TreeMap 键、值都不能为 null。
- Hashtable、HashMap 具有无序特性。TreeMap 是利用
红黑树实现的（树中的每个节点的值都会大于或等于它的左子树中的所有节点的值，并且小于或等于它的右子树中的所有节点的值），实现了 SortMap 接口，能够对保存的记录根据键进行排序。所以一般需求排序的情况下首选 TreeMap，默认按键的升序排序（深度优先搜索），也可以自定义实现 Comparator 接口实现排序方式。
一般情况下我们选用 HashMap，因为 HashMap 的键值对在取出时是随机的，其依据键的 hashCode 和键的 equals 方法存取数据，具有很快的访问速度，所以在 Map 中插入、删除及索引元素时其是效率最高的实现。而 TreeMap 的键值对在取出时是排过序的，所以效率会低点。
TreeMap 是基于红黑树的一种提供顺序访问的 Map，与 HashMap 不同的是它的 get、put、remove 之类操作都是 o(log(n))的时间复杂度，具体顺序可以由指定的 Comparator 来决定，或者根据键的自然顺序来判断。
对 HashMap 做下总结：
HashMap 基于哈希散列表实现 ，可以实现对数据的读写。将键值对传递给 put 方法时，它调用键对象的 hashCode()方法来计算 hashCode，然后找到相应的 bucket 位置（即数组）来储存值对象。当获取对象时，通过键对象的 equals()方法找到正确的键值对，然后返回值对象。HashMap 使用链表来解决 hash 冲突问题，当发生冲突了，对象将会储存在链表的头节点中。HashMap 在每个链表节点中储存键值对对象，当两个不同的键对象的 hashCode 相同时，它们会储存在同一个 bucket 位置的链表中，如果链表大小超过阈值（TREEIFY_THRESHOLD,8），链表就会被改造为树形结构。
有个问题要特别声明下：
- HashMap 在 jdk1.7 中采用表头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题。
- 在 jdk1.8 中采用的是尾部插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
我们可以简单列下 HashMap 在 1.7 和 1.8 之间的变化：
- 1.7 中采用数组 + 链表，1.8 采用的是数组 + 链表/红黑树，即在 1.7 中链表长度超过一定长度后就改成红黑树存储。
- 1.7 扩容时需要重新计算哈希值和索引位置，1.8 并不重新计算哈希值，巧妙地采用和扩容后容量进行&操作来计算新的索引位置。
- 1.7 是采用表头插入法插入链表，1.8 采用的是尾部插入法。
- 在 1.7 中采用表头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题；在 1.8 中采用尾部插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于