Hash Array Mapped Trie (HAMT)

Я пытаюсь разобраться с деталями HAMT. Я бы реализовал сам в Java, чтобы понять. Я знаком с Tries, и я думаю, что получаю основную концепцию HAMT.

В принципе,

Два типа узлов:

Key/Value

Key Value Node:
  K key
  V value

Индекс

Index Node:
  int bitmap (32 bits)
  Node[] table (max length of 32)

Сгенерировать 32-битный хэш для объекта.
Шаг через хэш 5-бит за раз. (0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-31) Примечание: последний шаг (7-й) - всего 2 бита.
На каждом шаге найдите позицию этого 5-битного целого в растровом изображении. например integer==5 bitmap==00001
- Если бит равен 1, то эта часть хэша существует.
- Если бит равен 0, ключ не существует.
Если ключ существует, найдите его индекс в таблице, посчитав число 1 в битовой карте между 0 и позицией. например integer==6 bitmap==0101010101 index==3
- Если таблица указывает на ключ/значение node, то сравните ключи.
- Если таблица указывает на индекс node, перейдите к следующему шагу.

Часть, которую я не совсем понимаю, - это обнаружение и смягчение конфликтов. В связанной статье он ссылается на него:

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

Если бы я должен был вычислить "новый" хеш и сохранить объект в этом новом хеше; как бы вы могли найти объект в структуре? Когда вы выполняете поиск, не генерирует ли он "начальный" хеш, а не "пересчитанный хеш".

Мне что-то не хватает.....

BTW: HAMT работает достаточно хорошо, он сидит между картой хэша и картой дерева в моих тестах.

Data Structure                    Add time   Remove time     Sorted add time Sorted remove time   Lookup time     Size     
Java Hash Map                   38.67 ms   18 ms           30 ms           15 ms                16.33 ms        8.19 MB        
HAMT                              68.67 ms   30 ms           57.33 ms        35.33 ms             33 ms           10.18 MB       
Java Tree Map                   86.33 ms   78 ms           75 ms           39.33 ms             76 ms           8.79 MB        
Java Skip List Map              111.33 ms  106 ms          72 ms           41 ms                72.33 ms        9.19 MB

Ответ 1

Вот два раздела статьи, которые, я думаю, вы могли пропустить. Первый бит - бит, непосредственно предшествующий бит, который вы указали:

Или ключ столкнется с существующим. В этом случае существующий ключ должен быть заменен вспомогательной хэш-таблицей, а следующий 5-битный хэш существующего ключа вычислен. Если по-прежнему происходит столкновение, то этот процесс повторяется до тех пор, пока не произойдет столкновение имеет место.

Итак, если у вас есть объект A в таблице, и вы добавляете объект B, который сталкивается, ячейка, с которой сталкиваются их ключи, будет указателем на другую подтаблицу (где они не сталкиваются).

Далее, в разделе 3.7 документа, который вы связали, описан метод генерации нового хэша, когда вы заканчиваете первые 32 бит:

Хэш-функция была адаптирована для получения 32-битного хэша. Алгоритм требует, чтобы хэш может быть расширен до произвольного количества бит. Это было достигнуто переименование ключа в сочетании с целым числом, представляющим уровень trie, ноль - корень. Следовательно, если два ключа дают один и тот же начальный хэш, тогда пересмотр имеет вероятность 1 в 2 ^ 32 дальнейшего столкновения.

Если это ничего не объясняет, скажем, и я продолжу этот ответ более подробно.

Ответ 2

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

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

В настоящее время я также изучаю HAMP в контексте функционального программирования и изучая существующий код. Существует несколько эталонных реализаций HAMT в Haskell как Data.HshMap и в Clojure как PersistenceHashMap.

В Интернете есть несколько других простых реализаций, которые не имеют дело с коллизиями, но они полезны для понимания концепции. Здесь они находятся в Haskell и OCaml

Я нашел замечательную статью статьи в целом, которая описывает HAMT с картинками и ссылками на оригинальные исследование документы от Фила Багвелла.

Связанные пункты:

При реализации HAMT в F # я заметил, что реализация функции popCount, описанная здесь, действительно имеет значение и дает 10-15% по сравнению с наивной реализацией, описанной в следующих ответах в ссылка. Не большой, но бесплатный обед.

Связанные структуры IntMap (Haskell и его порт для F #) очень хороши, когда ключ может быть целым, и они реализуют связанные PATRICIA/Radix trie.

Я считаю, что вся эта реализация очень хороша для изучения эффективной неизменной структуры данных и функциональных языков во всей их красоте на этих примерах - они действительно сияют вместе!

Ответ 3

Если бы я должен был вычислить "новый" хеш и сохранить объект в этом новом хэш; как бы вы могли найти объект в состав? Когда вы делаете поиск, не генерирует ли он "начальную", хэш, а не "пересчитанный хеш".

При выполнении поиска используется начальный хеш. Когда бит в начальном hash исчерпан, либо выполняется одно из следующих условий:

мы получим ключ/значение node - вернем его
мы получим индекс node - это намек на то, что нам нужно идти глубже, пересчитывая новый хеш.

Ключ здесь - хэш-бит исчерпание.

Ответ 4

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