HashMap 1.7 的底层结构
JDK1.7 中，HashMap 采用位桶 + 链表的实现，即使用链表来处理冲突，同一 hash 值的链表都存储在一个数组中。但是当位于一个桶中的元素较多，即 hash 值相等的元素较多时，通过 key 值依次查找的效率较低。它的数据结构如下
HashMap 大致结构
HashMap 底层数据结构就是一个 Entry 数组，Entry 是 HashMap 的基本组成单元，每个 Entry 中包含一个 key-value 键值对。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
而每个 Entry 中包含 「hash, key ,value」 属性，它是 HashMap 的一个内部类
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;
}
...
}
所以，HashMap 的整体结构就像下面这样
HashMap 1.8 的底层结构
与 JDK 1.7 相比，1.8 在底层结构方面做了一些改变，当每个桶中元素大于 8 的时候，会转变为红黑树，目的就是优化查询效率，JDK 1.8 重写了 resize() 方法。
HashMap 重要属性
「初始容量」
HashMap 的默认初始容量是由 DEFAULT_INITIAL_CAPACITY 属性管理的。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
HashMap 的默认初始容量是 1 << 4 = 16， << 是一个左移操作，它相当于是
「最大容量」
HashMap 的最大容量是
static final int MAXIMUM_CAPACITY = 1 << 30;
这里是不是有个疑问？int 占用四个字节，按说最大容量应该是左移 31 位，为什么 HashMap 最大容量是左移 30 位呢？因为在数值计算中，最高位也就是最左位的位 是代表着符号为，0 -> 正数，1 -> 负数，容量不可能是负数，所以 HashMap 最高位只能移位到 2 ^ 30 次幂。
「默认负载因子」
HashMap 的默认负载因子是
static final float DEFAULT_LOAD_FACTOR = 0.75f;
float 类型所以用 .f 为单位，负载因子是和扩容机制有关，这里大致提一下，后面会细说。扩容机制的原则是当 HashMap 中存储的数量 > HashMap 容量 负载因子时，就会把 HashMap 的容量扩大为原来的二倍。
HashMap 的第一次扩容就在 DEFAULT_INITIAL_CAPACITY DEFAULT_LOAD_FACTOR = 12 时进行。
「树化阈值」
HashMap 的树化阈值是
static final int TREEIFY_THRESHOLD = 8;
在进行添加元素时，当一个桶中存储元素的数量 > 8 时，会自动转换为红黑树（JDK1.8 特性）。
「链表阈值」
HashMap 的链表阈值是
static final int UNTREEIFY_THRESHOLD = 6;
在进行删除元素时，如果一个桶中存储元素数量 < 6 后，会自动转换为链表
「扩容临界值」
static final int MIN_TREEIFY_CAPACITY = 64;
这个值表示的是当桶数组容量小于该值时，优先进行扩容，而不是树化
「节点数组」
HashMap 中的节点数组就是 Entry 数组，它代表的就是 HashMap 中 「数组 + 链表」 数据结构中的数组。
transient Node<K,V>[] table;
Node 数组在第一次使用的时候进行初始化操作，在必要的时候进行 resize，resize 后数组的长度扩容为原来的二倍。
「键值对数量」
在 HashMap 中，使用 size 来表示 HashMap 中键值对的数量。
「修改次数」
在 HashMap 中，使用 modCount 来表示修改次数，主要用于做并发修改 HashMap 时的快速失败 - fail-fast 机制。
「扩容阈值」
在 HashMap 中，使用 threshold 表示扩容的阈值，也就是 初始容量 * 负载因子的值。
threshold 涉及到一个扩容的阈值问题，这个问题是由 tableSizeFor 源码解决的。我们先看一下它的源码再来解释
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
代码中涉及一个运算符 |= ，它表示的是按位或，啥意思呢？你一定知道 「a+=b 的意思是 a=a+b」，那么同理：a |= b 就是 a = a | b，也就是双方都转换为二进制，来进行与操作。如下图所示
我们上面采用了一个比较大的数字进行扩容，由上图可知 2^29 次方的数组经过一系列的或操作后，会算出来结果是 2^30 次方。
所以扩容后的数组长度是原来的 2 倍。
「负载因子」
loadFactor 表示负载因子，它表示的是 HashMap 中的密集程度。
</div>
