Класс Java Hashtable - эта штука работает так, как я думаю? Конкретные вопросы включены

Question

У меня есть класс с именем Node, который я написал. Я переопределил его функцию hashCode (), чтобы учесть два поля узла (есть также третье поле, которое не влияет на функцию my hashCode ()). Я также написал функцию equals (), которая учитывает все три поля.

Я пытаюсь использовать класс Hashtable для хранения узлов, чтобы впоследствии я мог легко проверить при создании новых узлов, являются ли новые узлы дубликатами узлов в хеш-таблице или нет. Пока у меня есть это

 Hashtable<Node,Node> hashTbl = new Hashtable<Node,Node>();
 ...
 Node node1 = // some new node
 hashTbl.put(node1,node1);
 ...

Итак, скажем, я создаю новый узел с именем node2, который имеет точно такое же значение хеш-функции, что и node1, но не равен node1, как определено методом equals (). Я хочу проверить, является ли node2 дубликатом чего-либо в хеш-таблице (это не так), но если я использую constainsKey (), разве это не даст мне ложный положительный результат? Кажется, что использование containsValue () не будет использовать эффективность хэш-таблицы. Так как я могу сделать это эффективно?

Кроме того, я предполагаю, что когда я вызываю hashTbl.put (arg1, arg2), он вызывает функцию hashCode () arg1 и использует это значение, чтобы найти индекс в «массиве» для размещения arg2. Является ли это право?

Извините за то, что я немного запутался. Всем спасибо.

Answer 1

Во-первых, вам, вероятно, нужен HashSet (или что-то подобное), а не Hashtable - все, что вы пытаетесь сделать, - это проверять членство, и HashSet позволит вам сделать это без необходимости указывать значение для каждого ключа.

Чтобы ответить на ваш вопрос, определяется, в какой слот в массиве помещается значение, но каждый слот на самом деле является связанным списком. Если новый ключ не равен .equal любому другому ключу в связанном списке, новый ключ и значение помещаются в их собственный узел в связанном списке. Простое возвращение 1 для всех объектов является совершенно законной и правильной .hashcode реализацией. Единственная проблема с этой реализацией состоит в том, что она превращает Hashtables и подобные структуры данных в связанные списки (что, очевидно, приводит к потере всех преимуществ производительности Hashtable).

Короче говоря, ваш метод .hashcode будет работать нормально. Если вы поместите большое количество объектов, которые не .equal, но имеют одинаковый хэш-код, производительность снизится, но код все равно будет работать правильно.

Answer 2

Вы, по сути, правы: хеш-таблица (кстати, HashMap - более новый, более рекомендуемый класс) использует hashCode(), чтобы найти корзину для помещения вашего объекта. Если есть столкновение (другой объектв том же сегменте), он использует список в каждом сегменте, используя equals(Object), чтобы выяснить, равен ли этот новый объект одному из объектов в хэше (или, при поиске, чтобы увидеть, соответствует ли ключ поиска)одна из пар ключ-значение).Таким образом, в худшем случае всех коллизий ваш хэш превращается в список с O (N) операциями.Как вы указали, это неэффективно.

Пока ваш equals(Object) правильный, функциональной проблемы не будет - просто проблема эффективности, если ваш хэш-код вызывает слишком много конфликтов.В принципе, если два объекта равны, они должны иметь одинаковый hashCode для корректности;если два объекта не равны, они должны иметь разные хэш-коды для эффективности хеширования.

Answer 3

HashTable (или HashMap) содержит N корзин, где корзина может содержать более одного объекта.(Каждый бин фактически является связанным списком Map.Entry).HashCode () ключа используется для определения корзины.Однако после определения ячейки для ключа используется метод equals (), чтобы узнать, существует ли уже ключ.Итак, если вы поместите node1 и node2 в HashTable, и оба имеют одинаковый hashCode (), но не равны, они попадут в один и тот же bin, но этот bin будет связанным списком длины два с двумя ключами, node1и node2, и соответствующие значения.

containsKey () НЕ даст вам ложное срабатывание, так как он будет использовать hashCode (), чтобы найти ячейку, но затем выполнит равные для всех ключей для этого ячейки.Наличие одинакового hashCode для набора ключей делает HashTable медленным и неэффективным (если все значения имеют одинаковый hashCode, по сути, вы сохраняете его в связанном списке), но не нарушает контракт.