Цепочка хеш-таблиц

 public void put(int key, int value) {
        int hash = (key % TABLE_SIZE);
        if (table[hash] == null)
            table[hash] = new LinkedHashEntry(key, value);
        else {
            LinkedHashEntry entry = table[hash];
            while (entry.getNext() != null && entry.getKey() != key)
                entry = entry.getNext();
            if (entry.getKey() == key)
                entry.setValue(value);
            else
                entry.setNext(new LinkedHashEntry(key, value));
        }
    }

Я только изучаю концепцию цепочки хеш-таблиц и подумал, добавим ли мы новый элемент. мы увидим, существует ли ключ элемента, если да, мы просто свяжем его с тем же узлом с тем же ключом. Но только что нашли этот код в Интернете под заголовком цепочки хэш-таблиц, но он не делает то, что я предполагал to .it либо я ошибаюсь, либо этот код. эта часть меня больше всего смущает:

if (entry.getKey() == key)
                entry.setValue(value);

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

Спасибо,


person user2333934    schedule 29.04.2013    source источник
comment
Этот код выглядит правильно. Упомянутая вами строка использует существующий узел и перезаписывает правильное значение. Не могли бы вы уточнить, что вас беспокоит?   -  person raptortech97    schedule 30.04.2013
comment
Часть, которая отличается в цепочке, - это случай else.   -  person Louis Wasserman    schedule 30.04.2013


Ответы (1)


Цепочка хеш-таблиц — это своего рода реализация хэш-таблицы. Он используется для уменьшения коллизии хеш-хэшей. Например, хеш-значение элемента с именем A равно 100, а в таблице [100] уже существует другой элемент. Чтобы ввести элемент A, в случае хеширования открытого адреса, элемент A будет вставлен с индексом 101 в таблицу, что добавит вероятность коллизии хэшей (если в будущем хеш-значение другого элемента равно 101). И цепочки хеш-таблиц не будет.

person chncwang    schedule 30.04.2013