Как работает HashSet
Поправьте, если неверно - для объекта вычисляется хеш, помещается в такой вот ассоциативный массив, в нашем случае это HashSet. При возникновении коллизий, объект помещается в ту же ячейку в связный список. Но по какому принципу они распределяются? На первую пустую ячейку, или по какой-то логике? И почему поиск по хеш коду быстр? Как он их ищет?
Ответы (2 шт):
Грубо говоря, хранилище HashSet - это просто массив. Хэш значения определяет по какому индексу в массиве будет храниться это значение. Соответственно и поиск - это просто обращение по индексу, поэтому и быстро.
Да, это массив.
Нет, пустой элемент массива не ищет. Это метод открытой адресации разрешения коллизий. В HashSet применяется метод цепочек: в случае коллизии объект помещается в тот же элемент массива в односвязанный список. При достижении размера массива указанном в TREEIFY_THRESHOLD (8 по умолчанию) - уже не в односвязанный список, а в красно-черное бинарное дерево.
Какой будет индекс вычисляется на основании хеша и размера массива.
Ищет также, как вычисляется индекс. Т.е. мы не проходимся в поисках по всему массиву, а вчисляем индекс и сразу обращаемся по нему к нужному элементу.
Поэтому и быстро: O(1) при отсутствии коллизий.
Вообще, в HashSet все точно также, как в HashMap. Только в роли key вычтупает само value. Под капотом у HashSet мапа и работает.