HAT -trie — это тип radix trie , который использует узлы массива для сбора отдельных пар ключ-значение под узлами radix и хэш-корзинами в ассоциативный массив . В отличие от простой хэш-таблицы , HAT-trie хранят ключ-значение в упорядоченной коллекции. Первоначальными изобретателями являются Николас Аскитис и Ранджан Синха. [1] [2] Аскитис и Зобель показали, что построение и доступ к коллекции ключей/значений HAT-trie значительно быстрее, чем другие методы сортированного доступа, и сопоставимы с хэш-массивом, который является несортированной коллекцией. [3] Это связано с дружественной к кэшу природой структуры данных, которая пытается сгруппировать доступ к данным во времени и пространстве в 64-байтовый размер строки кэша современного ЦП.
Новое HAT-дерево начинается как указатель NULL, представляющий пустой узел. Первый добавленный ключ выделяет наименьший узел массива и копирует в него пару ключ/значение, которая становится первым корнем дерева. Каждая последующая пара ключ/значение добавляется к начальному узлу массива до тех пор, пока не будет достигнут максимальный размер, после чего узел разрывается путем перераспределения его ключей в хэш-контейнер с новыми базовыми узлами массива, по одному на каждый занятый слот хэша в дереве. Хэш-контейнер становится новым корнем дерева. Ключевые строки хранятся в узлах массива с байтом кодирования длины, предваряющим байты значения ключа. Значение, связанное с каждым ключом, может храниться либо в строке, чередуясь с ключевыми строками, либо помещаться во второй массив, например, в память сразу после и присоединяться к узлу массива. [4]
После того, как trie вырос до своего первого узла хэш-контейнера, хэш-контейнер распределяет новые ключи в соответствии с хэш-функцией значения ключа в узлы массива, содержащиеся под узлом контейнера. Ключи продолжают добавляться до тех пор, пока не будет достигнуто максимальное количество ключей для конкретного узла хэш-контейнера. Затем содержимое контейнера перераспределяется в новый узел radix в соответствии с первым символом сохраненного значения ключа, который заменяет узел хэш-контейнера в качестве корня trie [5] (например, см. Burstsort [6] ). Существующие ключи и значения, содержащиеся в хэш-контейнере, укорачиваются на один символ и помещаются под новый узел radix в набор новых узлов массива.
Сортированный доступ к коллекции обеспечивается путем перечисления ключей в курсоре путем ветвления вниз по radix trie для сборки ведущих символов, заканчивающихся либо на хэш-контейнере, либо на узле массива. Указатели на ключи, содержащиеся в хэш-контейнере или узле массива, собираются в массив, который является частью курсора для сортировки. Поскольку в хэш-контейнере или узле массива существует максимальное количество ключей, существует предустановленный фиксированный предел размера курсора во все моменты времени. После того, как ключи для хэш-контейнера или узла массива исчерпаны get-next (или get-previous) (см. Iterator ), курсор перемещается в следующую запись radix-узла, и процесс повторяется. [7]