Как лучше всего обрабатывать несколько объектов, не отступая от уже обработанных объектов?

Question

Скажем, я хотел бы обработать несколько объектов некоторого класса Object в ходе некоторого алгоритма более высокого уровня с помощью некоторого метода treat(Object o). В этом алгоритме могут встречаться идентичные объекты (не имеющие одинакового адреса), поэтому я не хочу обрабатывать каждый из этих идентичных объектов, только первый появляется, игнорируя другие.

Простое решение было бы реализовать структуру ArrayList для хранения всех уже обработанных объектов с именем treated и сделать следующее.

if (!treated.contains(o)){
    treat(o);
    treated.add(o);
}

Однако я думаю, что метод contains работает в линейном времени, тогда как использование HashSet вместо ArrayList могло бы сделать это за постоянное время.

Вот моя проблема: одинаковые хэш-коды не гарантируют равенство . Другими словами, использование HashSet treated следующим образом:

if (!treated.contains(o)){
    treat(o);
    treated.add(o);
}

может не обрабатывать все отдельные объекты, поскольку некоторый объект o1 может иметь тот же хэш-код, что и другой объект o2. Если лечится o1, то o2 не будет, и наоборот. Может ли HashMap treated, используемый вместе с equals(), лучше подходить для моей проблемы?

if (treated.containsKey(o.hashCode())){
    Object o2 = treated.get(o.hashCode());
    if (!o.equals(o2)){
        treat(o);
    }
} else {
    treat(o);
    treated.put(o.hashCode(), o);
}

Какой метод рекомендуется использовать для решения этой проблемы?

NB: я видел комментарии об использовании «идеального хэш-кода», т.е. хэш-кода, присваивающего уникальное значение каждому уникальному объекту, таким образом не получая одинаковых хэш-кодов для разных объектов. Я не вижу в этом решения, поскольку (теоретически) я могу обрабатывать любое количество различных объектов, тогда как хэш-коды имеют тип int, что эффективно ограничивает количество различных хэш-кодов.

Answer 1

Другими словами, использование HashSet treated следующим образом [...] может не обрабатывать все отдельные объекты, поскольку некоторый объект o1 может иметь тот же хэш-код, что и другой объект o2

Это основано на ошибочном предположении, что HashSet.contains проверяет только код ha sh. Это не так - он использует код ha sh для поиска одинаковых кандидатов , но затем проверяет фактическое равенство с equals как обычно.

Из contains документация метода :

Возвращает true, если этот набор содержит указанный элемент. Более формально, возвращает true тогда и только тогда, когда этот набор содержит элемент e такой, что Objects.equals(o, e).