Почему HashSet имеет в своем имени «Hash»?

Question

Почему Hashset называется "Hash" -set?

Я понимаю, что мы называем hashtable или hashmap, поскольку это хранилище значений ключей, и когда мы помещаем (), ключ хэшируется и распределяется равномерно с использованием хорошей хэш-функции.

Я предполагаю, что он называется HashSet, потому что когда мы добавляем (), значение хешируется и сохраняется, чтобы сохранить его уникальным. Но почему перебор? На самом деле мы не заботимся о «равном распределении» данных, как в хэш-таблице.

Answer 1

Мы заботимся о равном распределении, потому что хотим, чтобы наши базовые операции Collection работали постоянно. Чтобы соблюдать основные правила SET, нет двух одинаковых объектов, мы хотим быстро найти потенциально равное совпадение. HashSet - один из довольно хороших способов сделать это. Сравните с теоретическим ArraySet, где добавление нового элемента является линейной временной операцией для итерации и проверки каждой существующей записи на равенство.

Answer 2

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

Answer 3

HashSet (например, HashMap) использует, ну, хэширование, для достижения O (1) амортизируется устанавливает / тестирует / удаляет производительность. (В вопросе о некоторых ошибочных предположениях былоHashSet не использует хеширование.)

Теперь в Java все объекты являются "хэшируемыми" - то есть они имеют функцию hashCode() (так как они являются потомками Объект ).Качество этой хеш-функции позволит алгоритму хеширования достичь ожидаемых характеристик производительности, описанных выше, «распределив объекты [равномерно] через сегменты».(Реализации объекта по умолчанию hashCode / равно сумма для идентификатора объекта. Как правило, это должно быть изменено для любого подкласса.)

Однако, если ваш класс плохо реализует hashCode (например, возвращает 1 для всех значений), тогдапроизводительность HashSet / HashMap сильно пострадает в результате (для любого нетривиального n).Важно отметить, что hashCode определяет сегмент , но equals определяет, собственно, фактическое равенство, которое можно использовать , даже если хеш-код уникален и / или существуетнет коллизий (например, чтобы убедиться, что test / get не возвращает ложноположительный результат - его можно было бы устранить при установке / вставке без коллизий).

Просто следуйте инструкциямустановка требований в Object wrt.hashCode и equals или объекты могут быть потеряны.Плохая функция хеширования, которая соблюдает правила, все равно будет работать, хотя и с потенциально низкой производительностью.(Изменяемый объект особенно проблематичен для использования в хеш-ADT, потому что хеш-код и / или равенство не всегда могут быть стабильными.)

Answer 4

Что такое «перебор»? Идея HashXXX для любого X состоит в том, чтобы обеспечить производительность O (1), а это достигается хэшированием. Если вам не нужна производительность O (1), не используйте ее. Например, используйте TreeSet.