哈希集如何不允许重复项？

hashmap java hashset

2022-09-01 07:37:08

我正在经历.有人提到addHashSet

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

但该方法是在内部保存值addHashMap

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

所述方法putHashMap

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

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

答案 1

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 == PRESENTMap.putSetSet

实际上，对的底层结构进行了一些更改 -- 它用 .但是从的实现之外是看不出来的。（碰巧的是，这种变化甚至不是真正的变化，因为）。Set(a, OLD)(a, PRESENT)SetOLD == PRESENT

答案 2

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

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 行的地图进行更改，其中似乎我们正在更改地图条目的值。但是，的值为。但是因为是静态的和最终的，所以只有一个这样的实例;因此，分配实际上不会改变地图，因此根本不会改变集合！valuePRESENTPRESENTe.value = value

更新：

初始化后。
- 其中的所有项目都作为键存储在 a
中 - 所有只有一个对象的值都是静态字段HashSetHashMapHashMapPRESENTHashSet