Расширяемое хеширование

Расширяемое хеширование - это тип хеш- системы, которая обрабатывает хеш-код как битовую строку и использует дерево для поиска по корзине. ^[1] Из-за иерархической природы системы повторное хеширование является инкрементной операцией (при необходимости выполняется по одной корзине за раз). Это означает, что чувствительные ко времени приложения меньше подвержены влиянию роста таблицы, чем стандартное повторное хеширование всей таблицы.

Расширяемое хеширование было описано Рональдом Феджином в 1979 году. Практически все современные файловые системы используют расширяемое хеширование или B-деревья . В частности, глобальная файловая система , ZFS и файловая система SpadFS используют расширяемое хеширование. ^[2]

Пример [ править ]

Предположим, что хеш-функция возвращает строку битов. Первые i бит каждой строки будут использоваться в качестве индексов для определения их места в «каталоге» (хеш-таблице). Кроме того, i - это наименьшее число, так что индекс каждого элемента в таблице уникален. ${\ displaystyle h (k)}$

Ключи, которые будут использоваться:

{\ Displaystyle {\ begin {align} h (k_ ​​{1}) = 100100 \\ h (k_ ​​{2}) = 010110 \\ h (k_ ​​{3}) = 110110 \ end {align}}}

Предположим, что для этого конкретного примера размер корзины равен 1. Первые два ключа, которые нужно вставить, k ₁ и k ₂ , можно отличить по старшему значащему биту, и они будут вставлены в таблицу следующим образом:

Теперь, если бы k ₃ было хешировано в таблицу, было бы недостаточно различать все три ключа одним битом (потому что и k _3, и k ₁ имеют 1 в качестве крайнего левого бита). Кроме того, поскольку размер ведра равен единице, таблица будет переполняться. Поскольку сравнение первых двух наиболее значимых битов даст каждому ключу уникальное местоположение, размер каталога удваивается следующим образом:

Таким образом, теперь k ₁ и k ₃ имеют уникальное местоположение, отличающееся первыми двумя крайними левыми битами. Поскольку k ₂ находится в верхней половине таблицы, и 00, и 01 указывают на него, потому что нет другого ключа для сравнения с тем, который начинается с 0.

Приведенный выше пример взят из Fagin et al. (1979) .

Дополнительная информация [ править ]

{\ displaystyle h (k_ ​​{4}) = 011110}

Теперь необходимо вставить k ₄ , и первые два бита в нем равны 01 .. (1110), и, используя 2-битную глубину в каталоге, он преобразуется из 01 в сегмент A. Корзина A заполнена (максимальный размер 1 ), поэтому его нужно разбить; поскольку существует более одного указателя на Bucket A, нет необходимости увеличивать размер каталога.

Необходима информация о:

Размер ключа, который отображает каталог (глобальная глубина), и
Размер ключа, который ранее отображал ведро (локальная глубина)

Чтобы различать два случая действия:

Удвоение каталога при заполнении корзины
Создание новой корзины и перераспределение записей между старой и новой корзиной

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

Количество записей каталога равно 2 ^{глобальной глубине} , а начальное количество сегментов равно 2 ^{локальной глубине} .

Таким образом, если глобальная глубина = локальная глубина = 0, то 2 ⁰ = 1, то есть начальный каталог одного указателя на одну корзину.

Вернемся к двум случаям действия; если ведро заполнено:

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

Ключ 01 указывает на Bucket A, а локальная глубина 1 для Bucket A меньше, чем глобальная глубина 2 для каталога, что означает, что для ключей, хэшированных для Bucket A, используется только 1-битный префикс (т.е. 0), и для этого ведра должен быть свой содержимое разбивается с использованием ключей 1 + 1 = 2 бита длиной; в общем, для любой локальной глубины d, где d меньше, чем D, глобальная глубина, затем d должна быть увеличена после разделения корзины, а новое d используется как количество битов ключа каждой записи для перераспределения записей прежних ведро в новые ведра.

Сейчас же,

{\ displaystyle h (k_ ​​{4}) = 011110}

выполняется еще раз, с 2 битами 01 .., и теперь ключ 01 указывает на новую корзину, но в ней все еще есть ( и также начинается с 01). ${\ displaystyle k_ {2}}$ ${\ displaystyle h (k_ {2}) = 010110}$

Если бы был 000110 с ключом 00, не было бы проблем, потому что оставалось бы в новом сегменте A ', а сегмент D был бы пуст. ${\ displaystyle k_ {2}}$ ${\ displaystyle k_ {2}}$

(Это был бы наиболее вероятный случай, когда сегменты имеют размер больше 1, а новые разделенные сегменты вряд ли переполнились бы, если бы все записи не были снова перенесены в один сегмент. Но просто чтобы подчеркнуть роль информации о глубине, пример будет рассмотрен логически до конца.)

Таким образом, сегмент D необходимо разделить, но проверка его локальной глубины, равной 2, совпадает с глобальной глубиной, равной 2, поэтому каталог должен быть снова разделен, чтобы хранить ключи с достаточной детализацией, например 3 бита.

Ковш D необходимо разделить, так как он заполнен.
Поскольку локальная глубина D = глобальной глубине, каталог должен удвоиться, чтобы увеличить детализацию ключей.
Глобальная глубина увеличилась после разделения каталога до 3.
Новая запись повторно вводится с глобальной глубиной 3 бита и заканчивается в D, имеющем локальную глубину 2, которая теперь может быть увеличена до 3, а D может быть разделена на D 'и E. ${\ displaystyle k_ {4}}$
Содержимое разделенной корзины D, было изменено на 3 бита, и оно попадает в D. ${\ displaystyle k_ {2}}$
K4 повторяется, и он попадает в E, у которого есть запасной слот.

Теперь он находится в D и повторяется снова с 3 битами 011 .., и он указывает на сегмент D, который уже содержит so is full; Локальная глубина D равна 2, но теперь глобальная глубина равна 3 после удвоения каталога, поэтому теперь D можно разделить на D 'сегмента, а E, содержимое D, было повторено с новой глобальной битовой маской глубины 3 и заканчивается в D ', затем новая запись повторяется с битовой маской с использованием нового счетчика битов глобальной глубины, равного 3, и это дает 011, который теперь указывает на новую корзину E, которая пуста. Так происходит в Bucket E. ${\ displaystyle h (k_ {2}) = 010110}$ ${\ displaystyle h (k_ {4}) = 011110}$ ${\ displaystyle k_ {2}}$ ${\ displaystyle k_ {2}}$ ${\ displaystyle h (k_ {2})}$ ${\ displaystyle k_ {2}}$ ${\ displaystyle k_ {4}}$ ${\ displaystyle h (k_ {4})}$ ${\ displaystyle k_ {4}}$

Пример реализации [ править ]

Ниже приведен расширяемый алгоритм хеширования в Python , в котором устранены проблемы связывания блока диска и страницы памяти, кеширования и согласованности. Обратите внимание, что проблема возникает, если глубина превышает размер в битах целого числа, потому что в этом случае удвоение каталога или разделение корзины не позволит повторно хешировать записи в разные сегменты.

В коде используются младшие значащие биты , что делает более эффективным расширение таблицы, поскольку весь каталог может быть скопирован как один блок ( Ramakrishnan & Gehrke (2003) ).

Пример Python [ править ]

PAGE_SZ  =  10 Страница класса :  def  __init__ ( self )  ->  None :  self . m  =  []  сам . d  =  0 def  full ( self )  ->  bool :  return  len ( self . m )  > =  PAGE_SZ def  put ( self ,  k ,  v )  ->  None :  для  i ,  ( key ,  value )  in  enumerate ( self . m ):  if  key  ==  k :  del  self . m [ i ]  сломать  себя . м . добавить (( k ,  v )) Защита  получить ( сам ,  к ):  для  ключа ,  значения  в  себе . m :  если  ключ  ==  k :  возвращаемое  значениеclass  EH :  def  __init__ ( self )  ->  None :  self . gd  =  0  сам . pp  =  [ Страница ()] def  get_page ( self ,  k ):  h  =  hash ( k )  return  self . pp [ h  &  (( 1  <<  self . gd )  -  1 )] def  put ( self ,  k ,  v )  ->  None :  p  =  self . get_page ( k )  full  =  p . полный ()  стр . положите ( k ,  v ),  если  заполнено :  если  p . d  ==  себя . gd :  self . pp  * =  2  сам . gd  + =  1 p0  =  Страница ()  p1  =  Страница ()  p0 . d  =  p1 . d  =  p . d  +  1  бит  =  1  <<  p . d  для  k2 ,  v2  в  p . m :  h  =  hash ( k2 )  new_p  =  p1,  если  h  &  bit  else  p0  new_p . положите ( k2 , v2 ) для  i  в  диапазоне ( hash ( k )  &  ( bit  -  1 ),  len ( self . pp ),  bit ):  self . pp [ i ]  =  p1,  если  i  &  bit  else  p0 def  get ( self ,  k ):  вернуть  self . get_page ( k ) . получить ( к )if  __name__  ==  "__main__" :  eh  =  EH ()  N  =  10088  l  =  список ( диапазон ( N )) импортировать  случайный  случайный . shuffle ( l )  вместо  x  in  l :  а . положить ( x ,  x )  print ( l ) для  i  в  диапазоне ( N ):  print ( eh . get ( i ))

Заметки [ править ]

^ Fagin, R .; Nievergelt, J .; Pippenger, N .; Стронг, HR (сентябрь 1979 г.), «Расширяемое хеширование - метод быстрого доступа к динамическим файлам», транзакции ACM в системах баз данных , 4 (3): 315–344, doi : 10.1145 / 320083.320092 , S2CID 2723596
^ Mikuláš Patocka.«Дизайн и реализация файловой системы Spad» . Разделы «4.1.6 Расширяемое хеширование: ZFS и GFS» и «Таблица 4.1: Организация каталогов в файловых системах». 2006 г.

См. Также [ править ]

Ссылки [ править ]

Fagin, R .; Nievergelt, J .; Pippenger, N .; Стронг, HR (сентябрь 1979 г.), «Расширяемое хеширование - метод быстрого доступа к динамическим файлам», транзакции ACM в системах баз данных , 4 (3): 315–344, doi : 10.1145 / 320083.320092 , S2CID 2723596
Ramakrishnan, R .; Герке, Дж. (2003), Системы управления базами данных, 3-е издание: Глава 11, Индексирование на основе хэша, стр. 373–378
Зильбершатц, Ави; Корт, Генри; Сударшан, С., Концепции системы баз данных, Шестое издание: Глава 11.7, Динамическое хеширование

Внешние ссылки [ править ]

Эта статья включает материалы, являющиеся общественным достоянием из документа NIST : Блэк, Пол Э. «Расширяемое хеширование» . Словарь алгоритмов и структур данных .
Расширяемые хеширующие заметки в Университете штата Арканзас
Расширяемые примечания к хешированию
Слайды из книги System Concepts по расширяемому хешированию для динамических индексов на основе хеша

[1] Fagin, R .; Nievergelt, J .; Pippenger, N .; Стронг, HR (сентябрь 1979 г.), «Расширяемое хеширование - метод быстрого доступа к динамическим файлам», транзакции ACM в системах баз данных , 4 (3): 315–344, doi : 10.1145 / 320083.320092 , S2CID 2723596

[2] Mikuláš Patocka.«Дизайн и реализация файловой системы Spad» . Разделы «4.1.6 Расширяемое хеширование: ZFS и GFS» и «Таблица 4.1: Организация каталогов в файловых системах». 2006 г.

[1]