Спиральное хеширование — вид хеширования, предложенный Мартином (Martin, G. N. N., Spiral storage: Incrementally Augmentable Hash Addressed Storage). В этой технике элементы распределяются по корзинам неравномерно, так, что элементы преимущественно располагаются в одном из концов «корзинного» пространства. Когда коэффициент загруженности (отношение количества числа элементов к числу корзин) превысит пороговое значение, первая корзина, вероятно, наиболее плотная, разбивается на g корзин, где g — коэффициент роста.
Изначально существует g-1 корзин, пронумерованных от 1 до g-1. Отметим, что адресное пространство корзин выглядит так: {1, 2, …, g — 1} = {g0, …, g1 — 1}. При превышении порогового значения первая корзина разбивается на g новых корзин, становящихся корзинами от g до 2g-1. Элементы первой корзины распределяются по новым корзинам с использованием новой хеш-функции (хеш-функция параметризована). Первой корзины теперь не существует, существуют только {2, 3, … 2g-1} = {gc, …, gc+1-1}, где c=logg2.
В общем случае на k-ой стадии (т.е. после k-1 разбиения) выбирается корзина k и разбивается на g новых корзин, получающих номера kg … g(k+1)-1. Её элементы распределяются между новыми корзинами с помощью новой хеш-функции. После k разбиений первых k корзин получим {gc, …, gc+1-1}, где c=logg(k+1) и число корзин всегда делится на g-1.
Опишем теперь хеш-функцию H(K, k), обеспечивающую неравномерное распределение. Заметьте, что хеш-функция зависит не только от ключа K, но ещё и параметризована количеством проведённых разбиений k. Вспомним, что после k разбиений наше адресное пространство имеет вид {gc, …, gc+1-1}, где c=logg(k+1). У нас имеется gc(g-1) корзин от gc до gc+1-1. Получив ключ K мы для начала сопоставим ему x из [0, 1). Это можно сделать, используя, например, функцию распределения пар ключ-значение (G. D. Knott — Hashing functions, The Computer Journal Volume 18 Number 3). Затем мы сопоставляем x число x' из [c, c+1), распределённое равномерно. Один из вариантов такого сопоставления был предложен Мартином. Значение H(K, k) определяется как [gx'] (округление с отбрасыванием дробной части). Такая хеш функция обладает тем свойством, что H(K, k+1) = H(K, k) для всех корзин gc, gc + 1, …, gc+1, существующих на стадии k, кроме корзины gc = k+1, которой больше нет на стадии k+1. Заметьте, что P(H(K, k) = i) — логарифмически убывающая функция logg(i+1)-loggi для gc ≤ i ≤ gc+1, откуда и берётся название спиральное хеширование.
Если использовать открытую адресацию, некоторые элементы будут храниться в чужих корзинах. Поэтому при разбиении корзины нам нужно будет просмотреть и другие, чтобы найти элементы этой корзины. Но нам не хотелось бы затрагивать слишком много корзин при разбиении, поэтому лучше не использовать метод открытой адресации для борьбы с коллизиями. Мы предпочитаем метод цепочек.
Средний
Простой
Простой
Простой
