java - HashSet 如何不允许重复？

Question

我正在通过 HashSet 的 add 方法。提到了

If this set already contains the element, the call leaves the set unchanged and returns false.

但 add 方法在内部将值保存在 HashMap

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

HashMap的put方法声明

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.

那么如果HashMap的put方法替换旧值，HashSet add方法在重复元素的情况下保持集合不变？

Answer 1

PRESENT 只是一个虚拟值——集合并不真正关心它是什么。集合 关心的是 map 的键。所以逻辑是这样的:

Set.add(a):
  map.put(a, PRESENT) // so far, this is just what you said
    the key "a" is in the map, so...
      keep the "a" key, but map its value to the PRESENT we just passed in
      also, return the old value (which we'll call OLD)
  look at the return value: it's OLD, != null. So return false.

现在，OLD == PRESENT 并不重要——请注意 Map.put 不会更改键，只是映射到的值那把 key 。由于 map 的 keys 是 Set 真正关心的，所以 Set 是不变的。

事实上，Set 的底层结构发生了一些变化——它取代了 (a, OLD) 的映射> 带有 (a, PRESENT)。但这在 Set 的实现之外是无法观察到的。 (事实上​​，这种变化甚至不是真正的变化，因为 OLD == PRESENT)。