HashMap的实现

搜索文档…
HashMap的实现
0x00 背景知识
首先HashMap是基于hash表的，hash表的相关知识及其存储原理，可以参考我之前写的一篇文章：查找算法总结，要着重看此文章关于冲突处理所讲述的拉链法。
我们仅在这稍微明确一点概念：首先对于拉链式的hash表，其是由数组和链表共同组成的，当然Java中还引入了红黑树，当链表长度大于8时，将链表转为红黑树以提高查找效率。我们先来看上面的这个图，保存这个hash表的数组称之为桶（bucket），而每个桶中保存了一系列的数据入口（entries）。
同理，我们在这明确一个概念“等同”：我们假定如果两个对象其hashCode相同，且任一一个调用equals方法与另一个返回true，即认为两个对象等同。
同时，在HashMap中有如下几个量需要注意，代码如下：
1
/**
2
 * The number of key-value mappings contained in this map.
3
 */
4
// MAP中所包含的键值对的数量
5
transient int size;
6
​
7
/**
8
 * The next size value at which to resize (capacity * load factor).
9
 *
10
 * @serial
11
 */
12
// (The javadoc description is true upon serialization.
13
// Additionally, if the table array has not been allocated, this
14
// field holds the initial array capacity, or zero signifying
15
// DEFAULT_INITIAL_CAPACITY.)
16
// 阈值，超过此阈值就会诱发桶的扩容操作，值为：桶的容量乘以装填因子
17
int threshold;
18
​
19
/**
20
 * The load factor for the hash table.
21
 *
22
 * @serial
23
 */
24
// 装填因子
25
final float loadFactor;
Copied!
HashMap和HashTable的区别
首先，HashMap是非线程安全的，而HashTable则是线程安全的，也因此，HashMap的效率较高。除此之外，在HashMap中null可以用来作为键，而HashTable则不可以，否则抛出NullPointerException。
HashMap和HashSet的区别
HashSet底层基于HashMap实现，其实现了Set接口，仅用来存储对象而不是键值对。而且HashSet较HashMap效率低。
HashMap的长度为什么是2的幂次方
因为经计算出来的hash值需要对数组长度进行取余运算，然后用余数定位其在hash表中的位置，为了优化取余运算的效率，人们发现取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(\&)操作，即：hash%length​等价于hash\&(length-1)，前提是length是2的n次方，采用二进制位操作\&，相对于%能够提高运算效率。
0x01 put方法
先来看一张流程图：
图片非原创，来自文章：HashMap原理深入理解​
正好我们就着源代码来说说这张图，首先我们来看put方法的源代码：
1
public V put(K key, V value) {
2
    return putVal(hash(key), key, value, false, true);
3
}
Copied!
其直接将工作转交至了putVal方法中，我们直接来看putVal的代码：
1
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
2
                boolean evict) {
3
    // 如果桶为空或者长度为0的话，那么调用resize方法对其进行扩容
4
    Node<K,V>[] tab; Node<K,V> p; int n, i;
5
    if ((tab = table) == null || (n = tab.length) == 0)
6
        n = (tab = resize()).length;
7
    // 通过(n - 1) & hash计算当前元素对应在table数组（桶）中的下标
8
    // 其中n为桶的长度，hash为依据key所计算的hash码值
9
    // 如果table数组中此项为空，意味着没有冲突发生
10
    // 那就直接在此项处新建一个Node直接将其插入
11
    if ((p = tab[i = (n - 1) & hash]) == null)
12
        tab[i] = newNode(hash, key, value, null);
13
    // 如果桶中已经有了至少一个元素
14
    else {
15
        Node<K,V> e; K k;
16
        // 首先判断链表的第一个结点与当前所插入的结点的`key`是否等同
17
        // 其中key的hash相同并且equals方法返回true被认为等同
18
        if (p.hash == hash &&
19
            ((k = p.key) == key || (key != null && key.equals(k))))
20
            // 如果等同的话，则将标记e指向p
21
            e = p;
22
        // 如果桶的entry类型为TreeNode的话
23
        else if (p instanceof TreeNode)
24
            // 那就调用红黑树的插入方法，将此键值对插入
25
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
26
        // 否则调用链表的插入方法，目标在链表尾部插入此结点
27
        else {
28
            for (int binCount = 0; ; ++binCount) {
29
                // 如果抵达链表尾部
30
                if ((e = p.next) == null) {
31
                    // 插入新结点
32
                    p.next = newNode(hash, key, value, null);
33
                    // 如果插入后链表的长度大于TREEIFY_THRESHOLD
34
                    // 即调用treeifyBin方法将链表变为红黑树
35
                    // 注：TREEIFY_THRESHOLD默认为8
36
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
37
                        treeifyBin(tab, hash);
38
                    break;
39
                }
40
                // 如果在链表中找到了和插入键值对key等同的结点则退出循环
41
                if (e.hash == hash &&
42
                    ((k = e.key) == key || (key != null && key.equals(k))))
43
                    break;
44
                p = e;
45
            }
46
        }
47
        // 如果标记e不为null的话
48
        // 即在当前hash表中找到了与所要插入的键值对的key相同的结点
49
        if (e != null) { // existing mapping for key
50
            V oldValue = e.value;
51
            // onlyIfAbsent即为是否仅在oldValue为null的情况下更新键值对
52
            // 这个参数在put方法中被默认给定为false
53
            if (!onlyIfAbsent || oldValue == null)
54
                e.value = value;
55
            afterNodeAccess(e);
56
            return oldValue;
57
        }
58
    }
59
    ++modCount; 
60
    // 键值对数量超过阈值时，调用resize方法进行扩容对桶进行扩容
61
    if (++size > threshold)
62
        resize();
63
    afterNodeInsertion(evict);
64
    return null;
65
}
Copied!
在上述两个代码中，我们可以看到两个方法afterNodeAccess和afterNodeInsertion这两个方法在HashMap里面的实现是空的，在此处什么都不做，其注释中写道：Callbacks to allow LinkedHashMap post-actions，即适用于LinkedHashMap实现一些后置功能的回调函数。
JDK7 put方法为什么线程不安全
以下内容仅适用于JDK7之前的版本，即对链表的插入方法为头插法，JDK8以后，链表的插入方法改为了尾插法，从此之后就不存在这个问题了。
众所周知，HashMap不是线程安全的，多线程的情况下操作HashMap的put操作有可能导致死循环，原因在于HashMap扩容使用的resize方法，由于扩容是新建一个数组，然后复制原数据到数组，由于数组下标挂有链表，所以需要复制链表，但多线程操作有可能导致环形链表。
我们先来看JDK7 HashMap实现中的transfer方法：
1
void transfer(Entry[] newTable, boolean rehash) {
2
    int newCapacity = newTable.length;
3
    for (Entry<K,V> e : table) {
4
        while(null != e) {
5
            Entry<K,V> next = e.next;
6
            if (rehash) {
7
                e.hash = null == e.key ? 0 : hash(e.key);
8
            }
9
            int i = indexFor(e.hash, newCapacity);
10
            e.next = newTable[i]; // 才用头插入，在链表头部插入元素
11
            newTable[i] = e; // 线程执行完上一行后，在此处挂起
12
            e = next; // 循环遍历链表内元素
13
        }
14
    }
15
}
Copied!
我们假设没有执行resize之前Entry数组的结构如下：
则其在单线程的情况下，正确执行扩容操作后的样子如下：
好了，现在我们来看多线程的情况，假设线程A执行扩容操作，在上述代码片中标记部分线程A被挂起，则目前线程A内的状态如下：
这个时候线程B介入了，线程B也想进行扩容操作，而且恰好线程B的扩容操作还操作完了，则线程B内的状态如下：
这是对于值为3, 7, 5的这三个对象来说，其状态为：
1
tab[1]=5, 5.next=null
2
tab[3]=7, 7.next=3, 3.next=null
Copied!
然后CPU又切换时间片到线程A，线程A继续运行，在Java中代码中的临时变量e和next实际上都为引用类型变量。线程A继续操作，线程A的newTable变为了如下状态：
继续循环：
1
e=7
2
next=e.next ----> next=3【从主存中取值】
3
e.next=newTable[3] ----> e.next=3（7.next=3）【从主存中取值】
4
newTable[3]=e ----> newTable[3]=7
5
e=next ----> e=3
Copied!
此时状态如下：
e=3于是又再一次进入循环：
1
e=3
2
next=e.next ----> next=null
3
e.next=newTable[3] ----> e.next=7（3.next=7）
4
newTable[3]=e ----> newTable[3]=3
5
e=next ----> e=null
Copied!
此时线程状态如下，并结束循环：
此时newTable[3]中所保存的链表即成了循环链表，当查找一个元素，假设说8，经计算indexOf(8) = 3，那么将会在table[3]所存储链表中查找，此时get(8)操作即为一个死循环。
JDK8之后的put方法为什么线程不安全？
JDK8中链表的插入方法由JDK7中的头插入改为了尾插入，所以上面会导致死循环的那个问题在JDK8中已经不复存在了。但HashMap依旧是线程不安全的，因为写入丢失。
现在考虑一种情况，2个线程同时要向一个HashMap中插入元素，而这两个元素恰好又有相同的hash值，假设这个hash值所对应的数组下标所在位置原先是没有元素的，那线程1直接进行赋值，然后CPU切换到了线程2，线程2又进行了一次直接复制，线程2赋的值覆盖了线程1的值，导致了写入丢失的问题。
其次，如果线程1和2向HashMap插入元素时，需要进行扩容操作的话，线程1和线程2都会各自生成各自的newTab，然后最后tab = resize()，到最后table里面只保存了最后一个线程的newTab，其余线程的均会丢失。
0x02 get方法
先来看一下get方法：
1
public V get(Object key) {
2
    Node<K,V> e;
3
    return (e = getNode(hash(key), key)) == null ? null : e.value;
4
}
Copied!
其主要工作在getNode方法中，用于通过键值hash和键值对象获取Node，如果其得到的值为null那就返回null，否则返回Node对象的value，我们着重来看getNode方法：
1
final Node<K,V> getNode(int hash, Object key) {
2
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
3
    // 首先检查桶是否为空，如果不为空的话，检查键值所在桶的位置是否为空
4
    // 如果二者均为空的话，返回null查找失败
5
    if ((tab = table) != null && (n = tab.length) > 0 &&
6
        (first = tab[(n - 1) & hash]) != null) {
7
        // 检查第一个是否等同
8
        if (first.hash == hash && // always check first node
9
            ((k = first.key) == key || (key != null && key.equals(k))))
10
            return first;
11
        if ((e = first.next) != null) {
12
            // 如果桶的entry类型为TreeNode的话
13
            if (first instanceof TreeNode)
14
                // 在entry所指定的红黑树中查找相关键值
15
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
16
            // 在链表中查找相关键值
17
            do {
18
                if (e.hash == hash &&
19
                    ((k = e.key) == key || (key != null && key.equals(k))))
20
                    return e;
21
            } while ((e = e.next) != null);
22
        }
23
    } 
24
    // 查找失败
25
    return null;
26
}
Copied!
0x03 remove方法
remove方法用于从HashMap中移除一个元素，代码如下：
1
public V remove(Object key) {
2
    Node<K,V> e;
3
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
4
}
Copied!
其主要工作在removeNode中，我们来看其源代码：
1
final Node<K,V> removeNode(int hash, Object key, Object value,
2
                            boolean matchValue, boolean movable) {
3
    Node<K,V>[] tab; Node<K,V> p; int n, index;
4
    // 要删除就要判断被删除的键值对在hash表中是否存在
5
    if ((tab = table) != null && (n = tab.length) > 0 &&
6
        // 判断被删除元素hash码值是否在表中存在
7
        (p = tab[index = (n - 1) & hash]) != null) {
8
        Node<K,V> node = null, e; K k; V v;.
9
        // p.hash在Node<K,V>构造时就已经赋值，详见其构造函数
10
        // 判断被删除元素是否在拉链中存在
11
        if (p.hash == hash &&
12
            ((k = p.key) == key || (key != null && key.equals(k))))
13
            node = p;
14
        else if ((e = p.next) != null) {
15
            // 在树中寻找被删除元素
16
            if (p instanceof TreeNode)
17
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
18
            else {
19
                // 在拉链中顺序寻找被删除元素
20
                do {
21
                    if (e.hash == hash &&
22
                        ((k = e.key) == key ||
23
                            (key != null && key.equals(k)))) {
24
                        node = e;
25
                        break;
26
                    }
27
                    p = e;
28
                } while ((e = e.next) != null);
29
            }
30
        }
31
        if (node != null && (!matchValue || (v = node.value) == value ||
32
                                (value != null && value.equals(v)))) {
33
            // 被删除元素存在的话
34
            if (node instanceof TreeNode)
35
                // 在树节点中删除
36
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
37
            // p代表了拉链的第一个位置
38
            else if (node == p)
39
                tab[index] = node.next;
40
            else
41
                p.next = node.next;
42
            ++modCount;
43
            --size;
44
            afterNodeRemoval(node);
45
            return node;
46
        }
47
    }
48
    // 被删除的键值对不存在，返回null
49
    return null;
50
}
Copied!
0x04 resize方法
1
final Node<K,V>[] resize() {
2
    Node<K,V>[] oldTab = table;
3
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
4
    int oldThr = threshold;
5
    int newCap, newThr = 0;
6
    if (oldCap > 0) {
7
        if (oldCap >= MAXIMUM_CAPACITY) {
8
            // 如果扩容前容量已经超出了所容许的最大容量
9
            // 那么提高门限值至int类型的最大值
10
            // 以防增加元素时再次触发resize操作
11
            threshold = Integer.MAX_VALUE;
12
            return oldTab; // 不再扩容
13
        }
14
        // 新容量翻番
15
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
16
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
17
            // 如果翻番后的容量仍小于所容许的最大容量的话
18
            // 门限值也翻番
19
            newThr = oldThr << 1; // double threshold
20
    }
21
    // 原容量==0 && 原门限值>0
22
    else if (oldThr > 0) // initial capacity was placed in threshold
23
        newCap = oldThr;
24
    // 原容量和原门限值均为0，则全部使用默认值初始化
25
    else {  // zero initial threshold signifies using defaults
26
        newCap = DEFAULT_INITIAL_CAPACITY;
27
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
28
    }
29
    // oldCap翻番后的newCap大于MAXIMUM_CAPACITY也会使newThr=0
30
    if (newThr == 0) {
31
        float ft = (float)newCap * loadFactor;
32
        // 如果说新的容量已经超过最大容量的话
33
        // 那新的门限值就设置为INT_MAX以后不再扩容
34
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
35
                    (int)ft : Integer.MAX_VALUE);
36
    }
37
    threshold = newThr;
38
    @SuppressWarnings({"rawtypes","unchecked"})
39
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
40
    table = newTab;
41
    // 复制现有表到新表
42
    if (oldTab != null) {
43
        for (int j = 0; j < oldCap; ++j) {
44
            Node<K,V> e;
45
            if ((e = oldTab[j]) != null) {
46
                oldTab[j] = null;
47
                if (e.next == null)
48
                    // 重新计算在新表中的位置
49
                    newTab[e.hash & (newCap - 1)] = e;
50
                else if (e instanceof TreeNode)
51
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
52
                else { // preserve order
53
                    // loHead和loTail标记的这个链表
54
                    // 表示插入到当前数组位置的元素们
55
                    Node<K,V> loHead = null, loTail = null;
56
                    // hiHead和hiTail标记的这个链表
57
                    // 表示插入到新数组位置的元素们
58
                    Node<K,V> hiHead = null, hiTail = null;
59
                    Node<K,V> next;
60
                    do {
61
                        next = e.next;
62
                        // 对于这个判断条件的理解请看下文
63
                        if ((e.hash & oldCap) == 0) {
64
                            // 扩容后的位置没有发生变化
65
                            // 在链表中顺序插入元素
66
                            if (loTail == null)
67
                                loHead = e;
68
                            else
69
                                loTail.next = e;
70
                            loTail = e;
71
                        }
72
                        else {
73
                            // 扩容后当前结点的位置需要变化
74
                            if (hiTail == null)
75
                                hiHead = e;
76
                            else
77
                                hiTail.next = e;
78
                            hiTail = e;
79
                        }
80
                    } while ((e = next) != null);
81
                    if (loTail != null) {
82
                        // 插入到当前数组位置
83
                        loTail.next = null;
84
                        // 有人看了下面的代码
85
                        // newTab[j + oldCap] = hiHead;
86
                        // 可能会疑惑这是否会产生覆盖问题
87
                        // 答案是不会，直接赋值不会产生覆盖问题，因为在下方的j + oldCap是始终大于等于oldCap的，而j是始终小于oldCap的
88
                        newTab[j] = loHead;
89
                    }
90
                    if (hiTail != null) {
91
                        // 插入到新数组位置
92
                        hiTail.next = null;
93
                        newTab[j + oldCap] = hiHead;
94
                    }
95
                }
96
            }
97
        }
98
    }
99
    return newTab;
100
}
Copied!
对判断条件(e.hash & oldCap) == 0的理解
扩容后重新计算元素在新表中的位置的时候，用到了一个非常巧妙的算法，首先我们每次重新计算，都是将原数组大小n乘以2。我们现在假设原数组大小为16，则新数组大小即为32，我们计算某hash值在数组中的位置时，使用的方法为e.hash & (n - 1)，当n翻一番的时候，这个产生的结果只可能出现2种情况，一种是不变，如下：
1
扩容前n为16时：
2
n-1          0000 0000 0000 0000 0000 0000 0000 1111
3
hash         1111 1111 1111 1111 0000 1111 0000 0101
4
hash & (n-1) 0000 0000 0000 0000 0000 0000 0000 0101
5
扩容后n为32时：
6
n-1          0000 0000 0000 0000 0000 0000 0001 1111
7
hash         1111 1111 1111 1111 0000 1111 0000 0101
8
hash & (n-1) 0000 0000 0000 0000 0000 0000 0000 0101
Copied!
首先一个对象的hash值只与这个对象有关，与其他因素无关，所以扩容前后hash值是不变的，变的只有n-1的值，在上例中，扩容前后的这个元素在数组中的位置依旧保持不变
另一种是结果也跟着移动2次幂的位置，如下：
1
扩容前n为16时：
2
n-1          0000 0000 0000 0000 0000 0000 0000 1111
3
hash         1111 1111 1111 1111 0000 1111 0001 0101
4
hash & (n-1) 0000 0000 0000 0000 0000 0000 0000 0101
5
扩容后n为32时：
6
n-1          0000 0000 0000 0000 0000 0000 0001 1111
7
hash         1111 1111 1111 1111 0000 1111 0001 0101
8
hash & (n-1) 0000 0000 0000 0000 0000 0000 0001 0101
Copied!
在这种情况下，我们只需要看新增的那个bit位是0还是1就好了，是0的话索引没变，是1的话索引变成原索引加oldCap。
我们发现新增的那个bit位的位置实际上就是oldCap（n）的位置，如下：
1
n            0000 0000 0000 0000 0000 0000 0001 0000
2
扩容后数组位置不变的情况：
3
hash         1111 1111 1111 1111 0000 1111 0000 0101
4
扩容后数组位置发生变化的情况：
5
hash         1111 1111 1111 1111 0000 1111 0001 0101
Copied!
我们发现只要判断hash & n是否等于1就可以判断出扩容之后的位置是否发生变化来，由此判断条件(e.hash & oldCap) == 0的意思即为判断扩容后的位置是否发生变化。
0x05 hash方法
下面再来看一下其采用的Hash函数：
1
static final int hash(Object key) {
2
    int h;
3
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4
}
Copied!
显然，通过其hash函数所得的hash码值与这个对象的hashCode有着直接的关联，这就产生了一个问题，首先hashCode的返回值是依据当前对象在JVM中的内存地址算出来的，当我们用一个自定义类的对象来做key的话，同样内容的两个对象，get操作就会出现问题，看代码：
1
/* == Main.java == */
2
public class Main {
3
    public static void main(String[] args) {
4
        Person boy = new Person("Qun", 22);
5
        Person girl = new Person("Hui", 23);
6
        HashMap<Person, Person> couples = new HashMap<Person, Person>();
7
        couples.put(boy, girl);
8
        Person someone = new Person("Qun", 22);
9
        System.out.println(couples.get(someone));
10
    }
11
}
12
​
13
/* == Person.java == */
14
public class Person {
15
    private String name;
16
    private int age;
17
​
18
    public Person(String name, int age) {
19
        this.name = name;
20
        this.age = age;
21
    }
22
​
23
    // 省略getter, setter
24
}
Copied!
get函数会返回null，someone和boy虽说看上去内容是一样的，但是实际上是两个对象，二者的hashCode会返回不一样的值，所得到的用于查找的hash码值也会不一样，所以get失败。好，我们来重写一下Person类的hashCode让他由属性name和age来决定，代码如下：
1
@Override
2
public int hashCode() {
3
    return name.hashCode() + age;
4
}
Copied!
TL;DR
String类型的对象所产生的hashCode值是由其所保存的字符串决定的，字符串相同，hashCode值也相同，字符串不同，hashCode值也不同。我们可以在其文档中，找到相关hashCode值产生算法的描述：
1
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
Copied!
这样就可以保证两个内容相同的Person对象产生的hashCode也相同了，让我们重新运行代码，依旧输出null，经检查发现get函数不仅会判断key的hash值相同，同时也会使用equals函数来判断两个对象是否等同，重写equals函数如下：
1
@Override
2
public boolean equals(Object obj) {
3
    return obj instanceof Person && 
4
             this.name.equals(((Person) obj).name) &&
5
               this.age == ((Person) obj).age;
6
}
Copied!
这样程序就返回了正确的结果。由此可以得到一个结论，查找HashMap时，get操作会先通过hashCode计算其相关的hash码值，当这个hash码值相同时，会调用equals方法来检验当前对象与数组中hash码值相同的对象是否等同，如果等同即会返回其关联的value。
这样的hash计算方法产生的hash碰撞的概率在其源码里有详细的介绍，摘抄如下：
Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) pow(0.5, k) / factorial(k)). The first values are: 0: 0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 8: 0.00000006 more: less than 1 in ten million
大意是在理想状况下，链表内元素的个数是服从泊松分布（Poisson distribution）的，其还给出了链表内元素个数所出现的概率，例如链表内有1个元素的概率是0.3032，超过8个元素的概率就在千万分之一了。也就说真正需要转化成红黑树的概率其实是很小的。
最近更新 8mo ago
复制链接
内容