深入解析 Java HashSet 底层原理

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

为什么要搞懂 HashSet？面试常客！

日常开发必备！

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

HashSet 与 HashMap 的关系类结构和关键字段public class HashSet extends AbstractSet

implements Set, Cloneable, java.io.Serializable {

private transient HashMap 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[] tab; Node 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 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)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[] tab, int hash) {

int n, index; Node e;

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

resize(); // 优先扩容

else if ((e = tab[index = (n - 1) & hash]) != null) {

TreeNode hd = null, tl = null;

do {

TreeNode 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[] resize() {

Node[] oldTab = table;

int oldCap = (oldTab == null) ? 0 : oldTab.length;

int newCap = oldCap << 1;

Node[] newTab = (Node[]) new Node[newCap];

table = newTab;

for (int j = 0; j < oldCap; ++j) {

Node e = oldTab[j];

if (e != null) {

oldTab[j] = null;

if (e.next == null)

newTab[e.hash & (newCap - 1)] = e;

else {

// 链表重新分桶

Node loHead = null, hiHead = null;

Node loTail = null, hiTail = null;

do {

Node 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;

}