Hash array mapped trie — это ассоциативный контейнер, который обладает свойствами хэш таблиц и trie. Операции вставки пары ключ-значение и поиск по ключу — О(1) операции.
Про trie на хабре уже писали.
В trie достаточно часто хранят строки, поэтому есть понятие алфавита, из которого могут состоять элементы. Для оптимизации под x32 ограничивают размер алфавита до 32 ( 0 — 31 ).
Давайте посмотрим, как выглядит array mapped trie, оно же AMT ( взято из [1] ):
AMT состоит из узла и нескольких отрезков, соединяющих наш узел и другие узлы. Каждый отрезок представляет собой один из возможных символов алфавита.
В узле хранится 32-битная структура ( bitmap ), каждый бит структуры отражает состояние одного из 32 отрезков ( 0 — нет, 1 — есть ). Также в узле находится таблица, в которой хранятся указатели на поддеревья или последние символы в данной подстроке ( листья ). Указатели в таблице хранятся упорядоченно, и каждому из указателей соответствует бит = 1 в битовой структуре.
Пример: чтобы найти символ 's', надо идти по битовой структуре до соответствующего бита. Пока идем по структуре — считаем биты = 1 ( взведенные биты ). Допустим, мы насчитали 5 взведенных битов, а бит, соответствующий 's', оказался 6-ым взведенным битом. Соответственно, нам нужен 6-ой указатель в таблице данного узла. Если бит оказался невзведенным ( = 0 ), то данного символа нет.
Теперь перейдем к HAMT. Вместо алфавита используются старшие биты хэша. Вот как выглядит HAMT ( взято из [1] ):
HAMT состоит из главной хэш таблицы размером 2 ^ t, где обычно t >= 5. Каждый элемент главной таблицы:
1. либо корневой узел дерева подтаблиц с размером 32
2. либо просто пара ключ — значение
Выбор хэш-функции зависит от вашего набора данных. Желательно выбрать хэш-функцию, дающую минимальное количество коллизий ( подробнее про коллизии в [2] ).
1. Генерируем 32-битный хэш для ключа.
2. Из получившегося хэша берем t старших бит ( примечание: t старших бит берем только в первый раз, в остальные — по 5 бит ) и используем их как индекс в таблице. Тут возможно 3 варианта:
a) в ячейке с таким индексом ничего нет — такого ключа нет в таблице;
b) в ячейке есть одна пара ключ / значение. Если ключ совпал — нашли элемент, не совпал — не нашли;
c) в ячейке хранится 32-битный bitmap и таблица с указателями. В этом случае берем следующие 5 бит хэша и снова используем их как индекс в bitmap. Если бит не взведен, то такого ключа нет, если взведен — то считаем все взведенные биты с начала по текущий ( как и в AMT ). Таким образом мы получили номер необходимого указателя в таблице. Идем по указателю и повторяем алгоритм.
Часто необходимо всего несколько итераций этого алгоритма ( хотя это зависит от заполненности дерева ). Ключ сравнивается всего один раз — когда мы попали в ситуацию b. Отсутствие ключа детектируется тоже достаточно рано.
Повторяем шаги из алгоритам вставки, пока не произойдет одна из 3 ситуаций:
a) в ячейке с таким индексом ничего нет;
b) в ячейке хранится 32-битный bitmap и таблица с указателями;
В обоих случаях алгоритам простой: если вставка происходит в главную таблицу — то просто вставляем пару ключ / значение. Если же вставка происходит в подтаблицу, то взводим соответствующий бит, аллоцируем новую таблицу указателей, копируем в неё указатели из старой таблицы и новый указатель на нашу пару, а старую таблицу удаляем.
В итоге у нас взведен бит соответствующей ячейки, в таблице указателей все старые указатели, а также в соответствующей ячейке новый указатель.
c) произошла коллизия — т. е. у нас совпала какая-то часть двух хэшей. Решение простое — создаем новую подтаблицу, от уже существующего ключа вычисляем хэш и используем очередные 5 бит для нахождения нужной ячейки. Взводим бит в данной ячейке, вставляем в таблицу указателей указатель на существующую пару ключ / значение, возвращаемся к вставляемой паре, берем тоже очередные 5 бит и ищем нужную ячейку. Этот шаг с созданием новой подтаблицы повторяем до тех пор, пока коллизия не исчезнет.
С каждым таким шагом вероятность коллизии уменьшается в 32 раза ( размер таблицы указателей и bitmap ).
Иногда мы получаем полную коллизию — все 32 бита хэшей двух разных ключей совпадают. Тогда берем следующую хэш-функцию и хэшируем ей два конфликтующих ключа. В итоге когда будем искать по ключу элемент — мы пройдем по всем битам первичного хэша, увидим, что пришли не в лист, а в подтаблицу, и вычислим новый хэш ключа с помощью второй функции.
Вообще, это не единственный способ решения коллизий, в разных реализациях есть другие. Автор в своей работе предлагает использовать ту же хэш-функцию, просто после коллизии подавать ей на вход ключ и уровень дерева, в котором мы находимся в данный шаг алгоритма ( 0 — корневая таблица и т. д. ). Если же приложению критически важно, чтобы время операции вставки было ограничено сверху ( чисто теоретически мы можем взять два таких ключа, что их хэши будут совпадать после нескольких вызовов функции рехэширования, а значит, операция вставки будет длиться очень долго ), то вместо рехэширования совпадающих ключей можно использовать сами ключи.
Нам понадобяться пулы от 1 до 32 элементов ( для таблиц различного размера ). Выделяем блоки памяти и разбиваем на соответствующие таблицы. В процессе работы постепенно будет увеличиваться фрагментация. Для того, чтобы вернуть память, необходимо проводить дефрагментацию. Можно установить лимит на объем фрагментированной памяти в процентах, проверять его при вставке элемента и при превышении лимита — проводить дефрагментацию. Операцию дефрагментации можно реализовать как О(1) операцию.
В какой-то момент времени дерево вырастет настолько, что увеличение размера корневой таблицы даст ощутимый прирост в скорости. Каждая подтаблица имеет 32 элемента, поэтому наиболее логичным будет изменение с 2 ^ t до 2 ^ ( t + 5 ). При увеличении размера все подтаблицы первого уровня попадают в корневую таблицу. Причем рехэширование нужно только в случае, когда у нас в корневую таблицу попадают листы дерева ( нужно заново вычислять хэш чтобы определить новое положение элемента ). В остальных случаях просто копируем элементы из подтаблицы в корневую таблицу.
Возможно не сразу копировать все подтаблицы в корневую таблицу, а постепенно. При этом запоминается индекс переноса. Все элементы ниже индекса копируются в новую таблицу, а индекс постепенно продвигается по старой таблице. Во время поиска происходит сравнение первых t бит хэша с индексом переноса — если хэш больше, то поиск направляется в старую таблицу, иначе — в новую. Алгоритм вставки тоже должен учитывать индекс переноса.
Когда стоит проводить увеличение корневой таблицы? Когда размер новой таблицы будет занимать 1 / f от всего дерева. Параметр f надо подбирать исходя из конкретной ситуации.
Объем памяти зависит от индекса переноса. Автор в своей работе привел таблицу, показывающую эту зависимость ( взято из [1] )
Т. е. если индекс переноса = N / 4, где N — количество вставленных в дерево пар ключ-значение, то занимаемая память пропорциональна 1.28 * N.
Во время удаления могут возникнуть две ситуации:
a) удаляем элемент в подтаблице с количеством элементов больше 2. Тогда надо перенести все остальные элементы в меньшую по размеру подтаблицу, а текущую пометить пустой.
b) удаляем элемент в подтаблице с количеством элементов равным 2. В этой ситуации оставшийся элемент просто переносим в подтаблицу уровнем выше, а текущую помечаем пустой.
Я потерял ссылку на реализацию от автора на С(( Кто найдет — напишите в комментарии.
github.com/yasm/yasm/blob/master/libyasm/hamt.c — пример реализации на С. Ссылки на примеры реализации на других языках можно найти в [3].
[1] статья от автора алгоритма
[2] статья про коллизии хэшей на Википедии
[3] статья про HAMT на Википедии
[4] хороший вопрос на SO
[5] краткий вводный курс в HAMT
Замечания и неточности пишите в комментариях, орфографические ошибки и потерявшиеся знаки препинания присылайте в личку.
Про trie на хабре уже писали.
Структура array mapped trie
В trie достаточно часто хранят строки, поэтому есть понятие алфавита, из которого могут состоять элементы. Для оптимизации под x32 ограничивают размер алфавита до 32 ( 0 — 31 ).
Давайте посмотрим, как выглядит array mapped trie, оно же AMT ( взято из [1] ):
AMT состоит из узла и нескольких отрезков, соединяющих наш узел и другие узлы. Каждый отрезок представляет собой один из возможных символов алфавита.
В узле хранится 32-битная структура ( bitmap ), каждый бит структуры отражает состояние одного из 32 отрезков ( 0 — нет, 1 — есть ). Также в узле находится таблица, в которой хранятся указатели на поддеревья или последние символы в данной подстроке ( листья ). Указатели в таблице хранятся упорядоченно, и каждому из указателей соответствует бит = 1 в битовой структуре.
Пример: чтобы найти символ 's', надо идти по битовой структуре до соответствующего бита. Пока идем по структуре — считаем биты = 1 ( взведенные биты ). Допустим, мы насчитали 5 взведенных битов, а бит, соответствующий 's', оказался 6-ым взведенным битом. Соответственно, нам нужен 6-ой указатель в таблице данного узла. Если бит оказался невзведенным ( = 0 ), то данного символа нет.
Структура hash array mapped trie
Теперь перейдем к HAMT. Вместо алфавита используются старшие биты хэша. Вот как выглядит HAMT ( взято из [1] ):
HAMT состоит из главной хэш таблицы размером 2 ^ t, где обычно t >= 5. Каждый элемент главной таблицы:
1. либо корневой узел дерева подтаблиц с размером 32
Index Node:
int bitmap (32 bits)
Node*[] table (max length of 32)
2. либо просто пара ключ — значение
Key Value Node:
K key
V value
Выбор хэш-функции зависит от вашего набора данных. Желательно выбрать хэш-функцию, дающую минимальное количество коллизий ( подробнее про коллизии в [2] ).
Поиск элемента
1. Генерируем 32-битный хэш для ключа.
2. Из получившегося хэша берем t старших бит ( примечание: t старших бит берем только в первый раз, в остальные — по 5 бит ) и используем их как индекс в таблице. Тут возможно 3 варианта:
a) в ячейке с таким индексом ничего нет — такого ключа нет в таблице;
b) в ячейке есть одна пара ключ / значение. Если ключ совпал — нашли элемент, не совпал — не нашли;
c) в ячейке хранится 32-битный bitmap и таблица с указателями. В этом случае берем следующие 5 бит хэша и снова используем их как индекс в bitmap. Если бит не взведен, то такого ключа нет, если взведен — то считаем все взведенные биты с начала по текущий ( как и в AMT ). Таким образом мы получили номер необходимого указателя в таблице. Идем по указателю и повторяем алгоритм.
Часто необходимо всего несколько итераций этого алгоритма ( хотя это зависит от заполненности дерева ). Ключ сравнивается всего один раз — когда мы попали в ситуацию b. Отсутствие ключа детектируется тоже достаточно рано.
Вставка элемента
Повторяем шаги из алгоритам вставки, пока не произойдет одна из 3 ситуаций:
a) в ячейке с таким индексом ничего нет;
b) в ячейке хранится 32-битный bitmap и таблица с указателями;
В обоих случаях алгоритам простой: если вставка происходит в главную таблицу — то просто вставляем пару ключ / значение. Если же вставка происходит в подтаблицу, то взводим соответствующий бит, аллоцируем новую таблицу указателей, копируем в неё указатели из старой таблицы и новый указатель на нашу пару, а старую таблицу удаляем.
В итоге у нас взведен бит соответствующей ячейки, в таблице указателей все старые указатели, а также в соответствующей ячейке новый указатель.
c) произошла коллизия — т. е. у нас совпала какая-то часть двух хэшей. Решение простое — создаем новую подтаблицу, от уже существующего ключа вычисляем хэш и используем очередные 5 бит для нахождения нужной ячейки. Взводим бит в данной ячейке, вставляем в таблицу указателей указатель на существующую пару ключ / значение, возвращаемся к вставляемой паре, берем тоже очередные 5 бит и ищем нужную ячейку. Этот шаг с созданием новой подтаблицы повторяем до тех пор, пока коллизия не исчезнет.
С каждым таким шагом вероятность коллизии уменьшается в 32 раза ( размер таблицы указателей и bitmap ).
Иногда мы получаем полную коллизию — все 32 бита хэшей двух разных ключей совпадают. Тогда берем следующую хэш-функцию и хэшируем ей два конфликтующих ключа. В итоге когда будем искать по ключу элемент — мы пройдем по всем битам первичного хэша, увидим, что пришли не в лист, а в подтаблицу, и вычислим новый хэш ключа с помощью второй функции.
Вообще, это не единственный способ решения коллизий, в разных реализациях есть другие. Автор в своей работе предлагает использовать ту же хэш-функцию, просто после коллизии подавать ей на вход ключ и уровень дерева, в котором мы находимся в данный шаг алгоритма ( 0 — корневая таблица и т. д. ). Если же приложению критически важно, чтобы время операции вставки было ограничено сверху ( чисто теоретически мы можем взять два таких ключа, что их хэши будут совпадать после нескольких вызовов функции рехэширования, а значит, операция вставки будет длиться очень долго ), то вместо рехэширования совпадающих ключей можно использовать сами ключи.
Распределение памяти
Нам понадобяться пулы от 1 до 32 элементов ( для таблиц различного размера ). Выделяем блоки памяти и разбиваем на соответствующие таблицы. В процессе работы постепенно будет увеличиваться фрагментация. Для того, чтобы вернуть память, необходимо проводить дефрагментацию. Можно установить лимит на объем фрагментированной памяти в процентах, проверять его при вставке элемента и при превышении лимита — проводить дефрагментацию. Операцию дефрагментации можно реализовать как О(1) операцию.
Изменение размера корневой таблицы
В какой-то момент времени дерево вырастет настолько, что увеличение размера корневой таблицы даст ощутимый прирост в скорости. Каждая подтаблица имеет 32 элемента, поэтому наиболее логичным будет изменение с 2 ^ t до 2 ^ ( t + 5 ). При увеличении размера все подтаблицы первого уровня попадают в корневую таблицу. Причем рехэширование нужно только в случае, когда у нас в корневую таблицу попадают листы дерева ( нужно заново вычислять хэш чтобы определить новое положение элемента ). В остальных случаях просто копируем элементы из подтаблицы в корневую таблицу.
Возможно не сразу копировать все подтаблицы в корневую таблицу, а постепенно. При этом запоминается индекс переноса. Все элементы ниже индекса копируются в новую таблицу, а индекс постепенно продвигается по старой таблице. Во время поиска происходит сравнение первых t бит хэша с индексом переноса — если хэш больше, то поиск направляется в старую таблицу, иначе — в новую. Алгоритм вставки тоже должен учитывать индекс переноса.
Когда стоит проводить увеличение корневой таблицы? Когда размер новой таблицы будет занимать 1 / f от всего дерева. Параметр f надо подбирать исходя из конкретной ситуации.
Объем необходимой памяти
Объем памяти зависит от индекса переноса. Автор в своей работе привел таблицу, показывающую эту зависимость ( взято из [1] )
Т. е. если индекс переноса = N / 4, где N — количество вставленных в дерево пар ключ-значение, то занимаемая память пропорциональна 1.28 * N.
Удаление элемента
Во время удаления могут возникнуть две ситуации:
a) удаляем элемент в подтаблице с количеством элементов больше 2. Тогда надо перенести все остальные элементы в меньшую по размеру подтаблицу, а текущую пометить пустой.
b) удаляем элемент в подтаблице с количеством элементов равным 2. В этой ситуации оставшийся элемент просто переносим в подтаблицу уровнем выше, а текущую помечаем пустой.
Исходный код
Я потерял ссылку на реализацию от автора на С(( Кто найдет — напишите в комментарии.
github.com/yasm/yasm/blob/master/libyasm/hamt.c — пример реализации на С. Ссылки на примеры реализации на других языках можно найти в [3].
Ссылки
[1] статья от автора алгоритма
[2] статья про коллизии хэшей на Википедии
[3] статья про HAMT на Википедии
[4] хороший вопрос на SO
[5] краткий вводный курс в HAMT
Замечания и неточности пишите в комментариях, орфографические ошибки и потерявшиеся знаки препинания присылайте в личку.