Hashtable, Hashfunction: разница между значением, ключом, хэш-значением?

Question

Давайте представим, что у нас есть данные, которые мы хотим поместить в Hashtable. Функция Hash вычисляет значение Hashvalue для каждого объекта данных и помещает эти значения хеш-значений в таблицу (каждое значение должно получить свой собственный сегмент). С помощью хеш-значения мы знаем точное положение объекта данных в таблице.

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

Мне интересно, в чем разница между значением, которое мы хотим поместить в Hashtable (в java Hashmap), hashvalue и ключом? Что за математика стоит за этим?

Answer 1

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

Логично, что выборка из хеш-таблицы:

• Вычислить хеш-код ключа, который мы ищем
• Найти все записи, которые имеют одинаковый хэш-код. (Это будет быстро, потому что мы имеем дело только с числом, и мы можем организовать структуру данных, которая позволяет легко находить записи с заданным хеш-кодом. Здесь есть множество вариантов.)
• Для каждой записи с правильным хеш-кодом сравните ключ, который мы ищем, с ключом в записи.
  • Если существующий ключ и ключ, который мы ищем, равны, верните значение для этой записи
• Нет совпадений? Вернуть null чтобы указать этот результат.

(Точный способ, которым хеш-таблица делится на сегменты, является подробностью реализации. Иногда каждый сегмент содержит только одну запись, но может быть связан с другими сегментами; в других случаях сегмент может содержать несколько записей. См. Запись в Википедии по хэшу таблицы для получения дополнительной информации.)

Здесь "запись" является {key, value, hash} кортеж:

• Хеш получен полностью из ключа; значение не имеет значения
• Там никогда не будет двух равных ключей
• Может быть несколько записей с одинаковым значением; значение равенства не имеет значения
• Может быть несколько записей с одинаковым хешем из-за коллизий хешей; это актуально, так как есть больше записей для просмотра при поиске соответствия для определенного ключа