Отображение хэш-массива Trie (HAMT)

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

В основном,

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

Ключ/значение

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. At each step, find the position of that 5-bit integer in the bitmap. e.g. integer==5 bitmap==00001
    1. If the bit is a 1 then that part of the hash exist.
    2. Если бит равен 0, то ключ не существует.
  4. If the key exists, find it's index into the table by counting the number of 1s in the bitmap between 0 and the position. e.g. integer==6 bitmap==0101010101 index==3
    1. If the table points to a key/value node then compare the keys.
    2. Если таблица указывает на индексный узел, перейдите к 2, продвигаясь на один шаг вперед.

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

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

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

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

Кстати: 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

java algorithm hash data-structures trie
person Justin    schedule 31.10.2013    source источник

Ответы (4)


arrow_upward
7
arrow_downward

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

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

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

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

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

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

person Andy Jones    schedule 23.11.2013
comment
Спасибо за это; Я все еще пытаюсь понять это в данный момент. Я вернусь к вам. - person Justin; 23.11.2013
comment
В разделе 3.7 предполагается, что хэш является функцией нескольких входных данных с уровнем дерева в качестве своего рода начального числа, но в таких языках, как Java и C#, часто хеш-код является примитивным методом объекта и, таким образом, имеет только один вход (объект). . Я не вижу никакого способа применить раздел 3.7 к таким языкам, а это значит, что лучшее, что вы можете сделать, это просто сохранить список коллизий в листе и искать его линейно. - person naasking; 22.04.2014
comment
Оберните объекты, помещаемые в структуру данных, в класс Node, затем вставьте Node, а не обернутый объект, в HAMT. Затем вы можете определить необходимую хеш-функцию с несколькими аргументами в классе Node. - person Andy Jones; 22.04.2014
comment
Хэш, сгенерированный из базового объекта, остается тем же самым, что означает, что любой хэш, сгенерированный из узла, также будет таким же, если только не будет включено какое-либо недетерминированное значение, например адрес узла. Но вы не можете знать адрес узла при поиске своего ключа, поэтому вы можете вставлять на бесконечную глубину, но вы больше не можете выполнять поиск. Я не вижу, как ваше предложение решает проблему. - person naasking; 23.04.2014
comment
Таким образом, функция customHash Node берет примитивный хэш объекта, содержащегося в Node, и объединяет его с целым числом, представляющим уровень дерева (переданным в качестве аргумента), и возвращает хэш результата. Если вы хотите проверить, находится ли объект в HAMT, вы вставляете его в объект Node и используете customHash, чтобы найти его местоположение на уровне. Ни в коем случае вы не ссылаетесь на примитивный хэш Node. - person Andy Jones; 23.04.2014
comment
Давайте рассмотрим конкретный пример: у нас есть два ключа, k1 и k2, где k1!=k2, и их конфликтующий хэш-код равен 42. Покажите мне любой customHash, который может принимать 42 и уровень дерева и детерминистически выдавать разные выходные данные для k1 и k2. . - person naasking; 23.04.2014
comment
Ага, извините, теперь я вижу вашу проблему. Так что проблема не в том, что хэш-код не может принимать несколько входных данных, а в том, что его нельзя расширить до уникальности. Я не понимаю, почему это проблема, характерная для управляемых языков, таких как Java или C#? - person Andy Jones; 23.04.2014
comment
Единственное решение, которое я вижу для любого языка, заключается в том, что каждый тип, вставленный в HAMT, должен иметь пользовательскую функцию, которая будет возвращать хэш, расширяемый вплоть до уникальности класса эквивалентности. - person Andy Jones; 23.04.2014
comment
Да, уникальность — это цель, я просто говорю, что единственный способ добиться этого — сделать так, чтобы функция хэш-кода primitive была функцией нескольких входов. Но это невозможно в Java/C#, если вы не напишете какую-то пользовательскую общую хеш-функцию, которая использует отражение, или, как вы сказали выше, требуя, чтобы каждый тип реализовывал пользовательскую функцию хеш-кода. - person naasking; 23.04.2014
comment
Какие языки имеют такой подходящий примитивный хэш-код? - person Andy Jones; 23.04.2014
comment
Ни у кого нет его примитивно, но вы можете написать его в общем на C/C++ и Ada, поскольку у них есть указатели. Вы также можете потребовать такую ​​хэш-функцию в Haskell, поскольку она поддерживает специальную перегрузку через классы типов. Единственный способ сделать это специальным образом в Java/C# — через отражение или просто отказаться и сделать то, что я сделал с моим C# HAMT, и сохранить коллизии в листе, который ищется линейно. - person naasking; 23.04.2014
comment
Например, вы используете адрес объекта в качестве хэш-кода? Это кажется немного опасным, поскольку оно не постоянно в течение жизни объекта. Конечно, вы можете кэшировать его при создании, но это не сделает вас лучше, чем определить собственную хеш-функцию. И разве вы не можете имитировать подход Haskell в Java/C#, используя подклассы и параметры ограниченного типа? Я полагаю, не будет работать на final классах. - person Andy Jones; 23.04.2014
comment
Не адрес для хеша, а функция будет выглядеть как int hash(void* obj, int nbytes, int seed). Итак, хэш содержимого объекта указывает на. Что касается Java/C#, то требование от клиентов вашего HAMT к подклассу не кажется разумным. Вы можете имитировать подход Haskell, передав явный делегат (C#)/анонимный класс (Java) в качестве хеш-функции. Все еще немного раздражает, и коллизии не должны быть настолько распространенными, чтобы линейный поиск был проблемой, за исключением огромных деревьев. Редактировать: и переданная хэш-функция должна фактически правильно использовать начальное значение, чтобы хэш работал правильно. - person naasking; 23.04.2014

arrow_upward
6
arrow_downward

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

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

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

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

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

По теме:

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

Связанные структуры IntMap (Haskell и его < href="https://github.com/fsharp/fsharpx/blob/master/src/FSharpx.Collections.Experimental/IntMap.fs" rel="nofollow noreferrer">порт на F#) очень хороши когда ключ может быть целым числом, и они реализуют связанные PATRICIA/Radix trie.

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

person V.B.    schedule 07.11.2013

arrow_upward
1
arrow_downward

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

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

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

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

person holygeek    schedule 25.07.2014

arrow_upward
0
arrow_downward

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

person naasking    schedule 20.04.2014
comment
Хотя это не соответствует строгому определению HAMT, это может быть лучшим подходом; Я измерю дополнительные затраты памяти, необходимые для переноса другого массива или связанного списка. Я дам Вам знать. - person Justin; 21.04.2014