HAT-трие

HAT -три — это тип поразрядного дерева , который использует узлы массива для сбора отдельных пар ключ-значение под узлами по счислению и хэш-группами в ассоциативный массив . В отличие от простой хеш-таблицы , HAT-пытается сохранить ключ-значение в упорядоченной коллекции. Первоначальными изобретателями являются Николас Аскитис и Ранджан Синха. ^[1]^[2] Аскитис и Зобель показали, что создание и доступ к коллекции ключей/значений HAT-trie происходит значительно быстрее, чем другие методы отсортированного доступа, и сравнимо с хэшем массива, который представляет собой несортированную коллекцию. ^[3] Это связано с дружественным к кэшу характером структуры данных, которая пытается сгруппировать доступ к данным во времени и пространстве в 64-байтовую строку кэша современного ЦП.

Описание

Новая HAT-трие начинается как NULL-указатель, представляющий пустой узел. Первый добавленный ключ выделяет наименьший узел массива и копирует в него пару ключ/значение, которая становится первым корнем дерева. Каждая последующая пара ключ/значение добавляется к исходному узлу массива до тех пор, пока не будет достигнут максимальный размер, после чего узел разбивается путем перераспределения его ключей в хеш-корзину с новыми базовыми узлами массива, по одному на каждый занятый хэш-слот в ведро. Хеш-корзина становится новым корнем дерева. Строки ключей хранятся в узлах массива с префиксом байта кодирования длины перед байтами значения ключа. Значение, связанное с каждым ключом, может быть сохранено либо в строке, чередуясь со строками ключей, либо помещено во второй массив, например, в память сразу после узла массива и присоединено к нему. ^[4]

Как только дерево превратилось в свой первый узел хеш-корзины, хеш-корзина распределяет новые ключи в соответствии с хеш-функцией значения ключа по узлам массива, содержащимся под узлом корзины. Ключи продолжают добавляться до тех пор, пока не будет достигнуто максимальное количество ключей для конкретного узла хеш-корзины. Содержимое сегмента затем перераспределяется в новый узел системы счисления в соответствии с первым символом сохраненного значения ключа, который заменяет узел хеш-корзины в качестве корня дерева. ^[5] (например, см. пакетную сортировку ^[6]). Существующие ключи и значения, содержащиеся в хеш-корзине, сокращаются на один символ и помещаются под новым узлом системы счисления в наборе новых узлов массива.

Сортированный доступ к коллекции обеспечивается путем перечисления ключей в курсор путем разветвления дерева системы счисления для сборки начальных символов, заканчивающегося либо хэш-ведром, либо узлом массива. Указатели на ключи, содержащиеся в хеш-корзине или узле массива, собираются в массив, который является частью курсора для сортировки. Поскольку в хэш-ведре или узле массива существует максимальное количество ключей, существует заранее установленный фиксированный предел размера курсора в любой момент времени. После того, как ключи для хеш-корзины или узла массива исчерпаны с помощью get-next (или get-previous) (см. Итератор ), курсор перемещается в следующую запись узла счисления, и процесс повторяется. ^[7]

Ссылки

^ описано в статье, опубликованной в Proc. Тридцатая Австралазийская конференция по информатике (ACSC2007), Балларат, Австралия. CRPIT, 62. Добби, Г., Ред. САУ. 97-105
^ https://dl.acm.org/citation.cfm?id=1273761 HAT-trie: структура данных на основе Trie с поддержкой кэша для строк.
^ Аскитис, Н. и Зобель, Дж. (2005), Разрешение конфликтов с учетом кэша для строковых хеш-таблиц, в «Proc. Симпозиум по обработке строк и поиску информации SPIRE», Springer-Verlag, стр. 92–104.
^ Аскитис, Н. и Зобель, Дж. 2011. Перепроектирование хеш-таблицы строк, пакетной попытки и BST для использования кеша. ACM J. Exp. Алгор. 15, 1, статья 1.7 (январь 2011 г.)
^ Пакетные попытки: быстрая и эффективная структура данных для строковых ключей ACM Trans. Инф. Сист., Том. 20, № 2. (апрель 2002 г.), стр. 192–223, doi: 10.1145/506309.506312, авторы: Штеффен Хайнц, Джастин Зобель, Хью Э. Уильямс.
^ Синха, Р. и Вирт, А. 2010. Инженерная пакетная сортировка: на пути к быстрой сортировке строк на месте. ACM J. Exp. Алгор. 15, статья 2.5 (март 2010 г.)
^ http://www.siam.org/meetings/alenex03/Abstracts/rsinha.pdf Сортировка больших наборов строк с учетом кэша с динамическими попытками

Внешние ссылки

[1] описано в статье, опубликованной в Proc. Тридцатая Австралазийская конференция по информатике (ACSC2007), Балларат, Австралия. CRPIT, 62. Добби, Г., Ред. САУ. 97-105

[2] ttps://dl.acm.org/citation.cfm?id=1273761 HAT-trie: структура данных на основе Trie с поддержкой кэша для строк.

[3] Аскитис, Н. и Зобель, Дж. (2005), Разрешение конфликтов с учетом кэша для строковых хеш-таблиц, в «Proc. Симпозиум по обработке строк и поиску информации SPIRE», Springer-Verlag, стр. 92–104.

[4] Аскитис, Н. и Зобель, Дж. 2011. Перепроектирование хеш-таблицы строк, пакетной попытки и BST для использования кеша. ACM J. Exp. Алгор. 15, 1, статья 1.7 (январь 2011 г.)

[5] Пакетные попытки: быстрая и эффективная структура данных для строковых ключей ACM Trans. Инф. Сист., Том. 20, № 2. (апрель 2002 г.), стр. 192–223, doi: 10.1145/506309.506312, авторы: Штеффен Хайнц, Джастин Зобель, Хью Э. Уильямс.

[6] Синха, Р. и Вирт, А. 2010. Инженерная пакетная сортировка: на пути к быстрой сортировке строк на месте. ACM J. Exp. Алгор. 15, статья 2.5 (март 2010 г.)

[7] ttp://www.siam.org/meetings/alenex03/Abstracts/rsinha.pdf Сортировка больших наборов строк с учетом кэша с динамическими попытками

[1]

[2]

[3]

[4]

[5]

[6]

[7]