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

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

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

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

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

Пример

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

(нулевой)
"клк"
"кур"
(нулевой)
(нулевой)
"тусклый"
"ати"	"ксу"
"рхв"
"qrj"	"офу"	"гкл"	"ЭКД"
(нулевой)

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

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

Подвал

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

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

Варианты

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

Выполнение

Вставка в C :

/* htab is the hash table,
   N is the size of the address space of the hash function, and
   M is the size of the entire table including the cellar.
   Collision buckets are allocated in decreasing order, starting with bucket M-1. */

int insert ( char key[] )
{
  unsigned h = hash ( key, strlen ( key ) ) % N;

  if ( htab[h] == NULL ) {
    /* Make a new chain */
    htab[h] = make_node ( key, NULL );
  } else {
    struct node *it;
    int cursor = M-1;

    /* Find the first empty bucket */
    while ( cursor >= 0 && htab[cursor] != NULL )
      --cursor;

    /* The table is full, terminate unsuccessfully */
    if ( cursor == -1 )
      return -1;

    htab[cursor] = make_node ( key, NULL );
    
    /* Find the last node in the chain and point to it */
    it = htab[h];

    while ( it->next != NULL )
      it = it->next;

    it->next = htab[cursor];
  }

  return 0;
}

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

Поиск в C:

char *find ( char key[] )
{
  unsigned h = hash ( key, strlen ( key ) ) % N;

  if ( htab[h] != NULL ) {
    struct node *it;

    /* Search the chain at index h */
    for ( it = htab[h]; it != NULL; it = it->next ) {
      if ( strcmp ( key, it->data ) == 0 )
        return it->data;
    }
  }

  return NULL;
}

Производительность

Удаление может оказаться трудным.

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