Путаница с линейным зондированием методом открытой адресации в хеш-таблицах?

Question

Предположим, что индекс массива в соответствии с функцией хеширования для строки "temp" равен 155, а ячейка 155 занята, после чего проверяется ячейка 156.Предположим, что местоположение 156 доступно, поэтому эта запись сохраняется в местоположении 156 вместо 155. Позже я нахожу другую строку «another_temp», которая сопоставляется с местоположением 156. И снова это сохраняется в следующем доступном местоположении 157.

Вопрос в следующем: если я захочу узнать местоположение «another_temp», как я узнаю, что это 157, а не 156, хотя хэш-функция вернула 156?

Спасибо.

Answer 1

Вам нужно сравнить ключ, а не только хеш-код.В хеш-таблице вам все равно нужно хранить ключ («temp» и «another_temp» в вашем случае).Недостаточно просто сохранить и сравнить хеш-значение, потому что хеш-значения не являются уникальными.

Есть несколько проблем с открытой адресацией.Один из них: что делать после удаления записи?Обычно вы храните специальный «удаленный» маркер.Другая проблема: если есть коллизия, следует ли увеличивать хэш-код?Вы найдете больше деталей в Википедии.