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)? Вы получите поиск в постоянном времени , сортировка не требуется.

N.B. ваши объекты должны будут правильно переопределить hashCode() и equals().

Answer 2

Возникает вопрос - почему бы не использовать структуру данных, которая не допускает дублирование (например, Set)?Если вы попытаетесь добавить дублирующийся элемент, метод вернет false и структура данных останется неизменной.

Answer 3

Убедитесь, что объекты имеют правильные методы equals() и hashCode(), и сохраните их в HashSet.Тогда поиск становится постоянным.

Если сохранение нежелательных объектов становится проблемой, кстати, вы можете рассмотреть возможность использования одной из многих реализаций WeakHashSet, доступных в Интернете - она ​​будет удерживать объекты, но все же позволитпри необходимости их можно собрать мусором.