JanGin's BLOG
主页
归档
标签
分类
avatar
文章
42
标签
43
分类
15
主页
归档
标签
分类
目录
  1. 一. 类的继承体系
  2. 二. HashMap的底层数据结构
  3. 三. HashMap的一些重要属性和概念
  4. 四. HashMap 的常用方法源码分析
    1. 4.1 put 方法
    2. 4.2 resize 方法
    3. 4.3 get 方法
    4. 4.4 hash 方法
HashMap的要点总结
|Java
字数总计:2.5k|阅读时长: 10 分钟

一. 类的继承体系

HashMap 是 Map<K, V> 接口的一种实现，此外HashMap还实现了 Serializable 和 Cloneable 接口， 是 Java 类库中提供的一种哈希表实现。

HashMap继承体系

和 HashTable 不同的是，HashMap的直接父类是 AbstractMap<K, V>， 而 HashTable 则直接继承于 Dictionary<K, V>.

HashMap 允许空的 key 和 value 值，而 HashTable 不允许空的 key 和 value 值。

二. HashMap的底层数据结构

HashMap的底层数据结构，用一句话概括就是 Node<K, V> 数组 table + 单个bucket后连着的单链表 （bucket 即数组 table 中的任意单个元素）。在 JDK1.8 之后有一处重大改进，那就是，当单个 bucket 之后的链表长度大于等于8时，单链表将转化为红黑树，此举可以将单链表的线性元素搜寻时间复杂度 O(n) 减少为红黑树的搜寻时间复杂度 O(log n).

Node<K , V> 是 HashMap 的静态内部类，实现了Map<K, V> 内建的 Map.Entry<K, V> 接口，一个Map.Entry<K, V>即代表了一对 Key-Value 键值对，也即 tables数组的元素类型。其源码如下：

java
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;		// 1
       final K key;		// 2
       V value;			// 3
       Node<K,V> next;		// 4

       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 内部类的源码可以看出，一个 Node 节点主要包含以下几个部分：

  1. 该节点通过计算所得的 Hash 值
  2. 该节点所存放的 Key
  3. 该节点所存放的 Key 对应的 Value
  4. 指向下一个 Node 节点的指针

于是乎，可以得到一个 HashMap 在 bucket 后接链表元素个数不长于8个时的整体数据结构大致长成这个样子：

HashMap底层结构

JDK 1.8 之后，当 bucket 后接链表长度大于8时，会进行 treeify 操作，使其结构变成如下形式：

treeify化后的HashMap

三. HashMap的一些重要属性和概念

  • 缺省的初始容量大小：
java
1
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4		// 默认 Node<K,V>[] table 的数组大小为16, 数字大小要求是2的幂次方
  • 缺省的负载因子:
java
1
static final float DEFAULT_LOAD_FACTOR = 0.75f;		// loadFactor 用来决定数组中已存元素个数占总体容量的多少比例时将进行扩容
  • 链表升级成红黑树结构的元素个数下限：
java
1
static final int TREEIFY_THRESHOLD = 8;
  • 红黑树退化成链表的元素个数上限：
java
1
static final int UNTREEIFY_THRESHOLD = 6;
  • 元素个数
java
1
transient int size;					// 当前哈希桶数组中一共拥有的元素个数
  • resize 的元素个数门槛
java
1
int threshold;			// capacity * load factor
  • 元素个数修改次数
java
1
private transient int modCount = 0;
  • 哈希集合的三个基本存储概念
名称 说明
table 存储所有节数据的数组
slot 哈希槽，即 table[i] 这个位置
bucket 哈希桶，即 table[i] 这个位置上所有元素形成的链表或树的集合

四. HashMap 的常用方法源码分析

4.1 put 方法
java
1
2
3
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

put 方法由 putVal方法具体实现，源码如下：

java
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
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果节点数组还未进行初始化，则先初始化， Node<K ,V>[] table 的懒加载
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 假设此处为StepA.　i = (n - 1) & hash　计算新插入的 Node 节点在数组中的存储位置
    // 这里的 n 代表哈希表的长度，哈希表习惯将长度设置为 2 的 n 次方，这样恰好可以保证 (n - 1) & hash 的计算得到的索引值总是位于 table 数组的索引之内
    // 如果位置上之前没有被放入元素，则直接生成一个 Node 放在此处
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 经过 StepA 处的计算之后，如果该位置已有元素，比较已有元素与新插入值的 hash 值来决定覆盖与否
        // 如果 hash 值相等并且 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 {// 走到这里，继续向后遍历当前计算所得数组 slot 位置上的后接链表，直到链表节点的 next 还未有节点指向，则直接 newNode() 方式插入，尾插法
            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;
                }
                // 如果找到了 hash 值和 key 都相等的节点，那就是它了，直接 break 退出遍历过程
                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;		// 记住 key 对应的旧值作为 put 方法的返回值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;	// 覆盖旧的 value 值
            afterNodeAccess(e);		// 此处是个空实现
            return oldValue;
        }
    }
    // 修改次数 + 1
    ++modCount;
    if (++size > threshold)
        resize();		// 扩容
    afterNodeInsertion(evict);		// 空实现
    return null;
}
4.2 resize 方法

在上面的 put 方法的源码中，可以看到当 map 中的元素个数达到 threshold 上限时，要进行 resize 扩容操作，resize 扩容的源码如下：

java
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
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;
            }
            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);
        }
        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;
                    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<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            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;
    }
4.3 get 方法

接下来看 get 方法的源码部分：

java
1
2
3
4
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;	// 找到Node节点，最终返回的是 Node 节点的 key 值对应的 value 值
}

get 方法先要找到对应的节点，其由 getNode 方法具体实现，getNode 方法源码如下：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {	// 同样先根据 hash 值计算出要找的节点在 bucket 数组中的索引位置
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))	// hash 值， key 值都相等，即认为找到了该节点，返回
            return first;
        if ((e = first.next) != null) {		// first.next != null, 说明有后接链表或者红黑树
            if (first instanceof TreeNode)	// 如果是 TreeNode类型，则转而去遍历红黑树来找到节点
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);	// 遍历后接链表来找到对应的 Node 节点，判断条件是 key 是否相等
        }
    }
    return null;	// 实在找不到就返回 null
}
4.4 hash 方法

每一次要定位到一个哈希槽，到需要先通过 hash 方法计算一遍节点对应的 hash 值，hash 方法的源码如下：

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

不难看出，就是直接取 key 的 hashCode() 再跟 [key 的 hashCode() 结果无符号右移16bit ] 后的结果进行异或。

为什么不直接取 hashCode() 得到的值而是还要加上异或操作呢？

假设要添加两个对象 a 和 b，如果数组长度是 16，这时对象 a 和 b 通过公式 (n - 1) & hash 运算，也就是 (16-1)＆a.hashCode 和 (16-1)＆b.hashCode，15 的二进制为 0000000000000000000000000001111，假设对象 A 的 hashCode 为 1000010001110001000001111000000，对象 B 的 hashCode 为 0111011100111000101000010100000，你会发现上述与运算结果都是 0。这样的哈希结果就太让人失望了，很明显不是一个好的哈希算法。但如果我们将 hashCode 值右移 16 位（h >>> 16 代表无符号右移 16 位），也就是取 int 类型的一半，刚好可以将该二进制数对半切开，并且使用位异或运算（如果两个数对应的位置相反，则结果为 1，反之为 0），这样的话，就能避免上面的情况发生。这就是 hash() 方法的具体实现方式。简而言之，就是尽量打乱 hashCode 真正参与运算的低 16 位。

文章作者: JanGin
文章链接: http://jangin.github.io/2021/06/30/key-points-of-hashmap/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 JanGin's BLOG！
HashMap
评论