💬 友情提示：本文在技术讲解的基础上，穿插了“大白话”解释，适合从0开始逐步搞懂 HashSet 的小伙伴！
注释: 本文流程图是UI AI根据代码分析

为什么要搞懂 HashSet？

• 面试常客！

• 日常开发必备！

• 搞懂了它，等于掌握了 Java 集合框架的“基石”！

HashSet 与 HashMap 的关系

类结构和关键字段

public class HashSet<E> extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

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

• HashSet = 只要 Key，不要 Value 的 HashMap。

• 实际数据都进了 map.put(e, PRESENT)，你放的东西被当成 key。

• PRESENT 是固定占位符，表示“这个 key 已存在”。

HashMap.put() 源码 + 注释 + 白话

源码核心段（putVal()）

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 高位扰动
}

putVal() 解读

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
    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; // 找到相同 key，准备覆盖
        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)
                        treeifyBin(tab, hash); // 超 8 个则尝试树化
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break; // 找到重复 key
                p = e;
            }
        }

        // 有重复则覆盖 value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            return oldValue;
        }
    }

    ++modCount;
    if (++size > threshold)
        resize(); // 超过容量，扩容
    return null;
}

• 看 table 是不是初始化好？没有就先 resize()。

• 用 hash & (length - 1) 定位数组桶。

• 桶是空的？直接插入。

  • 桶不空？

    • 遇到重复 key？覆盖。

    • 不重复：

      • 是红黑树？树里插。

      • 是链表？链尾插入，满 8 个考虑转树。

• 最后看 size 是不是超过 threshold？超过就扩容。

树化（treeifyBin）

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);
        tab[index] = hd;
        hd.treeify(tab); // 真正转红黑树
    }
}

resize() 扩容源码

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int newCap = oldCap << 1;
    Node<K,V>[] newTab = (Node<K,V>[]) new Node[newCap];
    table = newTab;

    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e = oldTab[j];
        if (e != null) {
            oldTab[j] = null;
            if (e.next == null)
                newTab[e.hash & (newCap - 1)] = e;
            else {
                // 链表重新分桶
                Node<K,V> loHead = null, hiHead = null;
                Node<K,V> loTail = null, hiTail = null;
                do {
                    Node<K,V> 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;
                    }
                    e = next;
                } while (e != null);
                if (loHead != null) newTab[j] = loHead;
                if (hiHead != null) newTab[j + oldCap] = hiHead;
            }
        }
    }
    return newTab;
}