HashMap
HashMap 的内存结构和原理，以及线程安全都是面试的热点问题，HashMap 大家并不陌生，它是用于映射(键值对)处理的数据类型。随着 JDK 版本的不断升级更新，JDK 1.8 引入了红黑树的数据结构对 HashMap 底层实现进行了优化。我们先看一下 JDK 1.7 版本的 HashMap ，然后在看一下 JDK 1.8 版本的 HashMap 有何变化。
一 Java 7 HashMap
1.1 HashMap 的数据结构
数组的优缺点：通过数组下标索引能快速查找到目标元素，但是在数组中插入(除末尾插入情况)或者删除元素(除末尾删除)需要移动数组元素，速度比较慢。
链表的优缺点：在链表中查找一个元素需要遍历链表去查找指定元素，速度比较慢，而插入和删除可以在常量时间内完成操作。因此链表适合快速插入和删除的场景，不利于查找元素。
HashMap 由 Entry 数组 + 链表 组成，每个实体嵌套类 Entry 的实例，Entry 中包含四个属性：key，value，hash 值和用于单向链表的 next ，如下图所示。
1.2 数组初始化
在第一个元素插入 HashMap 的时候做一次数组初始化，先确定初始数组的大小，并且计算数组扩容的阈值。
capacity：当前数组容量，始终是2^n，可以扩容，扩容或数组大小为当前的 2 倍(因为散列表的 hash 算法是根据移位来计算的，计算机是 2 进制的，移位也只能是 *2 或 /2 ，因此扩容要符合这个标准，否则会造成没必要的浪费)。
threshold：扩容的阈值，等于 capacity * loadFactor 。
loadFactor：负载因子，默认为 0.75 。
private void inflateTable(int toSize) {
// 找出一个 2^n 的数，使其不小于给出的数字，保证数组大小一定是 2 的 n 次方。
int capacity = roundUpToPowerOf2(toSize);
// 计算扩容阈值：capacity * loadFactor
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 算是初始化数组吧
table = new Entry[capacity];
initHashSeedAsNeeded(capacity); //ignore
}1.3 计算具体数组位置
如上图，在一个长度为 16 的数组中，每个元素存储的都是一个链表的头节点。这些元素按什么规则存储在数组中呢，一般是通过 hash (key) % len 获得，即元素 key 的哈希值对数组长度取模得到。在下图的哈希表中，40%16=8，56%16=8，72%16=8，所以 40、56、72 都存储在数组下标为 8 的位置中。
static int indexFor(int hash, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return hash & (length-1);
}1.4 添加节点到链表中
找到数组下标后，会先进行 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++;
}1.5 数组扩容
前面我们看到在插入新值的时候，如果当前的 size 已经达到了阈值，并且要插入的数组位置上已经有元素，那么就会触发扩容，扩容后，数组大小变为原来的 2 倍，并将原来数组中的值迁移到新的数组中去。由于是双倍扩容，迁移过程中，会将原来 table[i] 中的链表的所有节点，分拆到新的数组的 newTable[i] 和 newTable[i + oldLength] 位置上。如原来数组长度是 16 ，扩容后，原来 table[0] 出的链表里的所有元素会被分配到新的数组中 newTable[0] 和 newTable[16] 这两个位置上。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 新的数组
Entry[] newTable = new Entry[newCapacity];
// 将原来数组中的值迁移到新的更大的数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}1.6 put 操作
public V put(K key, V value) {
// table 为空时，需要先初始化数组大小
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果 key 为 null，感兴趣的可以往里看，最终会将这个 entry 放到 table[0] 中
if (key == null)
return putForNullKey(value);
// 1. 求 key 的 hash 值
int hash = hash(key);
// 2. 找到对应的数组下标
int i = indexFor(hash, table.length);
// 3. 遍历一下对应下标处的链表，看是否有重复的 key 已经存在，
// 如果有，直接覆盖，put 方法返回旧值就结束了
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 4. 不存在重复的 key，将此 entry 添加到链表中
addEntry(hash, key, value, i);
return null;
}1.7 get 操作
public V get(Object key) {
// 之前说过，key 为 null 的话，会被放到 table[0]，所以只要遍历下 table[0] 处的链表就可以了
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 1. 根据 key 值计算 hash 值
int hash = (key == null) ? 0 : hash(key);
// 2. 确定数组下标(hash & (length - 1))
// 3. 从头开始遍历链表，直到找到相等(== 或 equals)的 key
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}二 Java 8 HashMap
Jvava 8 对 HashMap 进行了一些修改，最大的不同是使用了红黑树，所以其由 数组 + 链表 + 红黑树 组成。在上述 Java 7 HashMap 的介绍，我们知道，查找的时候，根据 hash (key) & (length - 1) 我们能快速的定位到数组的具体下标，之后我们需要遍历对应链表，直到找到目标值，时间复杂度取决于链表的长度，为 O(n) 。为了提高性能，降低开销，在 Java 8 中，当链表的元素超过 8 个以后，会将链表转换成红黑树，在红黑树中进行查找时时间复杂度可以降低到 O(lg n ) 。
2.1 Java 8 HashMap 结构
在 Java 7 中使用 Entry 来代表每个 HashMap 中的数据节点，Java 8 中使用 Node，基本没什么区别，都是 key，value，hash 和 next 这四个属性，不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode 。
2.2 数组扩容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 对应数组扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 将数组扩大一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 将阈值扩大一倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 使用新的数组大小初始化新的数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 如果是初始化数组的话，到这里结束了，返回 newTab 即可
if (oldTab != null) {
// 遍历原数组，进行数据迁移
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果该数组位置上只有单个元素，就迁移这个元素
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 这里是红黑树的情况
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 这里是处理链表的情况，会把链表拆分为两个链表，放到新的数组里，并保留原来的先后顺序，loHead、loTail 对应一条链表，hiHead、hiTail 对应另一条链表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
// 第一条链表
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 第二条链表，新的位置是 j + oldCap
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}2.3 put 操作
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/*
* 第三个参数是 onlyIfAbsent 如果是 true，那么只有在不存在该 key 时才会进行 put 操作
* 第四个参数是 evict 我们不必关心
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 第一次 put 值的时候，会触发下面的 resize()，类似 Java 7 第一次 put 时也要初始化数组长度
// 第一次 resize 和后续的扩容有些不一样，第一次是数组从 null 初始化到默认的 16 或者自定义的容量
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;
// 如果该节点是红黑树的节点，调用红黑树的插入方法插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 链表的插入方法
for (int binCount = 0; ; ++binCount) {
// 插入到链表最后面(Java 7 是插入到链表最前面)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD 为 8 ，即待插入的值是链表中的第 9 个，会触发 treeifyBin ,将链表转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果在链表里找到了“相等”的 key(== 或 equals )
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 此时 break ，那么 e 为链表中的 node (与带插入的值的 key “相等”)
break;
p = e;
}
}
// e!=null 说明已经存在 key 与带插入的 key “相等”，put 操作则进行值覆盖，然后返回旧值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果 HashMap 由于新插入值导致 size 已经超过了阈值，需要进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}2.4 get 操作
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1. 计算 key 的 hash 值，根据 hash 值找到对应数组下标(hash (key) & (length - 1))
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 2. 判断数组该位置处的元素是否刚好是我们找的，不是的话，走下一步
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 3. 判断该元素类型是否是 TreeNode ，如果是，用红黑树的方法取数据，如果不是，走下一步
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 4. 遍历链表，直到找到相等(== 或 equals )的 key 值
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}