HashSet通過ArrayList的好處，反之亦然

我對Java中的數據結構有疑問。在解決Java中的典型哈希問題時，我使用了數據結構，這種數據結構一直運行良好，直到出現重複的對象（對象內容）。由於HashSet不支持重複插入，所以我的邏輯失敗了。HashSet通過ArrayList的好處，反之亦然

我取代的HashSet與典型Arraylist以來的HashSet的方法如。新增（），。載（），卸下襬臂（）中都支持，並且我的邏輯工作那麼完美。

但是，這是否意味着當涉及到重複時，ArrayList是Hashset的合理選擇？ Hashset通過ArrayList應該有一些時間複雜性優點嗎？有人可以提供一些關於這方面的見解嗎？

編輯：什麼是理想的數據結構，當你想要做哈希時，涉及重複。我的意思是當重複項不應該被忽略並且應該被插入。

來源

2015-07-12 SoulRayder

「哈希」是什麼意思？ – chrylis

將諸如字符串之類的對象添加到基於散列的數據結構中，並在稍後檢查它們的存在。如果相同的字符串出現兩次，則應該再次插入。 – SoulRayder

目前尚不清楚「哈希問題」是什麼意思，但也許你正在尋找multiset。來自Guava文檔：

支持順序無關的相等的集合，如Set，但可能有重複的元素。一個multiset有時也被稱爲一個包。

相互相等的多重集的元素被稱爲同一單個元素的出現。多重集中元素的出現次數稱爲該元素的計數（術語「頻率」和「多重性」是等效的，但在此API中未使用）。

JDK中沒有這樣的東西存在。

來源

2015-07-12 06:11:49 gdejohn

當您使用HashMap時，它會用新副本替換原始值。
當您使用HashSet時，後續重複項會被忽略（未插入）。
當你使用一個ArrayList，它只是增加了複製到列表

這一切都取決於你需要給你的需求的結束。

來源

2015-07-12 06:02:56 Constantin

但是當涉及到散列需求的時候，Hashset比arraylist有一些時間複雜性的優點嗎？否則，爲什麼你會需要哈希集，當你可以使用arraylist實現相同？ – SoulRayder

爲了簡單起見...如果您需要確保不允許重複項，您爲什麼會使用ArrayList？ – Constantin

看我的編輯。我想重複插入，不應該被忽略。 – SoulRayder

ArrayList不是合乎邏輯的選擇，如果你不想重複。針對不同用例的不同工具。

您可以在複製無效的地方使用Set，例如一組學生。 A List允許重複。

來源

2015-07-12 06:05:04

那麼當你想要在涉及重複項時進行哈希處理時，理想的數據結構是什麼？ – SoulRayder

@SoulRayder你爲什麼要這樣的事情？列表不使用桶來存儲數據，這是沒有意義的。你想做什麼？如果你擔心'ArrayList'的訪問時間，'get（int）'是常量時間，正如文檔 –

中提到的那樣。但是.contains（）是ArrayList中的線性時間嗎？或者在這兩種情況下也是這種常數？ – SoulRayder

如果您特別需要處理重複的HashSet，HashMap將能夠完成這項工作。如果您只需要添加對象的數量（使用快速查找/等），HashMap<T,Integer>將是理想的，其中T是您的對象的類型。如果您確實需要保留對已添加的重複對象的引用，請使用HashMap<T, List<T>>。這樣你可以使用HashMap的.containsKey(T t)來查找，並遍歷結果列表中的所有類似的哈希對象。例如，您可以創建此類：

public class HashSetWithDuplicates<T> { 

    private HashMap<T, List<T>> entries; 
    private int size; 

    public HashSetWithDuplicates(){ 
     entries = new HashMap<>(); 
     size = 0; 
    } 

    public HashSetWithDuplicates(Collection<? extends T> col){ 
     this(); 
     for(T t : col){ 
      add(t); 
     } 
    } 

    public boolean contains(T t){ 
     return entries.containsKey(t); 
    } 

    public List<T> get(T t){ 
     return entries.get(t); 
    } 

    public void add(T t){ 
     if (!contains(t)) entries.put(t, new ArrayList<>()); 

     entries.get(t).add(t); 
     size++; 
    } 

    public void remove(T t){ 
     if (!contains(t)) return; 
     entries.get(t).remove(t); 
     if(entries.get(t).isEmpty()) entries.remove(t); 
     size--; 
    } 

    public int size(){ 
     return size; 
    } 

    public boolean isEmpty(){ 
     return size() == 0; 
    } 
}

爲您的需求添加功能。

來源

2015-07-12 06:16:16 Mshnik

不明白爲什麼有人沒有評論就低估了這個答案。這似乎正是SoulRayder所需要的。重複的對象幾乎從來沒有任何意義，除了線程（即使有我懷疑）或其他東西。 –

HashSet通過ArrayList的好處，反之亦然

回答

相關問題