Ammar's Blog
微信号：aicjaish
首页 标签 分类 归档 留言 关于
HashMap底层设计实现
|Java源码分析
字数总计: 2.7k|阅读时长: 10 分钟

HashMap 概述

HashMap 是 Map 族下我们最常用的一种，HashMap 是基于哈希表的 Map 接口的实现。存储的对象是 Entry(包含了 Key 和 Value)。

在 HashMap 中，会根据 hash 算法来计算 key-value的存储位置并进行快速存取，特别的，HashMap 最多只允许一条 Entry 的建为 NULL，多余的会覆盖，但允许多条 Entry 的值为 NULL。此外，HashMap是 Map 的一个非同步实现类。

虽然 HashMap 和 HashSet 实现的接口规范不同，但是他们底层的 Hash 存储机制完全相同。 实际上， HashSet 本身就是在 HashMap 的基础上实现的。

HashMap 在 JDK 中的定义(1.8版本)

HashMap 实现了 Map 接口，并集成了 AbstractMap 抽象类，和 AbstractCollection 抽象类在 Collection 族的作用类似。AbstractMap 提供了 Map 接口的骨干实现。 以最大限度的减少实现 Map 接口所需的工作，

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

HashMap 的构造函数

HashMap 一共提供了四个构造函数，其中默认无参的构造函数和参数为 Map 的构造函数为 Java Collection Framework 规范的推荐实现，其余两个构造函数则是 HashMap 专门提供的。

HashMap()

该构造函数，构造一个具有 > 默认初始容量(16)和默认负载因子(0.75)的空 HashMap，1.8版本中，对其进行了优化，改为put时才会创建 table[]。

1
2
3
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

HashMap(int initialCapacity, float loadFactor)

该构造函数意在构造一个指定初始容量和指定负载因子的空 HashMap，赋值时才创建 table[]

1
2
3
4
5
6
7
8
9
10
11
12
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0) // 初始容量不能小于0
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY; // 初始容量不能超过2^30
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) // 负载因子不能小于0
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

HashMap(int initialCapacity)

HashMap(Map<? extends K,? extends V> m)

该构造器意在构造一个与指定 Map 具有相同映射的 HashMap， 初始容量不小于16，具体容量依赖指定 Map的大小，负载因子是0.75。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

所谓初始容量和负载因子，这两个参数是影响 HashMap 性能的重要参数，容量表示哈希表中 table 数组的大小，负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间使用程度。

负载因子越大，散列表的填装度越高，反之越小

Hash 的相关概念

Hash 就是把任意长度的输入 pre-Input(预映射)，通过哈希算法，变换成固定长度的输出(通常是整型)，该输出是哈希值。 这种转换是一种压缩映射。简单的说，就是一种将任意长度的消息压缩到某一固定长度的消息摘要函数。

HashMap 的数据结构

哈希在数据结构中的应用

数组的特点：寻址容易，插入和删除困难。

链表的特点：寻址困难，插入和删除容易。

如果综合两者的特性，做出一种寻址容易，插入和删除也容易的数据结构，哈希表。哈希表有多种实现方式，最经典的一种叫做 拉链法 可以理解为 链表的数组。如下图所示：

左边是个数组，数组的每个成员是个链表，根据元素的自身特征，把元素分配到不同的链表中去，反过来，根据特征找出正确的链表，再从链表中找出正确的元素。

其中，根据元素特征计算元素数组下标的方法就是哈希算法。

哈希表适合快速查找、删除的基本数据结构：

  • hash 函数(哈希算法)的选择：针对不同的对象(字符串、整数等)具体的法系方法
  • 碰撞处理：常用的两种方式，一种是 open hashing，即拉链法
  • 另一种是 closed hashing，即开地址法

Java 中最常用的两种结构是数组和链表，几乎所有的数据结构都可以利用这两种来组合实现，实际上，HashMap 就是一个链表数组，以下是它的数据结构：

initialCapacity 就代表了该数组的长度。

Entry

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(Entry) 为 HashMap 的内部类，实现了 Map.Entry 接口，包含了键 key，值 value，下一个结点 next，以及hash值四个属性。 Node(Entry) 是构成哈希表的基石，是哈希表所存储的元素的具体形式。

HashMap 的快速存储

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) {
    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;
    // 如果 table 为空，就创建 table 数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // p  判断数组是否为空 如果为空 则在链表头部添加一个新的 node(Entry)。
    // (n - 1) & hash 等价于  取模运算，其效率更高 目的在于根据 key 的 hash 找到一个合适的 索引准备键值对
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果最后一个 entry.key.hash == 传入对象的 key.hash，e = p
        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 {
            // 在 table 的第 i 个位置上迭代，寻找 key 保存的位置
            for (int binCount = 0; ; ++binCount) {
                // 没有找到，创建一个新的 Node(Entry)，
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 判断当前链上是否存在 hash 值相同，且 key 值相等的映射，若存在 则直接 break
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 如果没找到，则将p指向下一个node
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            // 直接覆盖 value
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    // 将节点添加到链头
    afterNodeInsertion(evict);
    return null;
}

正如 JDK 官方对该方法的描述那样，使用 hash() 方法对一个对象的 hashCode 进行重新计算，是为了防止质量低下的 hashCode() 函数实现。 由于 hashMap 的支撑数组长度总是 2 的幂次，通过右移可以使得低位的数据尽量不同，使得 hash 值分布均匀。

通过上述 hash() 方法计算得到的 Key 的 hash 值后，怎么才能保证元素均匀分布到 table 的每个桶中？我们会想到取模， 但是取模效率低， HashMap 是通过 t = (hash & (length - 1))处理，简单而高效。

将新的创建的 Entry 链入链表的表头。如果 HashMap 中元素的个数超过极限值，则容量扩大两倍。

随着 HashMap 中元素数量越来越多，发生碰撞的概率将越来越大，产生的子链长度也越来越长，这样会影响 HashMap 的存储速度，为了保证 HashMap 的效率，系统需要在某个临界点进行扩容，该临界点就是：
HashMap 中的元素数量在数值上等于 threshold(table 数组长度加载因子) 它需要重新计算这些元素在新 table 中的位置并进行复制处理。

如果能提前预知 HashMap 中元素的个数，那么在构造 HashMap 时预设元素的个数能够有效提高 HashMap 性能。

步骤：

  1. 若 oldCapacity 已达到最大值，直接将thresold 设为 Integer.Max_VALUE 然后返回
  2. 否则，创建一个更大的数组，将每条 Entry 重新哈希到新的数组中
    • 重哈希主要是一个重新计算原 HashMap 中的元素在新 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
/**
*
* Transfers all entries from current table to newTable
*/

void transfer( Entry[] newTable )
{
    /* 将原数组 table 赋给数组 src */
    Entry[] src = table;
    int newCapacity = newTable.length;
    /* 将数组 src 中的每条链重新添加到 newTable 中 */
    for ( int j = 0; j < src.length; j++ )
    {
        Entry<K, V> e = src[j];
        if ( e != null ) {
            src[j] = null; /* src 回收 */
            /* 将每条链的每个元素依次添加到 newTable 中相应的桶中 */
            do {
                Entry<K, V> next = e.next;
                /* e.hash指的是 hash(key.hashCode())的返回值; */
                int i = indexFor( e.hash, newCapacity );
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while ( e != null );
        }
    }
}

重哈希的步骤：

  1. 将原数组 table 赋值给 src
  2. 将数组 src 中的每条链重新添加到 newTable 中
    • 每条链中的每个元素依次添加到 newTable 中相应的索引中。
    • 将根据新的数组长度，对 hash(key.hashCode())的返回值进行重新分配索引

HashMap 的读取实现

相对 HashMap 的存储而言，读取就显得比较简单，HashMap 只需通过 key 的 hash 值定位到 table 数组的某个特定的索引，然后查找并返回 该 key 对应的 value 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public V get(Object key) {
	/* 若为null，调用getForNullKey方法返回相对应的value */
	if (key == null)
		/* 从table的第一个桶中寻找 key 为 null 的映射；若不存在，直接返回null */
		return (getForNullKey());
	/* 根据该 key 的 hashCode 值计算它的 hash 码 */
	int hash = hash(key.hashCode());
	/* 找出 table 数组中对应的桶 */
	for (Entry<K, V> e = table[indexFor(hash, table.length)];
			e != null;
			e = e.next) {
		Object k;
		/* 若搜索的key与查找的key相同，则返回相对应的value */
		if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
			return (e.value);
	}
	return (null);
}

步骤：

  1. 根据 key 的 hashCode 值计算它的 hash 码
  2. 根据 hash 码，找到 table 数组中对应的索引
  3. 再索引链表中 找到 key 相同的 Entry，返回 entry.value 即可
文章作者: Ammar
文章链接: http://lizhaoloveit.cn/2019/06/19/HashMap%E5%BA%95%E5%B1%82%E8%AE%BE%E8%AE%A1%E5%AE%9E%E7%8E%B0/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ammar's Blog！
Java
打赏
  • 微信
  • 支付宝
评论
繁