HashSet如何不允许重复？

Question

我正在经历add的HashSet方法。提到

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

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

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

put的HashMap方法指出

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

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

Answer 1

PRESENT只是一个虚拟值-该集合实际上并不关心它是什么。集合does关心的是地图的keys。因此逻辑如下：

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

实际上，[[已经]]对Set的基础结构进行了一些更改-它用(a, OLD)代替了(a, PRESENT)的映射。但这是从Set的实现之外无法观察到的。 （实际上，由于OLD == PRESENT，该更改甚至不是真正的更改。）。

您可能正在寻找的答案归结为以下事实：支持哈希映射将集合的元素映射到PRESENT中定义的值HashSet.java，如下所示：

private static final Object PRESENT = new Object();

在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行对地图进行了更改，其中看来我们正在更改地图条目的值。但是，value的值为PRESENT。但是由于PRESENT是静态且最终的，因此只有一个这样的实例；因此分配e.value = value实际上根本不会更改地图，因此也不会更改设置！
注

：初始化HashSet后。-它所有的int项目都作为键存储在HashMap中-HashMap的所有值只有一个对象，即PRESENT，这是HashSet]中的静态字段

您可以看到HashSet.add方法将元素作为键而不是值添加到HashMap.put。值将替换为HashMap而不是键。

请参见HashMap#put：

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

它用

new

值替换密钥，这样，HashMap#put中将没有重复项。

HashSet

e是键，所以如果
e

已经存在，

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

将不会返回put。因此，null将返回false。

add的JavaDoc：

与键关联的先前值；如果没有键的映射，则为null。 （返回null可能还表明该映射先前将null与key关联。）

从javadocs中获取HashMap.put（），“将指定值与此映射中的指定键相关联。如果该映射先前包含该键的映射，则将替换旧值。”

因此将替换映射值（这是HashSet类中的一个恒定静态字段，因此将替换同一实例），并且映射键保持不变（实际上是Set集合项）

Answer 2

您可能正在寻找的答案归结为以下事实：支持哈希映射将集合的元素映射到PRESENT中定义的值HashSet.java，如下所示：

Answer 3

您可以看到HashSet.add方法将元素作为键而不是值添加到HashMap.put。值将替换为HashMap而不是键。

Answer 4

请参见HashMap#put：

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

Answer 5

HashSet

e是键，所以如果
e

Answer 6

从javadocs中获取HashMap.put（），“将指定值与此映射中的指定键相关联。如果该映射先前包含该键的映射，则将替换旧值。”

因此将替换映射值（这是HashSet类中的一个恒定静态字段，因此将替换同一实例），并且映射键保持不变（实际上是Set集合项）