HashSet如何不允许重复？

Question

我正在检查< code>HashSet的< code>add方法。有人提到

如果该集合已经包含元素，则调用保持集合不变，并返回false。

但是add方法在内部保存HashMap中的值

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

HashMap的put方法声明

将指定值与该映射中的指定键相关联。如果映射先前包含该键的映射，则旧值将被替换。

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

Answer 1

如您所见，HashSet.add 方法将元素作为键而不是值添加到 HashMap.put 中。值在哈希映射中被替换，而不是键。

Answer 2

您可能正在寻找的答案归结于这样一个事实，即支持散列表将集合的元素映射到值< code>PRESENT，该值在HashSet.java中定义如下:

private static final Object PRESENT = new Object();

在＜code＞HashMap的源代码中。put我们有：

  386     public V put(K key, V value) {
  387         if (key == null)
  388             return putForNullKey(value);
  389         int hash = hash(key.hashCode());
  390         int i = indexFor(hash, table.length);
  391         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  392             Object k;
  393             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  394                 V oldValue = e.value;
  395                 e.value = value;
  396                 e.recordAccess(this);
  397                 return oldValue;
  398             }
  399         }
  400 
  401         modCount++;
  402         addEntry(hash, key, value, i);
  403         return null;
  404     }

因为有问题的键已经存在，所以我们将在第397行获取早期返回。但是您可能认为正在对第395行的map进行更改，在这一行中，我们似乎正在更改map条目的值。但是，value的值是PRESENT。但是因为PRESENT是静态的和最终的，所以只有一个这样的实例；因此赋值e.value=value实际上根本不会改变map，因此集合也不会改变！

更新：

一旦< code>HashSet被初始化。< br> -其中的所有项目都作为键存储在< code>HashMap中< br> -所有< code>HashMap的值只有一个< code>PRESENT对象，它是< code>HashSet中的静态字段

Answer 3

PRESENT只是一个虚拟值 - 集合并不真正关心它是什么。该套装真正关心的是地图的键。所以逻辑是这样的：

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不会更改键，只是更改映射到该键的值。由于map的键是Set真正关心的，因此Set是不变的。

事实上，< code >集合的底层结构已经发生了一些变化，它用< code>(a，PRESENT)替换了< code>(a，OLD)的映射。但是从< code>Set的实现之外是看不到的。(碰巧的是，这种变化甚至不是真正的变化，因为< code>OLD == PRESENT)。