HashSet如何不允许重复？

我正在经历HashSet的add方法。提及的是，HashSet如何不允许重复？

如果这个集合已经包含元素，那么调用离开集合不变并返回false。

但add方法是内部节省HashMap

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

值的HashMap的put方法指出

将指定值与此映射中指定的键。如果地图先前包含密钥的映射，则旧值将被替换。

所以如果HashMap的put方法取代了旧的价值，该HashSetadd方法是如何离开设定不变的重复元素的情况下？

来源

2014-03-06 Zeeshan

查找'HashSet.add'的源代码的荣誉。你有没有查找'HashMap.put'的源代码？ –

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

事实上，有具有了一些变化到Set的底层结构 - 它取代的(a, OLD)的映射与(a, PRESENT)。但从Set的实施以外，这是不可观察的。（恰巧，这种变化甚至不是真正的变化，因为OLD == PRESENT）。

来源

2014-03-06 10:04:19 yshavit

Nice说明。谢谢:) – Zeeshan

正如你所看到的HashSet.add方法将元素添加到HashMap.put作为一个关键而不是一个值。价值被替换为HashMap不是关键。

来源

2014-03-06 09:54:02 shazin

是的。地图中的所有值都是相同的（PRESENT）。 HashSet使用内部映射和它的KEY部分来存储集合的元素 – EdH

见HashMap#put：

将指定值与此映射中指定的键。如果映射先前包含密钥的映射，则替换旧值。

它取代与新值，这种方式的关键，没有重复将在HashSet。

来源

2014-03-06 09:56:00 Maroun

我得到了这个，没有重复的将会在'HashSet'中，我不想知道为什么旧的重复值没有被覆盖在'HashSet'？ – Zeeshan

@Shaan，可以替换地图值（它是HashSet类中的一个常量静态字段，因此被替换为相同的实例），并且地图关键字保持不变（这实际上是Set集合项） –

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

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

的JavaDoc put：

是否有键的映射关系与关键，或空关联的先前值。（返回null还可能表示该映射以前null与key关联。）

来源

2014-03-06 09:56:24 Batty

，你可能会寻找答案归结为背衬HashMap中的组的至在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，在它看来，我们是e改变地图条目的值。但是，value的值是PRESENT。但是因为PRESET是静态的和最终的，所以只有一个这样的实例;所以分配e.value = value实际上不会更改地图，因此根本不会改变！

来源

2014-03-06 10:06:11

+1因为添加真实的代码参考;） – jasilva

@RayToal，你如何复制代码以及行号？ – Zeeshan

从[这里]复制（http://hg.openjdk.java.net/jdk6/jdk6-gate/jdk/file/tip/src/share/classes/java/util/HashMap.java） –

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

因此，地图值将被替换（它是HashSet类中的一个常量静态字段，因此将替换相同的实例），并且map键保持不变（这实际上是Set集合项）

来源

2014-03-06 10:24:10

HashSet如何不允许重复？

回答

相关问题