Линейное хеширование - Linear hashing

Линейное хеширование (LH) - это динамическая структура данных, реализующая хеш-таблица и увеличивается или уменьшается по одному ведру за раз. Его изобрел Витольд Литвин в 1980 году.^[1]^[2] Его проанализировали Баеза-Йейтс и Соза-Поллман.^[3] Это первая из ряда схем, известных как динамическое хеширование.^[3]^[4] например, линейное хеширование Ларсона с частичными расширениями, ^[5]Линейное хеширование с разделением приоритетов,^[6]Линейное хеширование с частичным расширением и разделением приоритета,^[7]или рекурсивное линейное хеширование.^[8]

Файловая структура структуры данных динамического хеширования адаптируется к изменениям размера файла, что позволяет избежать дорогостоящей периодической реорганизации файла.^[4] Файл линейного хеширования расширяется за счет разделения заранее определенного сегмента на две и сжимается путем объединения двух заранее определенных сегментов в одну. Запуск реконструкции зависит от изюминки схемы; это может быть переполнение ковша или коэффициент загрузки (количество записей по количеству ковшей), выходящий за пределы заранее определенного диапазона.^[1]

Линейное хеширование также превратилось в масштабируемую распределенную структуру данных, LH *. В LH * каждая корзина находится на отдельном сервере.^[9] Сам LH * был расширен, чтобы обеспечить доступность данных при наличии неработающих сегментов.^[10] Операции на основе ключей (вставка, удаление, обновление, чтение) в LH и LH * занимают максимальное постоянное время независимо от количества сегментов и, следовательно, записей.^[1]^[10]

Детали алгоритма

Записи в LH или LH * состоят из ключа и содержимого, последнее в основном всех остальных атрибутов записи.^[1]^[10] Они хранятся в ведрах. Например, в реализации Эллиса ведро - это связанный список записей.^[2] Этот файл позволяет операциям CRUD на основе ключей создавать или вставлять, читать, обновлять и удалять, а также операции сканирования, которые сканируют все записи, например, для выполнения операции выбора базы данных для неключевого атрибута.^[10] Записи хранятся в сегментах, нумерация которых начинается с 0.^[10]

Хеш-функции

Чтобы получить доступ к записи с ключом ${ displaystyle c}$ , к ключу применяется семейство хэш-функций, коллективно называемых динамической хеш-функцией. ${ displaystyle c}$ . В любой момент не более двух хэш-функций ${ displaystyle h_ {i}}$ и ${ displaystyle h_ {я + 1}}$ используются. Типичный пример использует операцию деления по модулю x. Если исходное количество ведер ${ displaystyle N}$ , то семейство хеш-функций ^[10]

${ Displaystyle ч_ {я} (с) mapsto с { pmod {N cdot 2 ^ {я}}}}$

Расширение файла

По мере того, как файл увеличивается за счет вставок, он плавно расширяется за счет разделения одной корзины на две. Последовательность сегментов для разделения предопределена - это фундаментальное отличие от таких схем, как расширяемое хеширование Феджина.^[11]Для двух новых сегментов хэш-функция ${ displaystyle h_ {i}}$ заменяется на ${ displaystyle h_ {я + 1}}$ . Номер сегмента, который нужно разделить, является частью состояния файла и называется указателем разделения. ${ displaystyle s}$ .^[10]

Разделить контроль

Разделение может выполняться всякий раз, когда ведро переполняется. Это неконтролируемое разделение. В качестве альтернативы файл может отслеживать коэффициент загрузки и выполнять разделение, когда коэффициент загрузки превышает пороговое значение. Это было контролируемое расщепление.^[10]

Обращение

Адресация основана на состоянии файла, состоящем из указателя разделения ${ displaystyle s}$ и уровень ${ displaystyle l}$ . Если уровень ${ displaystyle l}$ , то используемые хэш-функции ${ displaystyle h_ {l}}$ и ${ displaystyle h_ {l + 1}}$ .

Алгоритм LH для ключа хеширования ${ displaystyle c}$ является^[10]

${ displaystyle a: = h_ {l} (c)}$

если ${ displaystyle a$

Расщепление

Когда ведро разделено, указатель разделения и, возможно, уровень обновляются в соответствии с^[10]

${ displaystyle s: = s + 1}$

если ${ Displaystyle s geq N раз 2 ^ {l}}$ : ${ displaystyle l + = 1, s = 0}$

Сжатие файла

Если при контролируемом разделении коэффициент нагрузки опускается ниже порогового значения, запускается операция объединения. Операция слияния отменяет последнее разбиение, а также сбрасывает состояние файла.^[10]

Расчет состояния файла

Состояние файла состоит из указателя разделения ${ displaystyle s}$ и уровень ${ displaystyle l}$ . Если исходный файл начинается с ${ Displaystyle N = 1}$ ведра, затем количество ведер ${ displaystyle n}$ и состояние файла связаны через^[12]

${ Displaystyle п = 2 ^ {l} + s}$

LH *

Основной вклад LH * состоит в том, чтобы позволить клиенту файла LH * найти бакет, в котором находится запись, даже если клиенту неизвестно состояние файла. Фактически клиенты хранят свою версию состояния файла, которая изначально представляет собой только информацию о первом сегменте, а именно сегменте 0. На основе состояния своего файла клиент вычисляет адрес ключа и отправляет запрос в этот сегмент. В сегменте запрос проверяется и, если записи нет в сегменте, он пересылается. В достаточно стабильной системе, то есть если во время обработки запроса происходит только одно разделение или слияние, можно показать, что есть не более двух пересылок. После пересылки последний сегмент отправляет сообщение настройки изображения клиенту, состояние которого теперь ближе к состоянию распределенного файла.^[10] Хотя для активных клиентов переадресация встречается довольно редко, их количество можно еще больше сократить за счет обмена дополнительной информацией между серверами и клиентами. ^[12]

Принятие в языковых системах

Грисволд и Таунсенд ^[13] обсудили принятие линейного хеширования в Язык значков. Они обсудили альтернативы реализации динамический массив алгоритм, используемый в линейном хешировании, и представлены сравнения производительности с использованием списка тестовых приложений Icon.

Принятие в системах баз данных

Линейное хеширование используется в Система баз данных Беркли (BDB), который, в свою очередь, используется многими программными системами, такими как OpenLDAP, с использованием реализации C, взятой из статьи CACM и впервые опубликованной в Usenet в 1988 году Эсмондом Питтом.

внешняя ссылка

Смотрите также

[WL80-1] а ^б ^c ^d Литвин, Витольд (1980), «Линейное хеширование: новый инструмент для адресации файлов и таблиц» (PDF), Proc. 6-я конференция по очень большим базам данных: 212–223

[Ellis-2] а ^б Эллис, Карла Шлаттер (июнь 1987 г.), «Параллелизм в линейном хешировании», Транзакции ACM в системах баз данных, 12 (2): 195–217

[BS-3] а ^б Баеза-Йейтс, Рикардо; Соза-Поллман, Гектор (1998), "Анализ линейного хеширования пересмотрен" (PDF), Северный вычислительный журнал: 70–85

[RD-4] а ^б Энбоди, Ричард; Du, HC (июнь 1988 г.), «Схемы динамического хеширования», Опросы ACM Computing, 20 (2): 85–113

[AL-5] Ларсон, Пер-Оке (апрель 1988 г.), «Динамические хеш-таблицы», Коммуникации ACM, 31 (4): 446–457, Дои:10.1145/42404.42410

[ruchte-6] Рухте, Уиллард; Тарп, Алан (февраль 1987 г.), «Линейное хеширование с разделением приоритетов: метод повышения эффективности поиска при линейном хешировании», Третья международная конференция IEEE по инженерии данных: 2–9

[7] Манолопулос, Яннис; Лоренцос, Н. (1994), "Производительность схем линейного хеширования для получения первичного ключа", Информационные системы, 19 (5): 433–446

[RS-8] Ramamohanarao, K .; Сакс-Дэвис, Р. (сентябрь 1984 г.), «Рекурсивное линейное хеширование», ACM-транзакции в базах данных, 9 (3): 369–391

[WL93-9] Литвин, Витольд; Неймат, Мари-Анн; Шнайдер, Донаван А. (1993), «Линейное хеширование для распределенных файлов», Труды Международной конференции по управлению данными SIGMOD 93: 327–336

[LMS-10] а ^б ^c ^d ^е ^ж ^грамм ^час ^я ^j ^k ^л Литвин, Витольд; Мусса, Рим; Шварц, Томас (сентябрь 2005 г.), «LH * RS - высокодоступная масштабируемая распределенная структура данных», Транзакции ACM в системах баз данных, 30 (3): 769–811

[Fagin-11] Феджин, Рональд; Нивергельт, Юрг; Пиппенгер, Николас; Стронг, Раймонд (сентябрь 1979 г.), «Расширяемое хеширование - метод быстрого доступа к динамическим файлам», Транзакции ACM в системах баз данных, 4 (2): 315–344

[CS-12] а ^б Чабкинян, Хуан; Шварц, Томас (2016), «Fast LH *», Международный журнал параллельного программирования, 44 (4): 709–734

[13] Грисволд, Уильям Г.; Таунсенд, Грегг М. (апрель 1993 г.), «Разработка и реализация динамического хеширования для наборов и таблиц в иконке», Программное обеспечение - практика и опыт, 23 (4): 351–367

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]