ToyanのBlog HomeArchivesTagsCategories
HashMap实现原理
|Java集合
Word count: 3.1k|Reading time: 12 min
关注点 结论
是否允许空 key和value都运行空
是否允许重复元素 key重复会覆盖，value允许重复
是否有序 无序
是否线程安全 非线程安全

HashMap的数据结构

在Java语言中，最基本的两种结构就是数组和模拟指针（引用），所有的数据结构都可以使用这两个基本结构来构造。HashMap实际就是一个"链表散列"的数据结构，即数组与链表的结合体。

从上图可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。

首先看一下HashMap的一个存储单元Node：

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
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) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

有上面代码可以看出，Node就是数组中的元素，每个Map.Entry其实就是一个Key-value对，它持有一个指向下一个元素的引用，这就构成了链表。

功能实现-方法

确定哈希桶数组索引位置

不管增加、删除、查找键值对，定位到哈希桶数组的位置都是关键的一步，而定位数组索引的主要方法如下。

1
2
3
4
5
6
7
8
9
10
11
12
// jdk1.8 & jdk1.7
static final int hash(Object key) {
    int h;
    // 第一步：h = key.hashCode() 取hashCode值
    // 第二步：h ^ (h >>> 16)     高位参与运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
static int indexFor(int h, int length) {
     // 第三步: 取模运算
     return h & (length-1);  
}

这里Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算

对于任意给定的对象，只要它的hashCode()值相同，那么调用hash()方法中所计算得到的hash码总是相同的。我们首先想到就是把hash值对数组长度求模，这样就保证了元素的分布相对比较均匀。但是，求模运算时间耗费较大，所以采用了indexFor()方法来计算该对象应该保存在table数组中的哪个索引处。

这个方法非常巧妙，它通过h & (table.length - 1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h & (length - 1)运算等价于对length取模，也就是h % length，但是&比%具有更高的效率。

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

如下图，其中n为table的长度。

添加与修改数据

由于Java8对hashMap底层进行了优化，当链表长度大于8时，转换为红黑树进行处理，因此以下采用了美团点评技术团队的讲解。

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

步骤一：判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

步骤二：根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

步骤三：判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

步骤四：判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

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

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

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
public V put(K key, V value) {
    // 对key的hashCode()做hash
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 步骤一：tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤二: 计算index,并对null进行处理 
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 步骤三：节点key存在，直接覆盖value
        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转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // key已经存在直接覆盖value
                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;
    // 步骤六：超过最大容量就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

删除数据

下面是Java8中删除数据源代码的分析：

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
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 步骤一：找到要删除数组元素为p
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 步骤二：数组元素p存在，表示要删除的节点node赋为p
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 数组元素p是链表，则将链表的下一个节点赋给节点e
        else if ((e = p.next) != null) {
            // 步骤三：如果p为红黑树，则调用方法找到要删除的节点赋给node
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 步骤四：如果为链表，则找到对应要删除的节点赋给node
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                            (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 如果找到要删除的节点node
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            // 步骤五：判断此时数组元素的类型，并删除对应的节点node
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

HashMap的其他相关讲解

扩容机制

扩容就是重新计算容量，当HashMap中无法容纳更多的元素时，就要扩大数组的长度，以便容纳更多的元素。由于Java中的数组是无法自动扩容的，所以要使用一个新的数组来代替已有的容量小的数组。

下面我们分析resize()方法的源码，由于Java8引入了红黑树，因此还采用Java7的源码进行分析。

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
// 传入新的容量
void resize(int newCapacity) {
    // 引用扩容前的Entry数组
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    // 扩容前的数组大小如果已经达到最大(2^30)了     
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // 修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 初始化一个新的Entry数组
    Entry[] newTable = new Entry[newCapacity];
    // 将数据转移到新的Entry数组里
    transfer(newTable);
    // HashMap的table属性引用新的Entry数组
    table = newTable;
    // 修改阈值
    threshold = (int)(newCapacity * loadFactor);
}
// 将原有Entry数组的元素拷贝到新的Entry数组里
void transfer(Entry[] newTable) {
    // src引用了旧的Entry数组
    Entry[] src = table;                
    int newCapacity = newTable.length;
    // 遍历旧的Entry数组
    for (int j = 0; j < src.length; j++) {
        // 取得旧Entry数组的每个元素
        Entry<K,V> e = src[j];           
        if (e != null) {
            // 释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                // 重新计算每个元素在数组中的位置
                int i = indexFor(e.hash, newCapacity); 
                e.next = newTable[i]; // 标记[1]
                newTable[i] = e;      // 将元素放在数组上
                e = next;             // 访问下一个Entry链上的元素
            } while (e != null);
        }
    }
}

newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一个位置上新元素总会被放在链表的头部位置；这样先放在一个索引的元素最终会放在Entry链的尾部（如果发生了hash冲突），这一点Java8与其不同。由于重新计算了hash值，所以最终可能放在新数组的不同位置。

下面举个例子简单说明一下扩容的原理。我们采用的hash算法就是key对数组的长度取模。其中哈希桶数组table数组的长度size=2，put的顺序是3、7、5。在mod 2后都在table[1]发生了冲突。这里假设负载因子loadFactor=1，即当键值对实际大小size大于table的实际大小时进行扩容。下面是resize的过程示意图。

Java8中对新数组的索引计算采用了更加简洁的算法，不需要每次去计算hash值；而且在旧链表迁移到新链表的时候，如果新表的数组索引位置相同，则链表元素会倒置，而Java8则不会，详细解析可以见tech.meituan.com/java-hashmap.html

HashMap的table是transient的

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

由于table采用了transient修饰，也就是表示其不可以被序列化，它的原因如下：
HashMap是基于hashCode的，hashcode作为Object的方法，是native修饰的

1
public native int hashCode();

这意味着hashCode与底层相关，对于不同平台的虚拟机，会有不用的hashCode实现方式，也就是同一个对象在不同的平台下会有不同的hashcode值。

由于Java的跨平台特性，如果table不用transient修饰，在虚拟机A下的程序在虚拟机B下就会造成无法正常运行，这样就失去了其跨平台的意义，所以为了避免这样的情况，Java自己重写了其序列化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
50
private void writeObject(java.io.ObjectOutputStream s)
    throws IOException {
    int buckets = capacity();
    // Write out the threshold, loadfactor, and any hidden stuff
    s.defaultWriteObject();
    s.writeInt(buckets);
    s.writeInt(size);
    internalWriteEntries(s);
}

private void readObject(java.io.ObjectInputStream s)
    throws IOException, ClassNotFoundException {
    // Read in the threshold (ignored), loadfactor, and any hidden stuff
    s.defaultReadObject();
    reinitialize();
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new InvalidObjectException("Illegal load factor: " +
                                            loadFactor);
    s.readInt();                // Read and ignore number of buckets
    int mappings = s.readInt(); // Read number of mappings (size)
    if (mappings < 0)
        throw new InvalidObjectException("Illegal mappings count: " +
                                            mappings);
    else if (mappings > 0) { // (if zero, use defaults)
        // Size the table using given load factor only if within
        // range of 0.25...4.0
        float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
        float fc = (float)mappings / lf + 1.0f;
        int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
                    DEFAULT_INITIAL_CAPACITY :
                    (fc >= MAXIMUM_CAPACITY) ?
                    MAXIMUM_CAPACITY :
                    tableSizeFor((int)fc));
        float ft = (float)cap * lf;
        threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
                        (int)ft : Integer.MAX_VALUE);
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
        table = tab;

        // Read the keys and values, and put the mappings in the HashMap
        for (int i = 0; i < mappings; i++) {
            @SuppressWarnings("unchecked")
                K key = (K) s.readObject();
            @SuppressWarnings("unchecked")
                V value = (V) s.readObject();
            putVal(hash(key), key, value, false, false);
        }
    }
}

参考资料

Author: Toyan
Link: https://toyan.top/hashMap/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Java
支付宝打赏
微信打赏