HashMap概述

简介

Java为数据结构的映射定义了一个接口java.util.Map，其中有四个常用实现类：HashMap、HashTable、LinkedHashMap和TreeMap。

Map

HashMap：根据键的hashCode值存储数据，允许一条记录的键为null，访问速度快，遍历顺序不稳定。HashMap线程不安全，并发环境可以使用Collections的syncronizedMap方法将它包装为线程安全的Map但是更推荐使用ConcurrentHashMap。JDK8以前HashMap使用数组＋链表的数据结构，而JDK8之后引入了红黑树结构，查找时间复杂度为O(logn)，当链表长度大于8并且数组长度大于64时会将链表转为红黑树。

LinkedHashMap：LinkedHashMap是HashMap的一个子类，通过加入双向链表保证了遍历的有序性。

Hashtable：Hashtable功xd能与HashMap类似，不同点是它继承Dictionary类，因此键值都不允许null，它直接对方法添加synchronized，是线程安全的。

TreeMap：TreeMap实现SortedMap接口，默认是按键值的升序排序，也可以指定排序的比较器，如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，它的key不能为null，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

哈希值

哈希值（hashCode）：为了支持哈希表而定义在Object中通过hashCode方法获取的对象散列码，它是一个int类型的整数，默认情况下使用对象的存储地址。

在HashMap中，存储键值对的数组地址就是通过对hashCode进行哈希算法获得的，而当数组的这个地址上有元素时会调用key的equals方法判断键是否重复，如果键储存引用数据类型，需要同时重写hashCode和equals方法，以维护为了维护equals方法的一般约定：equals判断相等的对象hashCode也必须相等。

哈希冲突

当对两个不同存储元素进行哈希运算得到地址相同时，就发生了哈希冲突（哈希碰撞），解决哈希冲突的方案有很多：开放寻址法、连地址法、再散列函数法等，而HashMap采用了链地址法来解决哈希冲突。

HashMap详解

存储结构

HashMap存储结构基于数组＋链表+红黑树（JDK8新增）实现。

HashMap中的哈希桶数组采用Node数组。

1
transient Node<K,V>[] table;

Node类型实现类Map.Entry接口，定义为一个映射（键值对）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) { ... }
    public final K getKey()        { ... }
    public final V getValue()      { ... }
    public final String toString() { ... }
    public final int hashCode() { ... }
    public final V setValue(V newValue) { ... }
    public final boolean equals(Object o) { ... }
}

对于扩容后的红黑树结构，则是使用TreeNode结构

1
2
3
4
5
6
7
8
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;
	...
}

由于链表的查找时间复杂度为O(n)，而红黑树结构的查找时间复杂度为O(logn)，当数据量较大时优于链表，因此引入了红黑树结构。

将链表长度阈值设置为8有几个原因：一是当链表长度达到8时，由于链表的平均查找长度位n/2等于4，此时红黑树平均查找长度为log2(8)等于3，之后红黑树查找效率才会开始显著高于链表；二是键值对分布满足泊松分布，大部分情况下在数组中分散较为均匀，当链表长度还未达到8时就已经扩容，HashMap维护的几乎都是链表，只有性能已经很差时才会达到树化阈值8。

成员属性

HashMap定义了几个重要的成员属性。

数组的默认初始容量为16，且扩容后必须为2的幂（合数）。常规设计是把桶的大小规定为素数，因为素数导致的冲突概率小于合数，因此Hashtable初始桶容量为11，而HashMap采用合数是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。

1
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

荷载系数（加载因子），默认为0.75，当键值对数量size大于数组容量乘以荷载系数时数组会进行扩容。默认值定义为0.75是在时间和空间成本之间提供了良好的权衡。较高的值会减少空间开销，但会增加查找成本。

1
static final float DEFAULT_LOAD_FACTOR = 0.75f;

链表的阈值长度默认为8，数组树化最小长度为64，即当数组长度大于64且链表长度大于8时链表结构转为红黑树结构，而取消树化的默认阈值为6。

1
2
3
4
5
static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

static final int MIN_TREEIFY_CAPACITY = 64;

哈希算法

计算哈希值是操作键值对的第一步，最终的哈希值是取hashCode的高位参与运算。值为null的键无法获取hashCode，因此直接返回0值，这也决定了HashMap只能存储一个值为null的键，而value不参与计算因此可以存在多个记录为null。

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

而键对应的最终数组下标并非hash值，通常是将hash值对数组长度取模运算，这样得到的数组下标的分布较为均匀，但取模消耗较大，因此HashMap通过效率更高的(n - 1) & hash运算得到保存位。由于数组长度总是2的幂，这种运算等价于对n取模，也就是hash%n。

1
tab[i = (n - 1) & hash]

JDK8中优化了高位运算算法，是通过hashCode的高16位异或低16位实现的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

1
2
3
4
5
6
7
 h = key.hashCode() : 1111 1111 1111 1111 1111 0000 1110 1010
		   h >>> 16 : 0000 0000 0000 0000 1111 1111 1111 1111
hash = h ^ h >>> 16	: 1111 1111 1111 1111 0000 1111 0001 0101

	 (n - 1) & hash : 0000 0000 0000 0000 0000 0000 0000 1111
					  1111 1111 1111 1111 0000 1111 0001 0101 
				  i : 0101 = 5

put方法

HashMap调用无参构造时并不会创建Node数组，只有在第一次调用put方法时才会创建长度为16的数组，这个过程在数组扩容方法resize中完成。

HashMap调用put方法的大概流程为：

  1. 判断数组table是否为空或为null，是则调用resize方法扩容，初始容量为16。
  2. 根据key的hash值计算数组下标i，如果table[i]为空则直接添加，如果不为空但调用首元素key值的equals方法判断键相同则覆盖并返回旧值，覆盖操作不会创建新的Node结点。
  3. 判断table[i]结点是否为TreeNode类型，如果是则安装红黑树规则添加元素。
  4. 若非红黑树则按照链表规则遍历，遍历过程中如果key存在则覆盖元素，否则插入链表尾部。此时如果链表长度大于8则调用treeifyBin方法将链表转为红黑树（方法内会判断键值对数量是否达到64，是则树化否则仅扩容）。
  5. 插入后判断键值对数量size是否大于threshold（数组容量乘以荷载系数），是则调用resize方法扩容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 数组为空则初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // table[i]为空直接添加
    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) {
                // 插入成功后判断是否转为红黑树
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // key值相同则覆盖
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 覆盖并返回旧值，不会创建新的Node结点
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 判断是否扩容
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

扩容机制

在JDK7中，会先引用扩容前的Entry数组，若数组大小已达到最大则不会再扩容，之后会创建一个新的Entry数组获取旧Entry的所有元素，释放旧Entry数组对象引用并重新计算每个元素在数组的位置，新的链表采用头插法创建链表。

而JDK8做了优化，由于使用2次幂扩容，重新计算hash值后只会修改高位bit，元素的位置要么在原位置上，要么移动2次幂的位置，因此不需要重新计算hash，只需要判断新增位bit的值，如果为0则索引不变，如果为1则新索引等于原索引+oldCap，重新得到的链表也不会倒置。

哈希运算后同一数组位置的key被分散到了原位置和原索引+oldCap位置上：

1
2
3
4
5
6
7
oldCap : .... 0000 1111
 hash1 : .... 0000 0101 -> .... 0000 0101 -> 00101 = 5
 hash2 : .... 1111 0101 -> .... 0000 0101 -> 00101 = 5
   
newCap : .... 0001 1111
 hash1 : .... 0000 0101 -> .... 0000 0101 -> 00101 = 5
 hash2 : .... 1111 0101 -> .... 0001 0101 -> 10101 = 5 + 16

尽管如此，扩容仍极为消耗性能，因此使用HashMap时尽可能估算Map的大小，初始化一个大概的数值，避免频繁扩容。

多线程死循环

HashMap是线程不安全的，并发环境下会发生多种错误，严重时会导致链表循环引用进而导致死循环。

在JDK7中一个典型的例子是：当两个线程添加完元素同时执行到resize方法时，第一个线程在原数组中遍历链表的过程中，第二个线先完成了rehash链表重组，使得链表倒置，此时线程一结点便指向之前的结点导致了循环链表。

遍历方式

HashMap有多种常用的遍历方式：遍历keySet集合、遍历entrySet集合、Lambda表达式直接遍历Map、获取entrySet的iterator迭代器进行遍历等，其中更推荐使用迭代器，效率较高，且能够直接调用迭代器的remove方法移除当前键值对。

参考文献