Java容器——HashMap简要分析
Base on Java8
简介
HashMap是基于哈希表实现的映射（map）。此实现提供了所有可选映射操作，并允许空值和空键。(HashMap类大致相当于Hashtable，只是它是不同步的，并且允许空值)。该类不能保证映射的顺序，特别是，它不能保证顺序随时间保持不变。
这个实现为基本操作(get和put)提供了恒定时间的性能（ constant-time performance），假设哈希函数将元素正确地分散在桶（bucket）中。对集合视图迭代需要的时间与HashMap实例的“容量”(bucket的数量)加上它的大小(键-值映射的数量)成正比。因此，如果迭代性能很重要，那么不要将初始容量设置得太高(或负载系数设置得太低)，这一点非常重要。
HashMap的实例有两个影响其性能的参数:初始容量和负载因子。初始容量是哈希表中的桶数，就是创建哈希表时的容量。负载因子是一种度量方法，用来衡量在自动增加哈希表的容量之前，哈希表允许达到的满度。当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表将被重新哈希(rehash，即重新构建内部数据结构)，这样哈希表的桶数大约是原来的两倍。
作为一般规则，默认的负载因子(.75)在时间和空间成本之间提供了一个很好的折衷。较高的值会减少空间开销，但会增加查找成本(反映在HashMap类的大多数操作中，包括get和put)。在设置初始容量时，应该考虑映射中的预期条目数及其负载因子，以便最小化重散列操作的数量。如果初始容量大于最大条目数除以负载因子，则不会发生重新散列操作（rehash）（If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.）。
如果要在一个HashMap实例中存储许多映射，那么以足够大的容量创建它将比根据需要让映射自动执行重散列以增长表更高效。注意，对同一个hashCode()使用多个键肯定会降低散列表的性能。为了改善性能，当键是可比较（即键实现Comparable接口）的时，这个类可以使用键之间的比较顺序来帮助断开连接）（this class may use comparison order among keys to help break tie）。
即hash冲突时，将冲突的key-value作为链表链接在数组上；同时Comparable接口可以有助于实现HashMap内部的红黑树。
注意，这个实现不能保证同步。如果多个线程并发地访问一个散列映射，并且至少有一个线程修改了映射的结构，那么它必须在外部进行同步(结构修改是添加或删除一个或多个映射的任何操作;仅仅改变实例已经包含的键相关联的值不是结构修改)。这通常是通过在封装映射的某个对象上进行同步来实现的（This is typically accomplished by synchronizing on some object that naturally encapsulates the map）。如果不存在这样的对象，则应该使用集合“包装”映射（ Collections.synchronizedMap）。这最好在创建时完成，以防止意外的非同步访问映射:
Map m = Collections.synchronizedMap(new HashMap(...));
这个类的所有“集合视图方法”返回的迭代器都是快速失败（fail-fast）的:如果在迭代器创建后的任何时候对映射进行了结构上的修改——除了通过迭代器自己的remove方法之外的任何方式，迭代器都将抛出一个ConcurrentModificationException异常。因此，在面对并发修改时，迭代器会快速且干净地失败，而不是在未来某个不确定的时间冒险做出任意的、不确定的行为。
注意，迭代器的快速失败行为不能得到保证，因为一般来说，在存在非同步并发修改时不可能做出任何硬性保证。快速失败迭代器尽最大努力抛出ConcurrentModificationException。因此，如果要编写一个依赖于这个异常来保证其正确性的程序，那将是错误的:迭代器的快速失败行为应该仅用于检测错误。
该类是Java Collections框架的成员。
分析
HashMap本质上是一个散列表，那么就离不开散列表的三大问题：散列函数、哈希冲突、扩容方案；同时作为一个数据结构，必须考虑多线程并发访问的问题，也就是线程安全。这四大重点则为学习HashMap的重点，也是HashMap设计的重点。
先看HashMap的使用场景：
Map<String, String> map = new HashMap<>();
map.put("key", "value");
put方法将键值对存入HashMap。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
在HashMap种，put方法则继续调用putVal方法，传入的第一个参数就是存放的key的哈希值。也就是通过散列函数计算出的哈希值。
哈希函数
哈希函数的目的就是确定所要存放的元素在数组中的下标。
查看hash方法的源码：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这段代码叫“扰动函数”。
大家都知道上面代码里的key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。
理论上散列值是一个int型，如果直接拿散列值作为下标访问HashMap主数组的话，考虑到2进制32位带符号的int表值范围从-2147483648到2147483648。前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的3。
当然，要在内存中存放40亿长的数组不太现实，所以需要通过取模运算得到数组下标。取模运算通过indexFor方法完成（JDK8没有indexFor方法，而是直接通过table[index = (n – 1) & hash]实现）4。
这里也同样可以看出为什么HashMap的数组长度要取为2的整数幂，因为这样（数组长度-1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101 //高位全部归零，只保留末四位
从HashMap的构造函数可以看出HashMap的初始化容量可以被指定：
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
为了保证HashMap数组长度为2的整数幂，HashMap提供了tableSizeFor方法，该方法使最高位的1后面的位全变为1。
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;
}
调用者确保传入的cap为正整数。
比如：传入的cap为12
0000,1001 #n=11
>>>1 0000,0100
| 0000,1001
------------------
0000,1101 #n=13
>>>2 0000,0011
| 0000,1101
------------------
0000,1111 #n=15
>>>4 0000,0000
| 0000,1111
------------------
0000,1111 #n=15
...
不难看出，最后执行下去n的结果还是15，也就是2n-1，所以最后返回时会进行加1操作。
如果对传入的cap没有做减1操作，且cap刚好为2的整数次幂，则返回值会变为cap的2倍。
哈希冲突解决
一旦哈希表的长度小于准备插入表的数据，那么hash冲突必然会出现。hash冲突指的是两个不同的key经过hash计算之后得到的数组下标是相同的。解决hash冲突的方式很多，如开放定址法（前提是散列表的长度大于等于所要存放的元素）、再哈希法、公共溢出表法（把哈希表分为公共表和溢出表，如果发生了溢出，溢出的数据全部放在溢出区5）、链地址法。HashMap采用的是链地址法。
旧版本（JDK1.8之前）的HashMap存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（TREEIFY_THRESHOLD默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能（O(logn)）。当长度小于（UNTREEIFY_THRESHOLD默认为6），就会退化成链表4。
扩容
进行putVal方法插入数据时会比较当前容器包含元素数与最大容量和负载因子乘积的大小：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
if (++size > threshold)
resize();
...
}
threshold：The next size value at which to resize (capacity * load factor).
得益于HashMap保证哈希表的容量为2的整数次幂，数据的迁移也较为方便。
key在新的数组的hash结果只有两种：在原来的位置，或者在原来位置+原数组长度。
比如：
hashcode 0010 1101
length-1 & 0000 0111
----------------------
0000 0101
扩容后
hashcode 0010 1101
length-1 & 0000 1111
----------------------
0000 1101
在新数组中的hash结果，仅仅取决于高一位的数值。如果高一位是0，那么计算结果就是在原位置，而如果是1，则加上原数组的长度即可。
源码
put
Params:
hash – hash for key
key – the key
value – the value to put
onlyIfAbsent – if true, don't change existing value
evict – if false, the table is in creation mode.
Returns:
previous value, or null if none
public V put(K key, V value) {
// 获取hash值，再调用putVal方法插入数据
return putVal(hash(key), key, value, false, true);
}
// onlyIfAbsent表示是否覆盖旧值，true表示不覆盖，false表示覆盖，默认为false
// evict和LinkHashMap的回调方法有关，不在本文讨论范围
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab是HashMap内部数组，n是数组的长度，i是要插入的下标，p是该下标对应的节点
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断数组是否是null或者是否是空，若是，则调用resize()方法进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 使用位与运算代替取模得到下标
// 判断当前下标是否是null，若是则创建节点直接插入，若不是，进入下面else逻辑
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// e表示和当前key相同的节点，若不存在该节点则为null
// k是当前数组下标节点的key
Node<K,V> e; K k;
// 判断当前节点与要插入的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);
// 最后一种情况是直接链表插入
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 长度大于等于8时转化为红黑树
// 注意，treeifyBin方法中会进行数组长度判断，
// 若小于64，则优先进行数组扩容而不是转化为树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 找到相同的直接跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果找到相同的key节点，则判断onlyIfAbsent和旧值是否为null
// 执行更新或者不操作，最后返回旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 如果不是更新旧值，说明HashMap中键值对数量发生变化
// modCount数值+1表示结构改变
++modCount;
// 判断长度是否达到最大限度，如果是则进行扩容
if (++size > threshold)
resize();
// 最后返回null（afterNodeInsertion是LinkHashMap的回调）
afterNodeInsertion(evict);
return null;
}
代码注释来自参考6
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;
// 如果原数组长度大于0
if (oldCap > 0) {
// 如果已经超过了设置的最大长度(1<<30,也就是最大整型正数)
if (oldCap >= MAXIMUM_CAPACITY) {
// 直接把阈值设置为最大正数
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 设置为原来的两倍
newThr = oldThr << 1;
}
// 原数组长度为0，但最大限度不是0，把长度设置为阈值
// 对应的情况就是新建HashMap的时候指定了数组长度
else if (oldThr > 0)
newCap = oldThr;
// 第一次初始化，默认16和0.75
// 对应使用默认构造器新建HashMap对象
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果原数组长度小于16或者翻倍之后超过了最大限制长度，则重新计算阈值
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;
// 如果他没有后继节点，那么直接使用新的数组长度取模得到新下标
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是红黑树，调用红黑树的拆解方法
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 新的位置只有两种可能：原位置，原位置+老数组长度
// 把原链表拆成两个链表，然后再分别插入到新数组的两个位置上
// 不用多次调用put方法
else {
// 分别是原位置不变的链表和原位置+原数组长度位置的链表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍历老链表，判断新增判定位是1or0进行分类
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;
}
代码注释来自参考6
