Fork me on GitHub

Java 容器总结(三)

发表于 | 分类于 | 热度 ℃ | 字数统计 3,291 | 阅读时长 ≈ 15
Java 容器总结(三) —— HashMap

1、ArrayList 和 LinkedList，它们的一个共同特点是，查找元素的效率都比较低，都需要逐个进行比较，而 HashMap 它的查找效率则要高的多。Map 表示映射关系，实现 Map 接口有多种方式，HashMap 实现的方式利用了 Hash。

2、Map 接口
Map 按照键存储和访问值，键不能重复，即一个键只会存储一份，给同一个键重复设值会覆盖原来的值。使用 Map 可以方便地处理需要根据键访问对象的场景。数组、ArrayList、LinkedList 可以视为一种特殊的 Map，键为索引，值为对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public interface Map<K,V> {
    V put(K key, V value);
    V get(Object key);
    V remove(Object key);
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    void putAll(Map<? extends K, ? extends V> m);
    void clear();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
    interface Entry<K,V> {
        K getKey();
        V getValue();
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
    }
    boolean equals(Object o);
    int hashCode();
}

Map 接口有两个类型参数，K 和 V，分别表示键 (Key) 和值 (Value) 的类型。在 HashMap 中，key 相同的依据是，要么都为 null，要么 equals 方法返回 true。Map.Entry 是一个嵌套接口，定义在 Map 接口内部，表示一条键值对。

注意：keySet()/values()/entrySet() 有一个共同的特点，它们返回的都是视图，不是拷贝的值，基于返回值的修改会直接修改 Map 自身。 Set 是一个接口，表示的是数学中的集合概念，即没有重复的元素集合。它扩展了 Collection，但没有定义任何新的方法，不过，它要求所有实现者都必须确保 Set 的语义约束，即不能有重复元素。Map 中的键是没有重复的，所以 ketSet() 返回了一个 Set。

3、HashMap 主要围绕以下几个变量来实现的，几乎所有的操作都是在操作以下几个变量：

1
2
3
4
5
6
7
8
// table 是一个 Node (单向链表) 类型的数组，数组中的每个元素都是一个单向链表，链表中的每个节点表示一个键值对，Node 是一个内部类
transient Node<K,V>[] table;
// size 表示实际键值对的个数
transient int size;
// 扩容的阈值
int threshold;
// loadFactor 是负载因子，表示整体上 table 被占用的程度，是一个浮点数，默认为 0.75，可以通过构造方法进行修改
final float loadFactor;

4、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
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    // table 是一个 Node 类型的数组，其中的每个元素指向一个单向链表，链表中的每个节点表示一个键值对，Node 是一个内部类
    transient Node<K,V>[] table;
    // size 表示实际键值对的个数
    transient int size;
    int threshold;
    final float loadFactor;

    // 静态内部类，实现了 Map.Entry 接口
    static class Node<K,V> implements Map.Entry<K,V> {
        // hash 是 key 的哈希值，直接存储 hash 值是为了在比较的时候加快计算
        final int hash;
        final K key;
        V value;
        // next 指向下一个 Node 节点，即链表元素的下一个节点
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            // 直接存储 hash 值是为了在比较的时候加快计算
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

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

table 默认为 null，当添加键值对后，table 就不是空表了，它会随着键值对的添加进行扩展，扩展的策略类似于 ArrayList，添加第一个元素时，默认分配的大小为 16，不过，并不是 size 大于 16 时再进行扩展，下次什么时候扩展与 threshold 有关。threshold 表示阈值，当键值对个数 size 大于等于 threshold 时考虑进行扩展。一般而言，threshold 等于 table.length 乘以 loadFactor。loadFactor 是负载因子，表示整体上 table 被占用的程度，是一个浮点数，默认为 0.75，可以通过构造方法进行修改。

5、put(K key, V value) 方法源码解析

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
// 调用 HashMap 的 put() 方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
-------------------------
// 获取 key 的 hash 值
static final int hash(Object key) {
    int h;
    // 做异或 和 无符号右移的位运算得到最后的 hash 值
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
------------------------
// onlyIfAbsent：if true, don't change existing value
// evict：if false, the table is in creation mode.
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 为 null，表示第一次保存时，调用 resize() 方法进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 注意：(n - 1) & hash 用来计算应该将这个键值对放到 table 的哪个位置
    // HashMap 中，length 为 2 的幂次方，(n - 1) & hash 等同于求模运算：h % length    
    // 找到了保存位置 i，table[i] 指向一个单向链表，接下来，就是在这个链表中逐个查找是否已经有这个键了
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 无哈希冲突,创建新的 Node
        tab[i] = newNode(hash, key, value, null);
    else {
        // 进到这里表明有哈希冲突了
        Node<K,V> e; K k;
        // 节点 key 存在,直接覆盖 value，保证 key 的唯一性
        // 而比较的时候，是先比较 hash 值，hash 相同的时候，再使用 equals 方法进行比较。注意：比较的时候先比较 hash，再比较地址值，最后才使用 equals()
        // 因为 hash 是整数，比较的性能一般要比 equals 比较高很多，hash 不同，就没有必要调用 equals 方法了，这样整体上可以提高比较性能
        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] 值相同的情况
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 如果 p 后的 Node 为空，表明当前链表只有一个结点
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 链表长度达到 8，改变链表结构为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                // key 相同则跳出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 就是移动指针方便继续取 p.next，因为前面有 e = p.next 这样的赋值
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 根据规则选择是否覆盖value
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 扩容检测，并且此处完成对 size 加 1
    if (++size > threshold)
        // size 大于阈值则扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}
------------------------
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;
}

6、get() 方法源码解析

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 V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
--------------------
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) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof 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);
        }
    }
    return null;
}

7、remove() 方法源码解析

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
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;
    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;
        // 要删除的结点是头结点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 不是要删除的结点头结点的情况
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                // 红黑树节点
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            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 表示要删除的结点，获取到 node 后，分情形删除节点
        // node 不为 null 的情况下，再判断 value 是否一致，相当于双重保障吧
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                // 红黑树结点删除，牵扯到由红黑树变链表的逻辑
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 头结点    
            else if (node == p)
                tab[index] = node.next;
            // 非头结点，注意：node 为要删除的结点，p 为要删除结点的前一个结点    
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

8、HashMap 的主结构类似于一个数组，添加值时通过 key 确定储存位置。当发生冲突时,相同 hash 值的键值对会组成链表。在 JDK 1.8 以前，数组 + 链表的组合形式大部分情况下都能有不错的性能效果。但是在极端情况下，一组「比如经过精心设计的」键值对都发生了冲突，这时的哈希结构就会退化成一个链表，使 HashMap 性能急剧下降。所以在 JDK 1.8 之后，采用数组+链表+红黑树「链表长度大于 8 时转为红黑树」的方式对元素进行存储。

9、HashMap 实现原理小结
HashMap 的基本实现原理，内部有一个数组 table，每个元素 table[i] 指向一个单向链表，根据键存取值，用键算出 hash，取模得到数组中的索引位置 buketIndex，然后操作 table[buketIndex] 指向的单向链表。

存取的时候依据键的 hash 值，只在对应的链表中操作，不会访问别的链表，在对应链表操作时也是先比较 hash 值，相同的话才用 equals 方法比较，这就要求，相同的对象其 hashCode() 返回值必须相同，如果键是自定义的类，就特别需要注意这一点。这也是hashCode和equals方法的一个关键约束。

HashMap 它实现了 Map 接口，可以方便的按照键存取值，它的实现利用了哈希，可以根据键自身直接定位，存取效率很高。

10、HashMap 特点分析
HashMap 实现了 Map 接口，内部使用数组+链表+红黑树和哈希的方式进行实现，这决定了它有如下特点：

  • 根据键保存、获取、删除操作的效率都很高，为 O(1)，每个单向链表往往只有一个或少数几个节点，根据 hash 值就可以直接快速定位。
  • HashMap 中的键值对没有顺序，因为 hash 值是随机的。

综上所述，HashMap 适用于不要求顺序，经常需要根据键存取值的场景。

11、根据哈希值存取对象、比较对象是计算机程序中一种重要的思维方式，它使得存取对象主要依赖于自身哈希值，而不是与其他对象进行比较，存取效率也就与集合大小无关，高达 O(1)，即使进行比较，也利用哈希值提高比较性能。

参考博客

Java 编程的逻辑 - 剖析 HashMap
Java8 HashMap 源码分析

-------------本文结束感谢您的阅读-------------

本文标题:Java 容器总结(三)

文章作者:Yan ChongSheng

发布时间:2018年08月23日

最后更新:2018年08月26日

原始链接:yanchongsheng.github.io/2018/08/23/Java-Java-Container-2018-08-23-Java容器总结-三/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

开启打赏模式