HashMap, HashSet, ConcurrentHashMap 源码分析

HashMap 源码

Node 数组

HashMap 底层是由 Node 数组组成的，其中包括 key，value，hash 以及指向下个节点的 next

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
_/**_
_ * Basic hash bin node, used for most entries.  (See below for_
_ * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)_
_ */_
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;

        return o instanceof Map.Entry<?, ?> e
                && Objects._equals_(key, e.getKey())
                && Objects._equals_(value, e.getValue());
    }
}

扰动函数（hash 方法）

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（n 是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
_/**_
_ * Computes key.hashCode() and spreads (XORs) higher bits of hash_
_ * to lower.  Because the table uses power-of-two masking, sets of_
_ * hashes that vary only in bits above the current mask will_
_ * always collide. (Among known examples are sets of Float keys_
_ * holding consecutive whole numbers in small tables.)  So we_
_ * apply a transform that spreads the impact of higher bits_
_ * downward. There is a tradeoff between speed, utility, and_
_ * quality of bit-spreading. Because many common sets of hashes_
_ * are already reasonably distributed (so don't benefit from_
_ * spreading), and because we use trees to handle large sets of_
_ * collisions in bins, we just XOR some shifted bits in the_
_ * cheapest possible way to reduce systematic lossage, as well as_
_ * to incorporate impact of the highest bits that would otherwise_
_ * never be used in index calculations because of table bounds._
_ */_
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

拉链法

将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

在 jdk1.8 之后，当链表的长度大于 TREEIFY_THRESHOLD （默认为 8）之后，会会首先调用 treeifyBin() 方法。这个方法会根据 HashMap 数组来决定是否转换为红黑树。只有当数组长度大于或者等于 MIN_TREEIFY_CAPACITY （默认为 64） 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是执行 resize() 方法对数组扩容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
_/**_
_ * Replaces all linked nodes in bin at index for given hash unless_
_ * table is too small, in which case resizes instead._
_ */_
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < _MIN_TREEIFY_CAPACITY_)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

resize 方法

resize 方法是对 HashMap 中数组进行扩容的方法具体流程为如下：

  1. 判断数组容量是否超过 MAXIMUM_CAPACITY（默认为 2^30）
  2. 超过后不再继续扩容
  3. 未超过，容量变为原来的两倍
  4. 重新计算 threshold
  5. 初始化新的 table，将原来元素插入新的 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
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
/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
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;
}

TreeNode 节点

在转换为红黑树后，链表节点会变为 TreeNode

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
_/**_
_ * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn_
_ * extends Node) so can be used as extension of either regular or_
_ * linked node._
_ */_
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    _/**_
_     * Returns root of tree containing this node._
_     */_
_    _final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
}

loadFactor 属性

用来控制 HashMap 中数组的疏密程度的属性，默认为 0.75f。

  • 越接近 1 代表数组中的数越稠密，越容易发生碰撞，从而链表更长，查找效率比较低。
  • 越接近 0 代表数组中的数越稀疏，越不容易发生碰撞，但同时数组存放数据越少，空间利用率低。

put 方法

HashMap 中插入元素使用的方法

具体流程如下：

  1. 如果定位到的数组位置没有元素，直接插入
  2. 如果定位到的数组位置有元素，比较两个元素的 key
  3. 如果 key 相同就直接覆盖
  4. 如果 key 不相同，判断 p 是否是一个树节点
  5. 如果 p 是树节点，调用 putTreeVal() 方法将元素插入树中
  6. 如果 p 不是树节点，则 p 为链表，将 元素放置元素链表末尾
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
/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with {@code key}, or
 *         {@code null} if there was no mapping for {@code key}.
 *         (A {@code null} return can also indicate that the map
 *         previously associated {@code null} with {@code key}.)
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        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);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    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;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

get 方法

HashMap 中 get 方法与 put 方法的流程相似，都是相同的判断

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
_/**_
_ * Returns the value to which the specified key is mapped,_
_ * or {_**@code **_null} if this map contains no mapping for the key._
_ *_
_ * <p>More formally, if this map contains a mapping from a key_
_ * {_**@code **_k} to a value {_**@code **_v} such that {_**@code **_(key==null ? k==null :_
_ * key.equals(k))}, then this method returns {_**@code **_v}; otherwise_
_ * it returns {_**@code **_null}.  (There can be at most one such mapping.)_
_ *_
_ * <p>A return value of {_**@code **_null} does not <i>necessarily</i>_
_ * indicate that the map contains no mapping for the key; it's also_
_ * possible that the map explicitly maps the key to {_**@code **_null}._
_ * The {_**@link **_#containsKey containsKey} operation may be used to_
_ * distinguish these two cases._
_ *_
_ * _**@see **_#put(Object, Object)_
_ */_
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(key)) == null ? null : e.value;
}

_/**_
_ * Implements Map.get and related methods._
_ *_
_ * _**@param **_key the key_
_ * _**@return **_the node, or null if none_
_ */_
final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = _hash_(key))]) != 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;
}

HashSet 源码

初始化方法

HashSet 底层是基于 HashMap 实现的，因此源码基本是直接调用 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
55
56
57
58
59
60
61
62
63
_/**_
_ * Constructs a new, empty set; the backing {_**@code **_HashMap} instance has_
_ * default initial capacity (16) and load factor (0.75)._
_ */_
public HashSet() {
    map = new HashMap<>();
}

_/**_
_ * Constructs a new set containing the elements in the specified_
_ * collection.  The {_**@code **_HashMap} is created with default load factor_
_ * (0.75) and an initial capacity sufficient to contain the elements in_
_ * the specified collection._
_ *_
_ * _**@param **_c the collection whose elements are to be placed into this set_
_ * _**@throws **_NullPointerException if the specified collection is null_
_ */_
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math._max_((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

_/**_
_ * Constructs a new, empty set; the backing {_**@code **_HashMap} instance has_
_ * the specified initial capacity and the specified load factor._
_ *_
_ * _**@param      **_initialCapacity   the initial capacity of the hash map_
_ * _**@param      **_loadFactor        the load factor of the hash map_
_ * _**@throws     **_IllegalArgumentException if the initial capacity is less_
_ *             than zero, or if the load factor is nonpositive_
_ */_
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

_/**_
_ * Constructs a new, empty set; the backing {_**@code **_HashMap} instance has_
_ * the specified initial capacity and default load factor (0.75)._
_ *_
_ * _**@param      **_initialCapacity   the initial capacity of the hash table_
_ * _**@throws     **_IllegalArgumentException if the initial capacity is less_
_ *             than zero_
_ */_
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

_/**_
_ * Constructs a new, empty linked hash set.  (This package private_
_ * constructor is only used by LinkedHashSet.) The backing_
_ * HashMap instance is a LinkedHashMap with the specified initial_
_ * capacity and the specified load factor._
_ *_
_ * _**@param      **_initialCapacity   the initial capacity of the hash map_
_ * _**@param      **_loadFactor        the load factor of the hash map_
_ * _**@param      **_dummy             ignored (distinguishes this_
_ *             constructor from other int, float constructor.)_
_ * _**@throws     **_IllegalArgumentException if the initial capacity is less_
_ *             than zero, or if the load factor is nonpositive_
_ */_
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

add 方法

插入元素时，调用 HashMap 中的 put 方法，key 为插入元素，value 为默认的 Object 对象

当你把对象加入 HashSet 时，HashSet 会先计算对象的 hashcode 值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用 equals() 方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Dummy value to associate with an Object in the backing Map
private static final Object _PRESENT _= new Object();

/**
 * Adds the specified element to this set if it is not already present.
 * More formally, adds the specified element {@code e} to this set if
 * this set contains no element {@code e2} such that
 * {@code Objects.equals(e, e2)}.
 * If this set already contains the element, the call leaves the set
 * unchanged and returns {@code false}.
 *
 * @param e element to be added to this set
 * @return {@code true} if this set did not already contain the specified
 * element
 */
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

ConcurrentHashMap 源码

ConcurrentHashMap 底层与 HashMap 相同，在具体操作上使用了 CAS （Compare-And-Swap）操作与 synchronized 锁来保证线程安全。

initialTable 方法

实现了延迟初始化，只有在真正需要时才会分配和初始化内部数据结构，通过 CAS 操作来保证多个线程在并发情况下能够安全地初始化哈希表，具体流程如下：

  1. 判断 sizeCtl 是否小于 0（sizeCtl 用于控制表的初始化和扩容行为）
  2. 如果小于 0，表示有线程正在进行初始化或扩容操作
  3. 如果大于等于 0，通过 CAS 将 sizeCtl 更新为 1。
  4. 并初始化 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
/**
 * Initializes table, using the size recorded in sizeCtl.
 */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

put 方法

put() 方法用于将一个键值对插入到 ConcurrentHashMap 中。如果指定的键已存在，则更新其值；如果不存在，则插入新的键值对。具体流程如下：

  1. 计算键的哈希值
  2. 如果哈希桶的位置为空，使用 CAS 操作尝试插入新节点、
  3. 如果不为空，使用 synchronize 同步块，来更新更新值，具体更新流程与 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
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
_/**_
_ * Maps the specified key to the specified value in this table._
_ * Neither the key nor the value can be null._
_ *_
_ * <p>The value can be retrieved by calling the {_**@code **_get} method_
_ * with a key that is equal to the original key._
_ *_
_ * _**@param **_key key with which the specified value is to be associated_
_ * _**@param **_value value to be associated with the specified key_
_ * _**@return **_the previous value associated with {_**@code **_key}, or_
_ *         {_**@code **_null} if there was no mapping for {_**@code **_key}_
_ * _**@throws **_NullPointerException if the specified key or value is null_
_ */_
public V put(K key, V value) {
    return putVal(key, value, false);
}

_/** Implementation for put and putIfAbsent */_
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = _spread_(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh; K fk; V fv;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = _tabAt_(tab, i = (n - 1) & hash)) == null) {
            if (_casTabAt_(tab, i, null, new Node<K,V>(hash, key, value)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == _MOVED_)
            tab = helpTransfer(tab, f);
        else if (onlyIfAbsent // check first node without acquiring lock
                 && fh == hash
                 && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                 && (fv = f.val) != null)
            return fv;
        else {
            V oldVal = null;
            synchronized (f) {
                if (_tabAt_(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                    else if (f instanceof ReservationNode)
                        throw new IllegalStateException("Recursive update");
                }
            }
            if (binCount != 0) {
                if (binCount >= _TREEIFY_THRESHOLD_)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

yzlzzzdeveloper