HashSet如何不允许重复？ [英] How does HashSet not allow duplicates?

问题描述

我正在浏览 HashSet 的 add 方法。提到

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

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

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

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.

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

So if the put method of HashMap replaces the old value, how the HashSet add method leaves the set unchanged in case of duplicate elements?

推荐答案

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

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

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

Now, the fact that OLD == PRESENT doesn't matter -- and note that Map.put doesn't change the key, just the value mapped to that key. Since the map's keys are what the Set really cares about, the Set is unchanged.

事实上，已经对 Set 的基础结构进行了一些更改 - 它用（a，PRESENT）替换了（a，OLD）的映射。但是在 Set 的实现之外，这是不可观察的。 （事实上​​，这种变化甚至不是真正的变化，因为 OLD == PRESENT ）。

In fact, there has been 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).

这篇关于HashSet如何不允许重复？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！