Как данные извлекаются из HashTable при столкновении?

Согласно этому, временная сложность поиска в хеш-таблице составляет O(1).

Однако, если есть столкновение, то, очевидно, это должно быть O (1) + что-то.

Мой вопрос:

Когда ты говоришь

get(someKey)

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

Но представьте, что для разрешения коллизий используется раздельная цепочка. И представьте, что someKey и someOtherKey имеют одинаковый вывод после применения к ним нашей функции хеширования. Скажите, что это значение «25».

Поэтому, когда я говорю

get(someKey)

Я получу данные из локации "25". Что делает его O (1). Здорово.

Однако, когда я говорю

get(someOtherKey)

Теперь someOtherKey связан с someKey.

Когда хеширование применяется к someOtherKey, я получаю 25.

Как мне получить нужную мне ценность? Какие внутренности? Есть какой-то другой стол? Как работает алгоритм? Есть ли какая-то другая таблица для хранения всех коллизий?

Спасибо. Надеюсь мой вопрос понятен!


hashmap hash hashtable hashcode hash-collision
person Koray Tugay    schedule 30.03.2013    source источник
comment
Вот очень хороший ресурс по этому вопросу: youtube.com/   -  person Koray Tugay    schedule 30.03.2013

Ответы (1)


arrow_upward
3
arrow_downward

Для обработки коллизий возможно множество различных структур данных. Вот хорошее резюме. http://en.wikipedia.org/wiki/Hash_table.

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

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

person Mark Taylor    schedule 30.03.2013
comment
Спасибо. Итак, хеш-таблица хранит ведра, а не значения напрямую? - person Koray Tugay; 30.03.2013
comment
Это зависит от реализации. Некоторые проекты могут быть структурированы таким образом, чтобы определенное количество значений хранилось непосредственно в структуре данных в корзине и перетекало во вторичную структуру только после того, как корзина заполнена. Особенно имеет смысл хранить одно значение в корзине, а затем иметь указатель на связанный список для любых вторичных значений. Таким образом, первый узел связанного списка остается в корзине. - person Mark Taylor; 30.03.2013
comment
Это также зависит от размера значений. Хеш-таблица общего случая, реализованная в библиотеке, должна быть гибкой для многих возможных размеров и диапазонов значений. Если набор данных (количество значений, диапазон значений) известен заранее, можно разработать конкретную структуру, которая будет более эффективной, чем общий случай. Это просто большая работа, которая того стоит только в крайних случаях. - person Mark Taylor; 30.03.2013