Java：有效跟蹤使用的對象

Question

我有一個隨時間收集對象的程序。這些對象通常但並不總是程序已經收到的對象的重複。唯一對象的數量有時可能高達數萬。隨着我的列表不斷增加，需要更多時間來確定某個對象是否已經出現。

我目前的方法是將所有東西都存儲在一個ArrayList中，al;使用Collections.sort（al）;並使用Collections.binarySearch（al，key）來確定我是否使用了一個對象。每當我遇到一個新的對象時，我必須插入然後排序。

我想知道是否有更好的方法來做到這一點。包含的速度通常會變慢。我正在尋找儘可能接近O（1）的東西。

非常感謝。

這是java。爲了理解什麼是我說的目的，基本上，我需要做這個的方法：

public boolean objectAlreadyUsed(Object o) { 
    return \\ Have we seen this object already? 

} 

Answer 1

而不是使用ArrayList，爲什麼不使用Set實現（可能是HashSet）？你會得到constant-time lookup，不需要排序。

N.B.您的物品將需要correctly override hashCode() and equals()。

Answer 2

這引出了一個問題 - 爲什麼不使用一個數據結構，不允許重複（如Set）？如果您嘗試add重複的項目，該方法將返回false和數據結構將保持不變。

Answer 3

確保對象有正確的equals()和hashCode()方法，並將它們存儲在HashSet中。查找然後變成不變的時間。

如果保留不需要的對象成爲問題，順便說一句，你可以考慮使用互聯網上可用的許多WeakHashSet實現之一 - 它將保留對象，但仍然允許它們在必要時被垃圾收集。