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

Расширяемое хеширование — это метод организации хеш-таблиц, предназначенный для работы с данными, хранящимися на внешних носителях (например, на жёстких дисках), который позволяет динамически изменять размер таблицы без значительного снижения производительности. В отличие от статических хеш-таблиц, где размер фиксирован, расширяемое хеширование адаптируется к росту или уменьшению объёма данных, минимизируя количество операций ввода-вывода и перестроений структуры. Метод был предложен в 1979 году Рональдом Фэгином, Джеффри Ульманом и Дэвидом Майером.

История

Развитие баз данных и систем управления файлами в 1970-х годах выявило проблему эффективного доступа к данным на медленных носителях (магнитные диски). Традиционные хеш-таблицы требовали перехеширования всех записей при изменении размера, что было дорогостоящим. Расширяемое хеширование было разработано как решение, позволяющее выполнять операции вставки, удаления и поиска с постоянным ожидаемым временем (O(1)) при условии сбалансированного хеширования, но с возможностью плавного расширения. Первая реализация была описана в статье «Extendible Hashing: A Fast Access Method for Dynamic Files» (1979).

Принцип работы

Расширяемое хеширование основано на использовании хеш-функции, которая преобразует ключ записи в битовую строку фиксированной длины (например, 32 бита). Для адресации используется только часть этих битов — глобальная глубина (global depth). Структура состоит из двух основных компонентов:

1. Каталог (directory) — массив указателей на страницы (блоки) данных. Размер каталога равен 2^g, где g — глобальная глубина.
2. Страницы (buckets) — блоки фиксированного размера, хранящие записи. Каждая страница имеет свою локальную глубину (local depth), которая может быть меньше или равна глобальной.

Поиск

Для поиска записи по ключу:

1. Вычисляется хеш-значение ключа.
2. Берётся последние g бит хеша (или первые — зависит от реализации).
3. Полученное число используется как индекс в каталоге.
4. По указателю из каталога находится страница, в которой выполняется линейный поиск записи.

Вставка

При вставке новой записи возможны два сценария:

• Страница не заполнена: запись добавляется в соответствующую страницу.
• Страница заполнена: происходит расщепление страницы (split):

1. Если локальная глубина страницы меньше глобальной, создаётся новая страница, и записи из переполненной страницы перераспределяются между двумя страницами на основе одного дополнительного бита хеша (глубина увеличивается на 1). Каталог не меняется, но его указатели корректируются.
2. Если локальная глубина равна глобальной, то сначала удваивается каталог (его размер становится 2^(g+1)), а затем выполняется расщепление страницы. Удвоение каталога — операция, требующая выделения памяти и копирования указателей, но она происходит редко.

Удаление

При удалении записи, если страница становится пустой, может быть выполнено слияние (merge) с соседней страницей (если они имеют одинаковую локальную глубину и могут быть объединены). Если после слияния количество страниц уменьшается, каталог может быть уменьшен (сжатие), но это происходит реже, чем расширение.

Классификация и варианты

Расширяемое хеширование существует в нескольких модификациях, адаптированных под разные сценарии:

• Классическое (по Фэгину): использует каталог переменного размера, который удваивается при переполнении.
• Линейное хеширование: альтернативный метод, предложенный Уитни Литвином (1980), который не требует отдельного каталога, а расширяет таблицу постепенно, добавляя одну страницу за раз.
• Сплавное хеширование (spiral hashing): вариант, где хеш-функция генерирует последовательность адресов, что позволяет избежать резкого удвоения каталога.
• Виртуальное хеширование: использует виртуальную память для имитации каталога, что упрощает управление.

Характеристики и производительность

Основные параметры, влияющие на производительность:

• Размер страницы: обычно от 1 до 8 килобайт. Слишком маленькие страницы приводят к частым расщеплениям, слишком большие — к неэффективному использованию памяти.
• Глобальная глубина: определяет размер каталога. Чем больше глубина, тем больше каталог, но меньше вероятность коллизий.
• Локальная глубина: показывает, сколько бит хеша используется для адресации внутри конкретной страницы.

Достоинства:

• Постоянное время поиска в среднем (O(1)).
• Динамическое расширение без полного перестроения.
• Высокая эффективность при работе с внешней памятью (минимум операций ввода-вывода).
• Простота реализации.

Недостатки:

• Неравномерное распределение записей может привести к большому размеру каталога (до 2^32, что неприемлемо для 32-битных систем).
• Удвоение каталога — дорогостоящая операция, особенно при большом количестве страниц.
• Не подходит для данных с неравномерным хешированием (например, короткие строки с низкой энтропией).
• Требуется предварительное знание максимального размера хеш-функции.

Применение

Расширяемое хеширование широко используется в системах управления базами данных (СУБД) и файловых системах, где требуется быстрый доступ к данным на диске:

• Реляционные СУБД: PostgreSQL (в реализации индексов GiST и GIN), Oracle (в некоторых версиях для хеш-индексов).
• NoSQL-системы: MongoDB (для шардирования и хеш-индексов), Redis (в качестве внутренней структуры для хеш-таблиц).
• Файловые системы: ZFS (для организации каталогов), ext4 (в некоторых реализациях).
• Поисковые системы: для индексации документов и быстрого поиска по ключевым словам.
• Кэширующие системы: Memcached, Varnish (для хранения объектов в памяти).

Пример реализации

Рассмотрим простую реализацию на языке C (псевдокод): ```c

define BUCKET_SIZE 4 // Максимальное количество записей в странице

typedef struct { int keys[BUCKET_SIZE]; int values[BUCKET_SIZE]; int count; int local_depth; } Bucket;

typedef struct { Bucket **directory; int global_depth; } ExtendibleHash;

int hash(int key) { return key; // Простая хеш-функция }

void insert(ExtendibleHash ht, int key, int value) { int h = hash(key); int index = h & ((1 << ht->global_depth) - 1); // Берём последние g бит Bucket bucket = ht->directory[index];

if (bucket->count < BUCKET_SIZE) { bucket->keys[bucket->count] = key; bucket->values[bucket->count] = value; bucket->count++; } else { // Расщепление split_bucket(ht, index); // Повторная вставка insert(ht, key, value); } } ```

Критика и ограничения

Основная критика расширяемого хеширования связана с его чувствительностью к качеству хеш-функции. Если хеш-функция генерирует неравномерное распределение, каталог может разрастись до огромных размеров, а производительность упасть. Кроме того, метод не гарантирует постоянного времени вставки в худшем случае (при частых удвоениях каталога). В современных системах часто предпочитают линейное хеширование или B-деревья, которые менее чувствительны к распределению данных.

Интересные факты

• Расширяемое хеширование стало основой для многих алгоритмов в области распределённых систем, например, Consistent Hashing (согласованное хеширование), используемого в CDN и NoSQL-базах данных.
• В 1980-х годах метод активно применялся в системах управления базами данных для мэйнфреймов, таких как IMS от IBM.
• В некоторых реализациях каталог хранится не в памяти, а на диске, что позволяет обрабатывать таблицы с миллиардами записей.

Источники

• Fagin, R., Nievergelt, J., Pippenger, N., & Strong, H. R. (1979). Extendible hashing: A fast access method for dynamic files. ACM Transactions on Database Systems.
• Litwin, W. (1980). Linear hashing: A new tool for file and table addressing. Proceedings of the 6th International Conference on Very Large Data Bases.
• Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley.
• Garcia-Molina, H., Ullman, J. D., & Widom, J. (2009). Database Systems: The Complete Book (2nd ed.). Pearson.