基于HashMapJDK1.8中的源码

参考前辈们的成果,简单的分析HashMap的源码,了解一下HashMap的存储结构,主要方法工作原理和线程安全这几个方面。

简介

Java为数据结构中的映射定义了一个接口java.util.Map,此接口主要有四个常用的实现类,分别是HashMap、Hashtable、LinkedHashMap和TreeMap,类继承关系如下图所示:

java.util.map类图

下面对各个实现类的特点做一些说明:

  1. HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。

  2. Hashtable:Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。

  3. LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

  4. TreeMap:TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类,要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化,Map对象很可能就定位不到映射的位置了。

通过上面的比较,我们知道了HashMap是Java的Map家族中一个普通成员,鉴于它可以满足大多数场景的使用条件,所以是使用频度最高的一个。


以上都不是我写的,摘自美团的技术博客:Java 8系列之重新认识HashMap,233333

存储结构

HashMap内部究竟是怎样的结构呢?看一下源码就明白了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
transient Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node

        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) { ... }
}
  • 从源码可知,HashMap的键值对存储在Node中。HashMap的字段中有又有一个Node的数组:table。也就是说我们的数据存储在这个哈希表中。
  • 哈希表会发生哈希冲突,HashMap为了解决哈希冲突使用了哪种方法呢?一般的,我们有 linear probing(线性探测,也有叫开放地址法的) 和 separate chaining(链地址法)两种方式。显而易见,HashMap使用了链地址法。

讲到这里,你可以停下来去实现一个使用 linear probing 或者 separate chaining 实现的简单的哈希表,如果你学过数据结构的话应该很简单,这里我简单的实现了一下:

有参考《算法 第四版》中symbol table的内容

 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
public class SeparateChainingHashST<Key, Value> {
  private int M = 97;
  // 没有扩容机制,哈希表的长度固定为97
  private Node[] st = new Node[M];

  private static class Node {
    private Object key; //no generic, because array creation
    private Object val;
    private Node next;

    Node(Object key, Object val, Node next) {
      this.key = key;
      this.val = val;
      this.next = next;
    }
  }

  private int hash(Key key) {
    // 与上0x7fffffff,使得符号位变为0。如果是正数,值不变,如果是负数,则相当于值加上2^32-1
    // M 是素数
    // 取模消耗较大
    return (key.hashCode() & 0x7fffffff) % M;
  }

  public void put(Key key, Value value) {
    int i = hash(key);
    Node x = st[i];
    while (x != null) {
      // 寻找重复的key,找到就覆盖原理的值
      if (key == x.key || (key != null && key.equals(x.key))) {
        x.val = value;
        return;
      }
      //不相等把指针往下移动
      x = x.next;
    }
    st[i] = new Node(key, value, st[i]); //插入到链表头部
  }

  public Value get(Key key) {
    int i = hash(key);
    for (Node first = st[i]; first != null; first = first.next) {
      if (key.equals(first.key)) {
        return (Value) first.val;
      }
    }
    return null;
  }
}

可以看到我这里实现的哈希表的哈希桶(源码中叫hash bin node,)数组的大小固定为97。那么在HashMap中是怎么确定数组的大小的呢?

如果哈希桶数组很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞,所以就需要在空间成本和时间成本之间权衡,其实就是在根据实际情况确定哈希桶数组的大小,并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小,哈希桶数组(Node[] table)占用空间又少呢?答案就是好的Hash算法和扩容机制。

在说明Hash算法和扩容机制之前,我们先要了解一下几个相关的字段。

1
2
3
4
int threshold;             // 所能容纳的key-value对,如果超过会扩容
final float loadFactor;    // 负载因子
int modCount;
int size;

table的初始化长度(capacity)(默认值是16)。HashMap中table的长度一定是2的幂。为什么这样设计呢?其实是为了根据key的hashCode快速确定其下标。

  • load factor为负载因子(默认值是0.75)。

  • threshold是HashMap所能容纳的最大数据量的Node(键值对)个数,threshold = capacity * load factor。*当哈希桶数组没有被初始化时,threshold为capacity的值或者为0。*键值对数量超过threshold就会进行扩容,扩容之后,capacity为原来的两倍。

  • size是HashMap中键值对的个数,而不是table的长度(capacity)。

  • modCount字段主要用来记录HashMap内部结构发生变化的次数,内部结构发生变化指的是结构发生变化,例如put新键值对,但是某个key对应的value值被覆盖不属于结构变化。

JDK1.8版本中,对数据结构做了进一步的优化,引入了红黑树。当链表长度太长(默认超过8)时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能。

主要方法

Hash算法

一个好的Hash算法可以减少哈希碰撞,使得元素的分布尽量均匀。HashMap的Hash算法主要分为三步:

  1. key的hashCode
  2. 高位XOR低位
  3. 巧妙的取模运算
1
2
3
4
5
6
    static final int hash(Object key) {
        int h;
      	// 第一步:key.hashCode()
      	// 第二步: h ^ (h >>> 16)
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的长度比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

putVal中有如下的语句,可知最终的下标为(capacity - 1) & hash

1
2
3
4
5
6
7
8
9
    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 - 1) & hash, 其中n为哈希桶数组的长度。
       if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
      //...
    }

为什么取模运算变成了按位与运算呢?或者说为什么可以这样做?

因为HashMap的哈希桶数组的长度总是2的n次方,当长度总是2的n次方时,h& (capacity-1)运算等价于对长度取模,也就是h%capacity,而&%具有更高的效率。

我们都知道h / (2^n)相当于h >> n,即逻辑右移n位。而被移掉的n位就是余数。而h & (2^n - 1)就是取h的后n位二进制,也就是在除法运算中被移掉的n位,所以h & (2^n - 1)相当于h % 2^n

下面为美团博客中的例子:

hashMap哈希算法例图

put方法

HashMap的put方法执行过程可以通过下图来理解:

hashMap put方法执行流程图

  1. 判断键值对数组table[i]是否为空或为null,执行resize()进行扩容。注意:table的初始化是在第一次put中执行的。

  2. 根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向6,如果table[i]不为空,转向3;

  3. 判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向4,这里的相同指的是hashCode以及equals的返回值相等;

  4. 判断table[i] 是否为TreeNode,即table[i]是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

  5. 遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

  6. 插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

JDK1.8的putval源码如下:

 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;
      	//步骤1:如果为null,则利用resize进行初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
      	//步骤2:如果该数组项为null,直接新建节点
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
          	//步骤3:如果key值重复,直接覆盖
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
           //步骤4:如果该节点为TreeNode,在红黑树中插入节点
            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);
                        // TREEIFY_THRESHOLD = 8
                        //步骤5:判断链表长度是否大于8,大于8 把链表转化为红黑树
                        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;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //步骤6:插入成功后,检查size是否大于threshold,大于就进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

扩容机制

我们在putval方法中有提过过扩容,HashMap会在两种情况下进行扩容:

  • 在哈希桶数组没有初始化时,调用put方法时会调用resize进行初始化
  • 当size大于threshold时
  • 当某条链表的长度大于8,但是哈希桶数组大大小小于64时,进行扩容,而不是树型化链表

resize的实现过程可以参考下面的流程图,省略了一些不必要的细节

PS:这次的图终于是我自己画的啦n(≧▽≦)n,用的processon。

HashMap-resize

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
    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;
            }
            // 原来capacity的两倍也没有超过最大值,进行扩容
            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);
        }
        // 重新计算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;
                    //链表中只有一个节点,直接根据下标插入table
                    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和下标需要改变的node。
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // 扩容是把capacity乘以2,这样新的hash值相当于高位多出一位。
                            // 判断hash多出来的一位是否为0,为0的话,那么它的下标不变
                            // 为1的话,它的下标变为原下标+oldCap
                            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;
    }

在复制数据的时候,不需要重新计算下标。只需要看看原来的hash值新增的那个bit是1还是0,是0的话下标没变,是1的话下标变成原下标+oldCap

美团博客中的例子如下:

hashMap 1.8 哈希算法例图2

线程安全

HashMap不是线程安全的,在多线程的环境下使用可能会发生死循环。可以使用线程安全的ConcurrentHashMapHashTable也是线程安全的,但是效率低。关于这部分的内容,大概会在review到线程的时候,再详细的写一写吧。

参考

JDK1.8 HashMap 源码

《Algorithms 4th》

Java 8系列之重新认识HashMap

HashMap源码分析(JDK 1.8)

酷壳:JAVA HASHMAP的死循环