Хеширование C++: открытая адресация и цепочка

Для цепочки:

Может кто-нибудь объяснить мне эту концепцию и предоставить мне теоретический пример и простой код?

Я понимаю, что «Каждое местоположение таблицы указывает на связанный список (цепочку) элементов, которые хешируются в этом местоположении», но я не могу проиллюстрировать, что на самом деле происходит.

Предположим, у нас есть h(x) (функция хеширования) = x/10 mod 5. Теперь хешируем 12540, 51288, 90100, 41233, 54991, 45329, 14236, как это будет выглядеть?

А что касается открытой адресации (линейное зондирование, квадратичное зондирование и зондирование для каждого местоположения R), может ли кто-нибудь объяснить это и мне? Я пытался погуглить, но, кажется, еще больше запутался.


c++ addressing hash chaining
person forthewinwin    schedule 01.06.2012    source источник

Ответы (3)


arrow_upward
4
arrow_downward

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

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

Вот Java-анимация хэш-таблица.

person James    schedule 01.06.2012

arrow_upward
2
arrow_downward

потому что вы делаете мод 5, ваш стол будет иметь 5 локаций

местоположение 0: 90100

потому что результат 90100/10 mod 5 равен 0

по той же причине у вас есть:

местоположение 1: нет

местоположение 2: 45329

адрес 3: 51288->41233->14236

адрес 4: 12540->54991

вы можете найти дополнительную информацию в википедии

person xvatar    schedule 01.06.2012

arrow_upward
1
arrow_downward

При открытой адресации мы должны хранить элемент в таблице любым из способов (коэффициент загрузки меньше единицы).

Но в случае цепочки хэш-таблица хранит только указатели на заголовки списка ссылок, поэтому коэффициент загрузки может быть больше единицы.

person user1362740    schedule 01.06.2012
comment
Имеет значение только сохранение указателей на голову. Однако коэффициенты нагрузки, близкие к 1, встречаются редко. Смысл хеш-таблиц в том, чтобы избежать медленного поиска, а линейный поиск по спискам медленный, плюс есть случайное (не совсем сбалансированное) распределение хэшей. Производительность быстро падает при коэффициенте загрузки от 0,5 до 0,7. Обычно (большинство стандартных библиотечных хеш-таблиц), когда коэффициент загрузки достигает некоторой постоянной доли, новой таблице выделяется на несколько постоянных коэффициентов больше, и все элементы копируются. Это звучит неэффективно, но в амортизированном смысле все еще дает ожидаемое O (1). - person Steve314; 01.06.2012
comment
При открытой адресации при увеличении коэффициента загрузки мы перехэшируем таблицу. Использование большого размера таблицы, а затем повторная вставка ключей с использованием функции хеширования. - person user1362740; 05.06.2012