Как хеш-таблицы разрешают неопределенность сегментов и пробники?

Question

Я читаю структуры данных, а также алгоритмы и принципы программного обеспечения в C, чтобы попытаться обернуть голову вокруг некоторых внутренних структур данных, и меня действительно беспокоят две вещи:

(1) Как хеш-таблицы решают, какой элемент в корзине является предметом, который вы ищите, если все они имеют одинаковый хеш?

например

1. Получить ключ, значение
2. используйте алгоритм Hash для ключа, чтобы найти индекс, чтобы попытаться поместить значение в
3. если слот занят, но нет сегмента (отдельная запись), создайте блок и бросьте текущий элемент в корзину, а затем добавьте в него текущее значение.
4. теперь у меня есть корзина с кучей значений и "потерянной и найденной проблемой", где вы не можете сказать, какое значение принадлежит какому ключу, потому что все ключи отображаются на один и тот же хэш, а у элемента в корзине нет ключа для поиска ведро под ключ.

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

(2) Как хеш-таблицы сообщают, является ли значение в индексе правильным значением для ключа, или если зондирование обнаружило столкновение и поместило его в другое место.

например.

1. Получить ключ, значение
2. ключ хеша для поиска индекса (0)
3. По индексу, взятому, используйте алгоритм простого наведения для выполнения линейного поиска, пока слот не найден (слот 1 пуст)
4. теперь я ищу свой ключ и нахожу индекс 0. Как хэш узнает, что индекс 0 не является правильным элементом для этого ключа, но что он был обнаружен в слоте 1?

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

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

Извините за грубо сформулированный вопрос, но я просто должен был спросить.

Спасибо заранее

Answer 1

Хеш-таблицы сохраняют запись. Запись состоит из ключа и значения.

Как хеш-таблицы решают, какой элемент в корзине является предметом, который вы ищите, если все они имеют одинаковый хеш?

Потому что запрос выполняется путем передачи ключа.

Целью хеширования является сокращение времени на поиск индекса. Их ключ хэшируется, чтобы найти правильное ведро. Затем, когда элементы были уменьшены с общего N до очень малого n, вы можете даже выполнить линейный поиск, чтобы найти нужный элемент из всех ключей, имеющих одинаковый хэш.

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

Опять же, это потому, что Hash Table будет сохранять записи, а не только значение. Если в случае коллизии хэш-таблица видит, что ключ, найденный в этом сегменте, не является ключом, который запрашивается, то хеш-таблица знает, что коллизия произошла раньше, и ключ может находиться в следующем интервале. Обратите внимание, что в этом случае в корзине хранится одна запись, в отличие от первого ответа, где в корзине может храниться LinkedList или Дерево записей.