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实现之一 - 它将保留对象，但仍然允许它们在必要时被垃圾收集。