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如何不允許重複？

回答

相關問題