Я понимаю, что если в хеш-таблице происходит столкновение, у вас есть несколько вариантов сохранения данных. Вы можете использовать некоторое простое число для линейного обхода массива, пока не найдете свободное место. Вы также можете перефразировать всю таблицу в больший массив. Я уверен, что есть и другие способы. Чего я не понимаю, так это того, что если произойдет столкновение, то как вы узнаете, какая строка данных является той, которую вы искали? Могу ли я просто не разрешить использование дубликатов ключей?
Путаница с поиском информации в хеш-таблице при возникновении коллизии
Ответы (1)
Между хешем и ключом есть большая разница (хотя иногда они могут совпадать).
Ключ может быть очень большим числом, сложным объектом, состоящим из множества полей или чем-то еще.
Вы применяете свою хэш-функцию к этому ключу, чтобы получить хэш.
Таким образом, даже если вы запретите дублирование ключей, у вас все равно могут быть дубликаты хэшей.
Вы часто не можете использовать свой ключ как хеш напрямую, потому что индексы массива представляют собой последовательные целые числа, начинающиеся с 0, поэтому он не будет работать, если ваш ключ слишком большой, отрицательный или не является целым числом, и вам придется применить какой-то вид хеш-функции.
Если вы хотите хранить числа от 1 до 10000, вы бы позволили ключу быть самим числом и могли бы сделать хэш остатком от числа, деленного на 1000 (и, таким образом, у вас будет массив размером 1000 для хэш-таблицы) .
Вставка 1001 поместит его в индекс 1. Если вы попытаетесь вставить 2001, он также попытается перейти в индекс 1, и у вас будет коллизия.
* Ключ может быть либо всем значением, которое вы хотите сохранить, либо только его идентификатором.
person
Bernhard Barker
schedule
15.09.2015
Поэтому я бы запретил повторяющиеся ключи, использовал бы ключ для хэширования в место в таблице, сохранил бы уникальный ключ, если бы произошло столкновение, я бы разрешил его, и если бы я использовал ключ для получения информации, я бы проверил, были ли ключи то же самое, чтобы определить, была ли у меня правильная информация, когда я нашел место на столе, к которому я хэшировал?
- person Crinkley Crewms; 15.09.2015
@CrinkleyCrewms Да, это звучит правильно. Обратите внимание, что если вы ищете элемент, вам нужно будет сделать что-то похожее на ваши действия по разрешению коллизий, чтобы найти все возможные элементы, соответствующие этому хешу, например, для линейное исследование, вам нужно будет начать с индекса, соответствующего хэшу, и повторять массив, пока не найдете пустое место, потому что после этого ничего не будет. spot может иметь один и тот же хэш (удаление элементов нетривиально) и сравнивать каждый ключ с ключом, который вы ищете, чтобы увидеть, существует ли он в таблице.
- person Bernhard Barker; 15.09.2015
