HashSet 怎么判断元素重复，重复了是否 put

418 字

2 分钟

HashSet 怎么判断元素重复，重复了是否 put

2021-02-22

java集合

Java

/

集合

/

数据结构

HashSet 怎么判断元素重复，重复了是否 put#

HashSet 的 add 方法是通过调用 HashMap 的 put 方法实现的：

1
public boolean add(E e) {
2
    return map.put(e, PRESENT)==null;
3
}

所以 HashSet 判断元素重复的逻辑底层依然是 HashMap 的底层逻辑： HashMap 在插入元素时，通常需要三步：第一步，通过 hash 方法计算 key 的哈希值。

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

第二步，数组进行第一次扩容。

1
if ((tab = table) == null || (n = tab.length) == 0)
2
    n = (tab = resize()).length;

第三步，根据哈希值计算 key 在数组中的下标，如果对应下标正好没有存放数据，则直接插入。

1
if ((p = tab[i = (n - 1) & hash]) == null)
2
    tab[i] = newNode(hash, key, value, null);

如果对应下标已经有数据了，就需要判断是否为相同的 key，是则覆盖 value，否则需要判断是否为树节点，是则向树中插入节点，否则向链表中插入数据。

1
else {
2
    Node<K,V> e; K k;
3
    if (p.hash == hash &&
4
        ((k = p.key) == key || (key != null && key.equals(k))))
5
        e = p;
6
    else if (p instanceof TreeNode)
7
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
8
    else {
9
        for (int binCount = 0; ; ++binCount) {
10
            if ((e = p.next) == null) {
11
                p.next = newNode(hash, key, value, null);
12
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
13
                    treeifyBin(tab, hash);
14
                break;
15
            }
16
            if (e.hash == hash &&
17
                ((k = e.key) == key || (key != null && key.equals(k))))
18
                break;
19
            p = e;
20
        }
21
    }
22
}

也就是说，HashSet 通过元素的哈希值来判断元素是否重复，如果重复了，会覆盖原来的值。

1
if (e != null) { // existing mapping for key
2
    V oldValue = e.value;
3
    if (!onlyIfAbsent || oldValue == null)
4
        e.value = value;
5
    afterNodeAccess(e);
6
    return oldValue;
7
}