[java] Hash Array Mapped Trie (HAMT)



Answers

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

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

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

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

Я нашел хорошую статью статьи, которая описывает HAMT с картинками и ссылками на оригинальные research papers Фила Багвелла.

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

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

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

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

Question

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

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

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

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

Я должен что-то упустить .....

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

Data Structure                    Add time   Remove time     Sorted add time Sorted remove time   Lookup time     Size     
Java's 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's Tree Map                   86.33 ms   78 ms           75 ms           39.33 ms             76 ms           8.79 MB        
Java's Skip List Map              111.33 ms  106 ms          72 ms           41 ms                72.33 ms        9.19 MB     



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






Links