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

Question

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

Answer 1

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

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

Answer 2

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

• Используйте две хеш-таблицы, одна из которых хранит ключ -> значение, другая - другую часть отношения - значение -> ключ
• Используйте реализацию двунаправленного хеш-таблицы (у Google есть одна спецификация здесь ), которая поддерживает это, делая то же самое внутри

Answer 3

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

2 общих подхода:

• Неудача.Не вставляйте новый ключ / значение, но укажите, что ключ уже существует.
• Замените существующий ключ / значение и верните старую пару ключ / значение.

A 3Опция, которую я, по крайней мере, много не видел в любой реализации хеш-таблиц C / C ++:

• Сохраните исходный ключ, но обновите / замените новое значение для этого ключа

Answer 4

a) Вы предполагаете конкретную реализацию вашей хеш-таблицы b) Это очень сильно зависит от реализации.

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