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

Согласно this, временная сложность поиска в хеш-таблице равна O (1).Как данные извлекаются из HashTable при столкновении?

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

Мой вопрос:

Когда вы говорите

get(someKey)

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

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

Так что, когда я говорю

get(someKey)

я буду получать данные от местонахождения "25". Что делает его O (1). Отлично.

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

get(someOtherKey)

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

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

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

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

источник

2013-03-30 Koray Tugay

Вот очень хороший ресурс по этому вопросу: http://www.youtube.com/watch?v=UPo-M8bzRrc&list=EC4BBB74C7D2A1049C&index=21 –

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

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

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

источник

2013-03-30 15:50:59

Спасибо. Итак, хеш-таблица хранит ведра, а не значения напрямую? –

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

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

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

ответ

Смежные вопросы