Как реализовать хеш-таблицу с цепочкой?

Question

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

Это то, что я понимаю:

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

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

Что я не понимаю, так это:

Когда вы вводите ключ и хеш-функция создает местоположение, в котором происходит связывание, как оно определяет, какое значение в связанном списке в этом месте принадлежит этому конкретному ключу, а не другому ключу, участвующему в коллизии?

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

Answer 1

Простой способ: поддерживать связанный список «записей хеш-таблицы», которые являются парами ключ / значение. Как только вы попадете в корзину, проверьте ключ запроса по всем ключам в корзине.

Answer 2

Когда вы вводите ключ и хеш-функция создает местоположение, в котором происходит связывание, как оно определяет, какое значение в связанном списке в этом месте принадлежит этому конкретному ключу, а не другому ключу, участвующему вколлизия?

Вы просто прибегаете к линейному поиску сегмента по ключу.

Вы можете оценить следующую реализацию мини-хеш-таблицы, написанную на F #, взятую из этого блогаpost :

> let hashtbl xs =
    let spine = [|for _ in xs -> ResizeArray()|]
    let f k = spine.[k.GetHashCode() % spine.Length]
    Seq.iter (fun (k, v) -> (f k).Add (k, v)) xs
    fun k -> Seq.pick (fun (k', v) -> if k=k' then Some v else None) (f k);;
val hashtbl : seq<'a * 'b> -> ('a -> 'b) when 'a : equality

Эта hashtbl функция берет последовательность ассоциации xs пар ключ-значение, создает хеш-таблицу, представленную в виде spine массива ResizeArray сегментов и возвращаетлямбда-функция, которая находит соответствующий сегмент и выполняет в нем линейный поиск для заданного ключа k.Линейный поиск выполняется с использованием функции Seq.pick.