Set接口如何保證非重複

今天面試官問我：Set如何保證非重複？Set接口如何保證非重複

2013-07-02 Victor

*接口*只說明*實現*必須實現 - 而不是它們如何實現它。你需要詢問一個具體的實現。 –

'更正式地說，集合不包含e1和e2這樣的元素，這樣e1.equals（e2）和至多一個null元素。「也許他問的是什麼約束'Set'強制執行？例如，「equals」而不是「identity」或「hashCode」。 –

@Victor你是在問 - 面試 - 問題狂歡？ – NINCOMPOOP

答案在於add方法的源代碼。

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

在哪裏，PRESENT是Object類的對象：例如在TreeSet源代碼add方法如下實現。m是NavigableMap的對象。這NavigableMapm被用來存儲元素e作爲key和PRESENT作爲其value給定的密鑰e。因此，m中的每個密鑰都具有相同的對象PRESENT。在oracle doc中定義的put方法Map是：

將指定的值與此映射中指定的鍵關聯。如果地圖先前包含密鑰的映射，則舊值將被替換。
...
...
返回：與鍵，或如果爲null沒有該鍵沒有映射關聯的以前的值。（返回null還可能表示該映射以前null與key關聯。）

所以，當你把重複的元素集合中該元素放在NavigableMap關鍵值爲PRESENT。如果該密鑰在NavigableMap中不存在，則put方法返回null，因此 m.put(e,PRESENT)==null返回true，並且我們知道該元素已添加。如果關鍵是已經存在於NavigableMap然後put方法與現有overrided的value爲keye內NavigableMap並返回舊值（它是存在），因此 m.put(e,PRESENT)==null回報false，我們才知道這是不是添加的元素。

來源

2013-07-02 18:22:10

這隻回答'TreeSet'的問題。問題是關於「Set」。正如問，原來的問題實際上並不合理，但這不是答案。 – EJP

Set是一種抽象數據類型，可以用多種方式實現。它本身就是合同的規範;因此它不保證任何東西。這取決於接口的執行以保證合同得到滿足。

因此，查看實現的工作方式和原因更有意思。一些常見的實現是：

哈希表，由HashSet

平衡樹在Java中實現，因爲在Java中實現由TreeSet

位設置（特殊工種），如EnumSet和Java實現BitSet

跳過列表，如由ConcurrentSkipListSet

樸素陣列實現：掃描在添加它之前該元素的陣列;不經常使用。以Java語言實現CopyOnWriteArraySet

在求職面試中，您會回答上述問題並提供解釋任何一項實施的詳細信息。面試官應該已經知道其中的一些，除非被問到，否則開始對他們進行散漫並不會對你有好處。

來源

2013-07-02 18:06:04 Joni

...但是這個問題如何回答？ – radai

像這樣：*問：如何保證不重複？答：有很多方法可以做到這一點。例如A，B，C或D. * – Joni

是的，但這些保證是由impl支持的，而不是接口。我可以編寫一個使用ArrayList存儲的集合實現，並完全打破這種保證。 – radai

從規範的角度來看，指定add方法在嘗試添加副本時必須執行的操作。爲add方法文檔說這一點，例如：

將指定元素添加到這個組，如果它不是已存在（可選操作）。更正式地說，如果該集合不包含元素e2使得（e == null？ e2 == null：e.equals（e2）），則將該指定的元素e添加到該集合中的。如果這個集合已經包含元素，則該呼叫將保持集合不變並返回false。在組合與構造函數的限制，這確保集合從不包含重複的元素。

從同一頁（http://docs.oracle.com/javase/6/docs/api/java/util/Set.html）：

上構造的附加規定是，這並不奇怪，所有的構造必須創建一組不包含重複單元（如上所定義）。

（爲了完整起見，也有關於equals和hashCode規定是確保Set正確的模型設定的抽象。）

來源

2013-07-02 18:07:48

Set接口如何保證非重複

回答

相關問題