Введение
Линейный хэшинг (LH) — это динамическая структура данных, реализующая хэш-таблицу, которая расширяется или сжимается на один блок за раз. Он был изобретён Витольдом Литвином в 1980 году и проанализирован Бейзой Йейтс и Созой Поллман. Это первая из ряда схем, известных как динамическое хеширование, таких как линейный хэшинг Ларсона с частичными расширениями, линейный хэшинг с приоритетным разделением, линейный хэшинг с частичными расширениями и приоритетным разделением, или рекурсивный линейный хэшинг. Файловая структура динамической структуры данных хеширования адаптируется к изменениям размера файла, что позволяет избежать дорогостоящей периодической реорганизации файла. Сам LH* был расширен для обеспечения доступности данных в случае отказа блоков. Операции, основанные на ключе (вставка, удаление, обновление, чтение) в LH и LH* занимают максимальное постоянное время, не зависящее от количества блоков и, следовательно, записей.
Хэш-функции
Хаширующая функция возвращает индекс, начиная с 0, корзины, содержащей запись с заданным ключом. Когда корзина, использующая хаширующую функцию, разделяется на две новые корзины, эта хаширующая функция заменяется на для обеих новых корзин. В любой момент времени используется не более двух хаширующих функций, причем одна из них соответствует текущему уровню. Семейство хаширующих функций также называют динамической хаширующей функцией. Как правило, значение в соответствует количеству младших двоичных разрядов ключа , используемых для разделения корзин. Эту динамическую хаширующую функцию можно выразить арифметически как: Обратите внимание, что когда общее количество корзин равно одному, выполните следующие вычисления, чтобы определить правильную хаширующую функцию для заданного ключа. Неконтролируемое разделение происходит, когда разделение выполняется каждый раз, когда корзина переполняется, в этом случае эта корзина разделяется на две отдельные корзины. Сжатие файла происходит в некоторых реализациях алгоритма LH, если контролируемое разделение приводит к тому, что коэффициент загрузки опускается ниже порогового значения. В этом случае запускается операция слияния, которая отменяет последнее разделение и восстанавливает состояние файла.
Complete the calculations below to determine the correct hashing function for the given hashing key
An uncontrolled split occurs when a split is performed whenever a bucket overflows, in which case that bucket would be split into two separate buckets. File contraction occurs in some LH algorithm implementations if a controlled split causes the load factor to sink below a threshold. In this case, a merge operation would be triggered which would undo the last split, and reset the file state.
Расчет состояния файла
Состояние файла состоит из указателя разбиения и уровня. Если исходный файл начинался с корзин, то количество корзин и состояние файла связаны соотношением. В работе обсуждалось применение линейного хэширования в языке Icon. Авторы рассмотрели альтернативные варианты реализации алгоритма динамического массива, используемого в линейном хэшировании, и представили сравнение производительности на основе списка эталонных приложений Icon.
discussed the adoption of linear hashing in the Icon language. They discussed the implementation alternatives of dynamic array algorithm used in linear hashing, and presented performance comparisons using a list of Icon benchmark applications.
Принятие в системах баз данных
Линейное хеширование используется в системе баз данных Berkeley (BDB), которая, в свою очередь, применяется во многих программных системах. Реализация на языке C была основана на статье из CACM и впервые опубликована Эсмондом Питтом в Usenet в 1988 году.