Java HashSet 如何不允许重复？

How does HashSet not allow duplicates?

提问by Zeeshan

I was going through the addmethod of HashSet. It is mentioned that

我正经过add的方法HashSet。提到

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

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

But the addmethod is internally saving the values in HashMap

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

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

The putmethod of HashMapstates that

的put方法HashMap是

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.

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

So if the putmethod of HashMapreplaces the old value, how the HashSetaddmethod leaves the set unchanged in case of duplicate elements?

因此，如果该put方法HashMap取代了旧的价值，如何将HashSetadd法叶集不变的重复元素的情况下？

采纳答案by yshavit

PRESENTis just a dummy value -- the set doesn't really care what it is. What the set doescare about is the map's keys. So the logic goes like this:

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.

Now, the fact that OLD == PRESENTdoesn't matter -- and note that Map.putdoesn't change the key, just the value mapped to that key. Since the map's keysare what the Setreally cares about, the Setis unchanged.

现在，事实OLD == PRESENT并不重要——请注意，Map.put不会更改键，只是映射到该键的值。由于地图的键是Set真正关心的，所以Set是不变的。

In fact, there hasbeen some change to the underlying structures of the Set-- it replaced a mapping of (a, OLD)with (a, PRESENT). But that's not observable from outside the Set's implementation. (And as it happens, that change isn't even a real change, since OLD == PRESENT).

事实上，的底层结构已经发生了一些变化Set——它取代了(a, OLD)with的映射(a, PRESENT)。但这不是从Set的实现之外观察到的。（碰巧的是，这种变化甚至不是真正的变化，因为OLD == PRESENT）。

回答by shazin

As you can see the HashSet.addmethod adds the element to the HashMap.putas a key not as a value. Value is replaced in the HashMapnot the key.

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

回答by Maroun

See HashMap#put:

见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.

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

It replaces the key with the newvalue, this way, no duplicates will be in the HashSet.

它用新值替换键，这样，HashSet.

回答by Batty

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

e is the key, So if eis already present putwill not return null. Hence addwill return false.

e 是键，所以如果e已经存在put则不会返回null。因此add将返回false。

JavaDoc for put:

JavaDoc 用于put：

the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key.)

与 key 关联的先前值，如果没有 key 的映射，则为 null。（空返回也可以表明映射先前将空与键相关联。）

回答by Ray Toal

The answer that you may be looking comes down to the fact that the backing hashmap maps the elements of the set to the value PRESENTwhich is defined in HashSet.javaas follows:

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

private static final Object PRESENT = new Object();

In the source code for HashMap.putwe have:

在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     }

Because the key in question already exists, we will take the early return on line 397. But you might think a change is being made to the map on line 395, in which it appears that we are changing the value of a map entry. However, the value of valueis PRESENT. But because PRESENTis static and final, so there is only one such instance; and so the assignment e.value = valueactually doesn't change the map, and therefore the set, at all!

因为有问题的键已经存在，我们将在第 397 行获取早期返回值。但您可能认为正在对第 395 行的映射进行更改，在该行中，我们似乎正在更改映射条目的值。然而，价值value为PRESENT。但是因为PRESENT是static和final，所以只有一个这样的实例；所以这个任务e.value = value实际上根本不会改变地图，因此也不会改变集合！

Update:

Once a HashSetis initialized.
- All the items in it are stored as keys in a HashMap
- All the values that HashMaphave ONLY ONE object that is PRESENTwhich is a static field in HashSet

更新：

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

回答by sutanu dalui

From javadocs for 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() 的 javadoc，“将指定值与此映射中的指定键相关联。如果映射先前包含该键的映射，则替换旧值。”

Thus the map value will be replaced, (which is a constant static field in HashSet class, and thus the same instance is replaced), and the map key is kept untouched (which, in fact IS the Set collection item)

这样map值就会被替换，（它是HashSet类中的一个常量静态字段，因此替换了同一个实例），而map键保持不变（实际上就是Set集合项）