Как алгоритм поиска работает с объектами в java-коллекции, такой как HashSet?

Question

Вопрос действительно касается объектов, которые динамически изменяются в коллекции. Идет ли метод «содержит» и сравнивает ли каждый объект индивидуально каждый раз или он делает что-то умное?

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

Дополнительный вопрос:

Спасибо за ответы ниже ... Могу я также спросить, что происходит в случае ArrayList? Я не смог найти ничего в документации, где говорится, что нельзя помещать изменяемые объекты в ArrayList. Означает ли это, что алгоритм поиска просто идет и сравнивается с хеш-кодом каждого объекта ??

Answer 1

Они хешируют объект и ищут его по хеш-коду.Если он есть, он будет сравнивать сами объекты.Это связано с тем, что два или более объектов с одинаковым хешем могут не совпадать.

Поскольку в хеш-коллекциях Java используются сегменты (цепочки), они должны просматривать все объекты в сегменте.Эти объекты хранятся в связанном списке (не java.util.LinkedList, а в пользовательском списке)

Это обычно очень эффективно, а метод HashSet.contains() имеет амортизированный O (1) (постоянное время).

---

В документации Java есть ответ на вторую часть вашего вопроса:

Примечание: если изменчивый, нужно соблюдать особую осторожностьобъекты используются в качестве заданных элементов. Поведение набора не указывается, если значение объекта изменяется способом, который влияет на сравнения равных, в то время как объект является элементом в наборе.Особый случай этого запрета состоит в том, что недопустимо, чтобы набор содержал себя как элемент.

Answer 2

A HashSet вычисляет хеш-код элемента, когда он добавляется в набор.Он хранит это таким образом, который позволяет очень эффективно находить все элементы с одинаковым хеш-кодом.

Затем, когда вы вызываете contains(), ему просто нужно вычислить хеш-код значения, которое вы ищите и найдите все элементы в наборе с одинаковым хеш-кодом.Может быть несколько элементов, поскольку хеш-коды не являются уникальными, но, вероятно, будет гораздо меньше элементов с совпадающими хеш-кодами, чем элементов в самом наборе.Каждый соответствующий элемент затем проверяется с помощью equals, пока не будет найдено совпадение или у нас не останется кандидатов.

РЕДАКТИРОВАТЬ: Чтобы ответить на вторую часть, которую я как-то пропустил при первом чтении,не сможет найти элемент снова.Вы не должны изменять элемент, используемый в качестве ключа в хэш-таблице или элемент в хэш-наборе, любым способом, влияющим на равенство, иначе вы в основном сломаете вещи.

Answer 3

Простой ответ - нет, ничего умного не происходит.Если вы ожидаете, что состояние объекта изменится таким образом, что это повлияет на его поведение hashCode() и equals(...), то вы не должны хранить его в HashSet или в любом другом Set.Цитировать из http://download.oracle.com/javase/6/docs/api/java/util/Set.html:

Примечание. Необходимо соблюдать особую осторожность, если в качестве заданных элементов используются изменяемые объекты.Поведение набора не указывается, если значение объекта изменяется таким образом, что это влияет на equals сравнений, в то время как объект является элементом в наборе.Особый случай этого запрета состоит в том, что недопустимо, чтобы набор содержал себя как элемент.

Answer 4

A HashSet использует HashMap под капотом. Поэтому операция contains использует метод hashCode() в объекте, чтобы проверить, присутствует ли он в хэш-таблице, реализованной HashMap.