企业官网建设流程全解析

Set 家族全是 Map 的“只存 key 版”

Set的核心承诺是"元素不重复"。但如果你读HashSet源码，会发现一件很有意思的事——它自己几乎不存数据，去重逻辑全靠一个HashMap。这一篇揭开Set家族"借 Map 上位"的秘密，顺便把LinkedHashSet和TreeSet的底层也一并讲清。

一、HashSet 的真相：包装了一个 HashMap

看HashSet的字段和构造器就明白了：

privatetransientHashMap<E,Object>map;privatestaticfinalObjectPRESENT=newObject();// 占位 valuepublicHashSet(){map=newHashMap<>();}

HashSet把元素当作HashMap的key存进去，value 统一用一个静态空对象PRESENT占位。add方法：

publicbooleanadd(Ee){returnmap.put(e,PRESENT)==null;// key 已存在则 put 返回旧 value（非 null）→ false}

put返回null说明这个 key 之前不存在，add 成功返回 true；如果 key 已存在，put返回PRESENT（非 null），add 返回 false——去重就是靠 HashMap 的 key 不可重复实现的。所以HashSet的元素就是map.keySet()。

二、去重的契约：equals + hashCode

既然底层是 HashMap 的 key，那HashSet判断"两个元素是不是同一个"用的就是 HashMap 那套：先比 hashCode，再比 equals（见 HashMap 篇）。

所以把自定义对象放进 HashSet，必须正确重写equals和hashCode，否则：

• 只重写equals不重写hashCode：两个逻辑相等的对象可能 hashCode 不同 → 落到不同桶 → 都被加进去，去重失效。
• 只重写hashCode不重写equals：hashCode 相同但 equals 不同 → 挂在同一个桶的链表上，被认为不同元素，照样去重失效。

经典反例：你new User("张三")两次，如果User没重写这两个方法，HashSet 会当它俩是不同的人。重写后才会判定重复、只留一个。

三、性能：add/contains/remove 都是 O(1)

因为直接委托给 HashMap，HashSet的增、查、删平均复杂度都是 O(1)。这是它相对于"手写 List + 遍历 contains"的最大优势——后者是 O(n)。

四、LinkedHashSet：保插入序的 Set

LinkedHashSet是HashSet的子类，构造时建的是LinkedHashMap：

HashSet(intinitialCapacity,floatloadFactor,booleandummy){map=newLinkedHashMap<>(initialCapacity,loadFactor);}

所以它 = HashSet 的去重能力 + LinkedHashMap 的插入顺序。遍历时按你 add 的顺序输出，而不是 HashSet 那种"无序"。代价同样是节点多两个引用、内存略大。适合"要去重、又想按添加顺序展示"的场景，比如去重后的用户操作流水。

五、TreeSet：排序的 Set

TreeSet底层是TreeMap，元素当作 key，同样用PRESENT占位：

publicTreeSet(){this(newTreeMap<E,Object>());}

特性：

• 元素自动排序（自然序或构造时传Comparator）。
• 元素必须可比较，否则add抛ClassCastException；不允许 null（除非比较器允许）。
• 增删查 O(log n)。
• 实现NavigableSet，支持first()、last()、lower()、higher()、subSet()等范围/邻近操作。

适合"要去重且要排序/取区间"的场景，比如排行榜去重后取 Top N。

六、三兄弟怎么选？

对应底层一目了然：HashSet→HashMap，LinkedHashSet→LinkedHashMap，TreeSet→TreeMap。整个 Set 家族就是 Map 家族的"只存 key 版"，记住这层关系，Set 的行为就全解释得通了。

七、常见坑

1. 可变对象改了参与 equals/hashCode 的字段，就从 Set 里"消失"了：对象入 Set 后改字段，它的哈希桶位置变了，再contains/remove找不到，成了游离垃圾。规则：放进 HashSet/HashMap 的 key 必须是不可变对象（或至少别改参与哈希的字段）。
2. 遍历时删除用迭代器：for (String x : set) set.remove(x)抛ConcurrentModificationException，要用it.remove()。
3. HashSet 允许一个 null：只有一个，因为 key 不可重复；TreeSet 不允许 null。

八、面试追问

• Q：HashSet 怎么保证不重复？元素作 HashMap 的 key，value 用固定占位对象；add 时map.put返回非 null 说明 key 已存在，返回 false 去重。
• Q：为什么 HashSet 比 List 去重快？List 去重要contains遍历 O(n)，HashSet 靠哈希 O(1)。
• Q：HashSet 和 TreeSet 的 null 策略为何相反？HashSet 底层 HashMap 允许一个 null key；TreeSet 底层 TreeMap 要靠比较器排 key，null 无法参与比较，故不允许。

总结

Set 家族没有自己的存储，全是"借" Map：HashSet 包 HashMap、LinkedHashSet 包 LinkedHashMap、TreeSet 包 TreeMap，元素作 key、统一用占位 value。去重本质是 HashMap 的 key 不可重复，前提是正确实现 equals/hashCode 且 key 不可变。按"只去重 / 去重+保序 / 去重+排序"三档选 HashSet / LinkedHashSet / TreeSet。