HashMap数据结构
数组 + 链表
HashMap要实现哈希表的效果，尽量实现O(1)级别的增删改查，它的具体实现是同时使用了数组和链表。
首先HashMap的内部定义了静态类Node来实现Entry接口
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
Node实际上就是一个链表。
另外HashMap还定义了一个数组table来存储各个链表的表头
transient Node<K,V>[] table;
数组 + 红黑树
在Java 8中，HashMap相比之前的版本有了一个改动，那就是树化。当满足一定条件时，HashMap会将链表转化成红黑树，这是为了提高性能。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
HashMap相关字段
initialCapacity
刚刚提到了HashMap实际上就是数组加链表构成的，而initialCapacity就是数组初始的长度，也可以理解为HashMap的容量。HashMap的容量必须是2的N次方，至于原因后面会详细描述，默认长度是16
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
HashMap并不要求用户在指定HashMap容量时必须传入一个2的N次方的整数，而是通过下面的方法计算出比指定整数大的最小的2^N。
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;
}
下面详细解释一下为什么经过上述位移操作就能得到想要的结果。
首先，我们思考下2^N次方的二进制都有什么特征
0000 0010 // 2
0000 0100 // 4
0000 1000 // 8
0001 0000 // 16
可以看到对于2^N次方，它只有一位为1，其他都为0。那么对于任意一个整数，如果我们找到它的最高位1(从左往右出现的第一个1)，那么我们只要将这个1向左移一位，同时将其他位置为0就可以得到大于目标值的最小的2^N次方。
可以结合下面的公式来理解
2^0 + 2^1 + 2^2 + …… + 2^(n-1) = 2^n -1
2^0 + 2^1 + 2^2 + …… + 2^(n-1) < 2^n
OK，现在可以将问题转化为如何将一个数的最高位1向左移一位，并且其他位置为0.其实很简单，只要我们将将低于最高位1的位置都变成1，然后在加1就可以得到。我们以20为例
0001 0100 // 20
0001 1111 // 将低于最高位1的位置都变成1
0010 0000 // 0001 1111 + 1
现在在回过头看函数的实现
n |= n >>> 1
1. 将n向右移一位，那么最高位1也向右移了一位
2. 将n | (n>>>1),那么可知最高位1的下一位也变成了1
我们以20为例，最高位为5，经过操作之后第4位变成了1
0001 0100 // 20
0000 1010 // 20 >>> 1
0001 1110 // 20 | (20 >>> 1)
由于在Java中，int占4个字节，也就是32位，所有经过5次位移就可以将所有位都置为1。
这里有一种特殊情况，如果输入的数本身就是2^N次方，那么经过移位后得到的是2^(N+1)次方，以16为例
0001 0000 // 16
0001 1111 // 低于最高位都置为1
0010 0000 // 0001 1111 + 1 得32
可以看到得到的结果不符合预期，我们应该返回16才对。对于这种情况该怎么处理呢？很简单，我们只需要把输入数在处理之前做一个减1操作即可，为什么这样做呢？
原因很简单，如果一个数不是2的乘方，那么它本身减1之后，最高位的位置是不会变的，而我们后续会把最高位后的所有低位都变成1，所以这些低位本身是1或者是0都是不重要的，例如
0000 1101 - 1 = 0000 1100
0000 1101 --> 0000 1111
0000 1100 --> 0000 1111 不论是原值还是减1之后的值，经过位移操作之后得到的都是0000 1111
而如果输入数本身就是2的乘方，那么我们减1之后，最高位的位置会往右移动一位（剩余都是1），我们把它+1之后，又变成了它的原值。
loadFactor
当数据不断被put到HashMap，容量逐渐趋向饱和，那么就越容易造成哈希冲突，因此需要对HashMap进行扩容。而loadFactor(装载因子)就是用来决定扩容的时机。默认值是0.75
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
相关常量
// HashMap的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 链表的长度超过该阈值，则尝试进行将链表变化红黑树
static final int TREEIFY_THRESHOLD = 8
// 链表的长度小于该阈值，则尝试将红黑数变成链表
static final int UNTREEIFY_THRESHOLD = 6;
// 当数组的长度超过该阈值，才会将链表变成红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
// 当前map存储键值对的个数
transient int size;
// HashMap结构被修改的次数，put,remove等操作都会导致次数增加
transient int modCount;
// 扩容阈值，当map存储的键值对超过这个阈值就会进行扩容
// threshold = capacity * loadFactor
int threshold;
构造函数
// 无参构造函数，默认capacity为16，默认loadFactor为0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 指定initialCapacity，loadFactor为默认值
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 最终的构造函数
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 计算初始的扩容阈值
this.threshold = tableSizeFor(initialCapacity);
}
可以看到HashMap在初始化的时候，只是计算了loadFactor以及threshold两个参数的值，并没有初始化数组table。
这是因为HashMap属于懒加载，只有首次进行put操作时，HashMap才会初始化table
寻址方式
对于put或者get操作，HashMap会取得key的hashcode，将hashcode与数组的长度取模，得到的结果作为数组的index。在计算机中取模的代价远高于位操作的代价，因此HashMap要求数组的长度必须为2的N次方。此时将Key的哈希值对2^N-1进行与运算，其效果即与取模等效。
// 当n = 2^N
hash % n = hash & (n - 1)
hash
为了减少哈希冲突，HashMap并不是简单的把key的hashcode作为hash值，而是进行一定的优化，其中java8和之前的java版本对比有了其他的改进。
在java8之前的版本，HashMap通过如下方法使得最终的哈希值的二进制形式中的1尽量均匀分布从而尽可能减少哈希冲突
static int hash(int h) {
// 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);
}
而在java8中，采用如下的方法计算hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
前面我们已经知道HashMap通过hash & (n - 1)来决定数据的位置，很显然这种计算方式决定了数据的位置只和低位的数值有关，这样会使得哈希冲突的可能性增加。
因此HashMap让高16位的值不变，低16位与高16位进行异或操作，最终得到hash值。
put
下面我们来看下，在java8中，HashMap如何插入一个元素。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
可以看到put的主要实现都在putVal这个函数里
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; // 节点数据
Node<K,V> p; // 待插入节点
int n, i; // n 为数据长度，i为待插入节点在数组中的索引
// table是否已经初始化，若无，则进行初始化，具体过程在resize中实现
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算待插入节点的索引，i = (n - 1) & hash
// 若无冲突，则直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 插入的key是否已经在map中
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// HashMap是否树化
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;
}
}
// 该key之前就在map中，返回旧value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// map容量超过阈值，进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
代码看不清楚的话，直接来看流程图。
Java8中，HashMap最大的变动就是增加了树化处理，当链表中的数据超过8个时，HashMap会尝试将链表改造成红黑树。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 当数组的长度小于MIN_TREEIFY_CAPACITY，只是进行扩容，而不是树化
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;
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);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
可以看到当tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY为true时，只会进行扩容处理，而没有进行树化；MIN_TREEIFY_CAPACITY规定了HashMap可以树化的最小表容量为64，这是因为当一开始哈希表容量较小是，哈希碰撞的几率会比较大，而这个时候出现长链表的可能性会稍微大一些，这种原因下产生的长链表，我们应该优先选择扩容而避免这类不必要的树化。
那么为什么要进行树化呢？因为链表的查询效率远远低于数组，当过多的数据连成链表时，会降低查询效率。
resize
我们都知道数据是无法自动扩容的，只能重新计算新的容量，创建新的数组，并将所有数据拷贝到新的数组中，最后在释放掉旧的数据。
Java8对resize方法进行了优化，具体区别我们来仔细看下
Java8之前的resize
对于Java8之前的版本，它创建一个新的，长度为原来Capacity两倍的数组，保证新的Capacity仍为2的N次方，从而保证上述寻址方式仍适用。同时需要通过如下transfer方法将原来的所有数据全部重新插入（rehash）到新的数组中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
该方法并不保证线程安全，而且在多线程并发调用时，可能出现死循环。其执行过程如下
- 遍历原数组中的元素
- 对链表上的每一个节点遍历：用next取得要转移那个元素的下一个，将e转移到新数组的头部，使用头插法插入节点
- 循环2，直到链表节点全部转移
- 循环1，直到所有元素全部转移
单线程rehash
在单线程下，扩容操作没有问题，扩容后链表顺序倒转(因为使用头插法)
多线程rehash
这里假设有两个线程同时执行了put操作并引发了rehash，执行了transfer方法，并假设线程一进入transfer方法并执行完next = e.next后，因为线程调度所分配时间片用完而“暂停”，此时线程二完成了transfer方法的执行。此时状态如下
接着线程1被唤醒，继续执行第一轮循环的剩余部分
e.next = newTable[1] = null
newTable[1] = e = key(5)
e = next = key(9)
结果如图
接着执行下一轮循环，结果状态图如下所示
继续下一轮循环，结果状态图如下所示
此时循环链表形成，并且key(11)无法加入到线程1的新数组。在下一次访问该链表时会出现死循环
Java8的resize
Java8也规定了每次扩容都为之前的两倍（n*2），但是Java8不会重新计算每个值在数组中的索引位置。这是因为由于扩容为之前的2倍，新的索引位置只有两种情况，一是索引没有变化，而是原位置+扩容长度(即偏移值为扩容长度大小)
前面就说过，数据的在数组的索引是由hash & (n-1)计算得到的，其中n为数组长度。
我们假设当前数组length=16，两个数据的hash值分别为21和5
从上图可以看到，在扩容前21(0001 0101)和5(0000 0101)计算后得到的索引都为5，在扩容后，21得到的新索引为5+16 = 21，而5得到的新索引还是5
我们可以看到，数组扩容为原来的两倍后，只是将最高位往左移了一位
因此在进行&运算之后，和扩容前相比只可能出现两种情况，一种是毫无影响，一种为原位置 + 扩容长度
扩容前 扩容后
01xxx 11xxx
& &
mnxxx mnxxx
| m | n | 扩容前 | 扩容后 |
|---|---|---|---|
| 0 | 0 | 00xxx | 00xxx |
| 0 | 1 | 01xxx | 01xxx |
| 1 | 0 | 00xxx | 10xxx |
| 1 | 1 | 01xxx | 11xxx |
那么源码中是如何判断这两种情况呢？从表中我们也可以看到，只有m=0，则索引不变，m = 1,则索引偏移。那么如何判断m的值呢，其实只要 hash & n 就可以得到，源码实现如下，oldCap是原数组的大小，即 n
if ((e.hash & oldCap) == 0) {
...
} else {
...
}
接下来，我们来看下resize完整的源码
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// map已经初始化
if (oldCap > 0) {
// map容量超过最大值，不进行扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 进行扩容，map容量*2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// map构造时指定了initialCapacity参数
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// map构造时未指定任何参数
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// map构造时指定了initialCapacity参数,重新计算扩容阈值(threshold)
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;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//释放旧数据
oldTab[j] = null;
//表头只有一个数据，重新计算index
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表示表头
Node<K,V> loHead = null, loTail = null;
//扩容后，索引发生变化(原有值+扩容长度)，用hiHead表示
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;
}
}
}
}
}
return newTab;
}
resize的操作涉及了很多场景
- 无参构造：新容量是默认容量值16，新阀值是默认容量值16 * 负载因子0.75 = 12
- 有参构造：新容量是由传入的initialCapacity数据计算出大且最近的2^n的值，新阀值是新容量 * 0.75
- 正常扩容：旧容量大于等于最大容量值，设置新阀值为Integer.MAX_VALUE，结束扩容；否则新容量double操作
fast-fail
在使用迭代器的过程中如果HashMap被修改，那么ConcurrentModificationException将被抛出，也即Fast-fail策略
当HashMap的iterator()方法被调用时，会构造并返回一个新的EntryIterator对象，并将EntryIterator的expectedModCount设置为HashMap的modCount（该变量记录了HashMap被修改的次数）
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
在通过该Iterator的next方法访问下一个Entry时，它会先检查自己的expectedModCount与HashMap的modCount是否相等，如果不相等，说明HashMap被修改，直接抛出ConcurrentModificationException
总结
- Java8中HashMap相比之前的版本，在存储结构，寻址方式，resize等方面都进行了一定的改造优化
- HashMap的容量必须是2^N，是因为在计算数组索引时，位运算比取模运算性能更高
- HashMap使用的Lazy模式，初始化时不会创建table，而是直到put数据时才会创建table数组
- HashMap在resize时，索引只有两种情况，一是无变化，和原索引相等，另一种是原索引 + 扩容长度
