Объединенное хеширование - Coalesced hashing

Пример объединенного хеширования. В этом примере сегменты коллизий выделяются в порядке возрастания, начиная с сегмента 0.

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

Отдельная хеш-таблица цепочки

В отдельной хеш-таблице с цепочкой элементы, хеширующие один и тот же адрес, помещаются в список (или «цепочку») по этому адресу. Этот метод может привести к значительному расходу памяти, потому что сама таблица должна быть достаточно большой, чтобы поддерживать хорошо работающий коэффициент нагрузки (обычно в два раза больше ожидаемого количества элементов), а дополнительная память должна использоваться для всех, кроме первого элемента в таблице. цепочка (если не используются заголовки списка, в этом случае для всех элементов в цепочке должна использоваться дополнительная память).

пример

Дана последовательность «qrj», «aty», «qur», «dim,» «ofu», «gcl,» «rhv,» «clq,» «ecd», «qsu» из случайно сгенерированных трехсимвольных строк, будет создана следующая таблица (с использованием Одноразовый хэш-алгоритм Боба Дженкинса ) со столом размера 10:

(ноль)
"clq"
"qur"
(ноль)
(ноль)
"тусклый"
"аты"	"qsu"
"rhv"
"qrj"	"офу"	"gcl"	"ecd"
(ноль)

Эта стратегия эффективна, действенна и очень проста в реализации. Однако иногда использование дополнительной памяти может быть недопустимым, и наиболее распространенная альтернатива, открытая адресация, имеет неудобные недостатки, снижающие производительность. Основным недостатком открытой адресации является первичная и вторичная кластеризация, при которой поиск может осуществлять доступ к длинным последовательностям используемых блоков, которые содержат элементы с разными хэш-адресами; Таким образом, элементы с одним хеш-адресом могут удлинить поиск элементов с другими хеш-адресами.

Одно из решений этих проблем - объединенное хеширование. Объединенное хеширование использует тот же метод, что и отдельное объединение в цепочку, но вместо выделения новых узлов для связанного списка используются сегменты в реальной таблице. Первое пустое ведро в таблице во время столкновения считается ковшом столкновения. Когда коллизия происходит где-нибудь в таблице, элемент помещается в коллизионную корзину, и между цепочкой и коллизионной корзиной устанавливается связь. Вновь вставленный элемент может столкнуться с элементами с другим хэш-адресом, как в примере на изображении, когда вставлен элемент «clq». Считается, что цепочка для «clq» «сливается» с цепочкой «qrj», отсюда и название алгоритма. Однако степень объединения незначительна по сравнению с кластеризацией при открытой адресации. Например, когда происходит объединение, длина цепочки увеличивается только на 1, тогда как при открытой адресации поисковые последовательности произвольной длины могут объединяться.

Погреб

Важной оптимизацией для уменьшения эффекта объединения является ограничение адресного пространства хэш-функции только подмножеством таблицы. Например, если размер таблицы M с ведрами, пронумерованными от 0 до M - 1, мы можем ограничить адресное пространство так, чтобы хеш-функция назначала адреса только первым N места в таблице. Остальное M - N ведра, называемые погреб, используются исключительно для хранения элементов, которые сталкиваются при вставке. Слипание не может произойти, пока погреб не будет исчерпан.

Оптимальный выбор N относительно M зависит от коэффициента загрузки (или наполненности) таблицы. Тщательный анализ показывает, что ценность N = 0,86 × M обеспечивает почти оптимальную производительность для большинства факторов нагрузки.^[1]^[2]

Варианты

Возможны и другие варианты вставки, которые сокращают время поиска. Были разработаны алгоритмы удаления, которые сохраняют случайность, и поэтому анализ среднего времени поиска все еще сохраняется после удалений.^[1]

Выполнение

Вставка в C:

/ * htab - хеш-таблица,   N - размер адресного пространства хеш-функции, а   M - это размер всего стола, включая погреб.   Блоки коллизий распределяются в порядке убывания, начиная с блока M-1. * /int вставить ( char ключ[] ){  беззнаковый час = хэш ( ключ, Strlen ( ключ ) ) % N;  если ( htab[час] == НОЛЬ ) {    / * Создаем новую цепочку * /    htab[час] = make_node ( ключ, НОЛЬ );  } еще {    структура узел *Это;    int курсор = M-1;    / * Находим первое пустое ведро * /    пока ( курсор >= 0 && htab[курсор] != НОЛЬ )      --курсор;    / * Таблица заполнена, завершение неудачно * /    если ( курсор == -1 )      вернуть -1;    htab[курсор] = make_node ( ключ, НОЛЬ );        / * Находим последний узел в цепочке и указываем на него * /    Это = htab[час];    пока ( Это->Следующий != НОЛЬ )      Это = Это->Следующий;    Это->Следующий = htab[курсор];  }  вернуть 0;}

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

Поиск в C:

char *найти ( char ключ[] ){  беззнаковый час = хэш ( ключ, Strlen ( ключ ) ) % N;  если ( htab[час] != НОЛЬ ) {    структура узел *Это;    / * Ищем цепочку по индексу h * /    за ( Это = htab[час]; Это != НОЛЬ; Это = Это->Следующий ) {      если ( strcmp ( ключ, Это->данные ) == 0 )        вернуть Это->данные;    }  }  вернуть НОЛЬ;}

Спектакль

Удаление может быть трудным.^[3]^[4]

Объединенная цепочка позволяет избежать эффектов первичной и вторичной кластеризации и, как результат, может использовать преимущества эффективного алгоритма поиска для раздельного объединения. Если цепочки короткие, эта стратегия очень эффективна и может быть сильно сжатой с точки зрения памяти. Как и при открытой адресации, удаление из объединенной хеш-таблицы неудобно и потенциально дорого, а изменение размера таблицы ужасно дорого и должно выполняться редко, если вообще когда-либо.^{[нужна цитата ]}