Java:有效地跟踪使用过的对象

Question

我有一个程序,可以随着时间的推移收集对象.这些对象通常是,但并不总是程序已经收到的对象的重复.唯一对象的数量有时可达数万.随着我的列表增长,需要更多时间来确定对象之前是否出现过.

我目前的方法是将所有内容存储在ArrayList中; 使用Collections.sort(al); 并使用Collections.binarySearch(al,key)来确定我是否使用了一个对象.每当我遇到一个新对象时,我必须插入并排序.

我想知道是否有更好的方法来做到这一点.包含物往往会减速太快.我正在寻找尽可能接近O(1)的东西.

非常感谢.

这是java.为了理解我在说什么,我基本上需要一个方法来做到这一点:

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

}

Answer 1

这引出了一个问题 - 为什么不使用不允许重复的数据结构(例如Set)？如果您尝试添加重复项,该方法将返回false,数据结构将保持不变.

Answer 2

而不是使用ArrayList,为什么不使用Set实现(可能是a HashSet)？您将获得恒定时间查找,无需排序.