背景
在JDK1.2的 java.util 包中增加了一个 Collection 接口和 Map<K,V> 接口，用于对不同类型的元素进行操作。 Map<K,V> 接口主要用于存储以 Key-Value 形式的元素，其中 HashMap 就是 Map 接口的一个实现类。
名词介绍
比特：二进制数字中的位，信息量的度量单位，为信息量的最小单位。二进制数系统中，每个0或1就是一个位(bit)，位是数据存储的最小单位。其中8bit就称为一个字节（Byte）。
设计猜想
在探究源码之前，首先我们先尝试用自己的逻辑来设计下HashMap<K,V>的数据结构。在我们熟悉的数据结构中有 一种hash表的数据结构符合HashMap的存储要求。
[散列表](Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是 说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数， 存放记录的数组叫做散列表。
在设计HashMap中需要关注的几个方面:
数组大小、类型一旦确定，编译、运行时都不可修改，必须对HashMap的数组进行动态扩容。
通过Key计算得到的Hash值，必须保证元素都能正确的被保存，需要考虑hash冲突的影响。
设计思路
- 通过计算
key的hash值，然后对hash值和数组size进行取模运算得到一个数组的索引，将元素A添加到数组中，如果出现索引相同且Value对象不相等，则将元素添加到元素A后面。这里要求数组中的元素必须是一个Node节点，用于添加元素。 - 如果数组容量已经超过一定范围，对数组进行动态扩容，复制一个新的数组，将旧数组的元素重新计算hash值放入新数组中。
- 如果链表的长度超过一定范围，则将链表转换成红黑树降低查找的复杂度。
根据我们的猜想，我们可以通过HashMap源码进行验证。
源码分析
1.计算Key的hash值
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {}
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
其中 hash(key) 方法就是计算key的hash值， (h = key.hashCode()) ^ (h >>> 16) 使用高位16位和低16位异或运算得到Hash值，主要为了使hash分布尽可能的均匀。
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) {
//............
}else if (oldThr > 0) // initial capacity was placed in threshold
//............
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//............
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
通过resize()方法创建一个初始容量为 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 ，负载因子为 static final float DEFAULT_LOAD_FACTOR = 0.75f 的 Node 数组( Node 实现 Map.Entry 接口)。
3.存放元素
3.1数组索引位置上没有元素
计算数组 (n - 1) & hash 位置上是否存在元素，如果该索引位置上没有元素，则直接将新数据插入数据。
这里利用&运算的特性:
这里约定数组大小必须是2的幂函数，这样才能保证n-1&hash值为数组索引值。
| hash | 1010010101001010101 | 1010010101001001111 |
|---|---|---|
| n-1 | 0000000000000001111 | 0000000000000001111 |
| (n-1)&hash | 0000000000000000101=5 | 0000000000000001111 =15 |
精妙之处在于这里利用 & 运算的特性，保证n-1二进制最大位为0，则计算结果就等于数组下标，&相比于传统的取模运算性能更优。
3.2 数组索引位置存在元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// ............
else {
Node<K,V> e; K k;
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) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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)
e.value = value;
afterNodeAccess(e);
return oldValue;
} }
//............
这里分3中情况来分析:
-
如果数组索引位置的元素的key和新元素的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);
- 如果数组索引位置的元素仍是一个链表节点，则遍历这个节点，如果链表长度大于8则转换成红黑树，否则直接 新增一个节点添加到链表的表尾。
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
}
扩容机制
我们知道集合接口的出现主要是解决数组长度、类型固定的限制。实现机制主要是利用引用类型和数组动态扩容来 实现。 HashMap 实现 Map 接口的集合， HashMap 的扩容机制是怎样的呢?
猜想:如果数组容量小于数组容量的75%,我们就实现动态扩容一倍。原先数组上的链表需要重新根据新数组索引号 进行分配。
1.发生扩容的触发条件
if (++size > threshold)
resize();
数组size大于 threshold 时进行扩容。
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
这里使用 newCap = oldCap << 1 给新数组进行扩容，同时设置阈值 newThr = oldThr << 1 。
3.遍历旧数组转移至新数组
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
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;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
3.1仅一个元素
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
旧数组索引位置仅含有一个元素，将旧数组索引的元素转移至新数组相同索引位置上。
3.2元素为红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
旧数组索引位置元素为红黑树时，执行红黑树的方法
3.3元素为链表
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;
newTab[j + oldCap] = hiHead;
}
这里利用了 (e.hash & oldCap) == 0 算法实现链表元素位置控制:
1.如果(e.hash & oldCap) == 0，则数组位置不变
2.如果(e.hash & oldCap) != 0,则数组位置为原位置+OldCap
| hash | 101011010101010101 | 101011010101000101 |
|---|---|---|
| oldcap | 000000000000010000 | 000000000000010000 |
| e.hash & oldCap | 000000000000010000=16 | 000000000000000000=0 |
| 新元素位置 | Node[i]=Node[i+OldCap.length] | Node[i]=Node[i] |
