Хеш-таблица

Разрешение коллизий при помощи цепочек.

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

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

При предположении, что каждый элемент может попасть в любую позицию таблицы H с равной вероятностью и независимо от того, куда попал любой другой элемент, среднее время работы операции поиска элемента составляет Θ(1 + α), где α — коэффициент заполнения таблицы.

Пример хеш-таблицы с открытой адресацией и линейным пробированием, получающейся при вставке элементов в левой колонке сверху вниз.

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

Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. В общем случае, она зависит только от ключа элемента, то есть это последовательность h₀(x), h₁(x), …, h_{n — 1}(x), где x — ключ элемента, а h_i(x) — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него одним из приведённых ниже способов. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.

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

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

Последовательности проб

Ниже приведены некоторые распространенные типы последовательностей проб. Сразу оговорим, что нумерация элементов последовательности проб и ячеек хеш-таблицы ведётся от нуля, а N — размер хеш-таблицы (и, как замечено выше, также и длина последовательности проб).

• Линейное пробирование: ячейки хеш-таблицы последовательно просматриваются с некоторым фиксированным интервалом k между ячейками (обычно k = 1), то есть i-й элемент последовательности проб — это ячейка с номером (hash(x) + ik) mod N. Для того, чтобы все ячейки оказались просмотренными по одному разу, необходимо, чтобы k было взаимно-простым с размером хеш-таблицы.
• Квадратичное пробирование: интервал между ячейками с каждым шагом увеличивается на константу. Если размер хеш-таблицы равен степени двойки (N = 2^p), то одним из примеров последовательности, при которой каждый элемент будет просмотрен по одному разу, является:

  hash(x) mod N, (hash(x) + (1+1*1)/2) mod N, (hash(x) + (2+2*2)/2) mod N, (hash(x) + (3+3*3)/2) mod N, … - треугольные числа.

• Двойное хеширование: интервал между ячейками фиксирован, как при линейном пробировании, но, в отличие от него, размер интервала вычисляется второй, вспомогательной хеш-функцией, а значит, может быть различным для разных ключей. Значения этой хеш-функции должны быть ненулевыми и взаимно-простыми с размером хеш-таблицы, что проще всего достичь, взяв простое число в качестве размера, и потребовав, чтобы вспомогательная хеш-функция принимала значения от 1 до N — 1.

Ниже представлен код, демонстрирующий двойное хеширование:

// DICT_CELL_COUNT должно быть простым числом!
#define DICT_CELL_COUNT 30011

char* szWordAr[ DICT_CELL_COUNT ];
unsigned int uWordArSize = 0;

#define WORD_IDX_BAD (( unsigned int )-1)

unsigned int uWordIdxByHashAr[ DICT_CELL_COUNT ]; // необходимо инициализировать элементы значением WORD_IDX_BAD

#define STRIDE_1 17
#define STRIDE_2 13

// Функция GetOrAddWordIdx( .. ) возвращает индекс слова pcszWord в массиве szWordAr.
// При этом происходит добавление слова pcszWord в словарь szWordAr, если его там нет.

unsigned int GetOrAddWordIdx( const char* const pcszWord )
  {
    unsigned int uHash1 = 0, uHash2 = 0;

    const unsigned char* cbtWordCharCur = ( const unsigned char* )pcszWord;

    // Вычислим два хеша слова pcszWord:
    // uHash1 лежит в диапазоне [ 0 .. DICT_CELL_COUNT - 1 ]
    // uHash2 лежит в диапазоне [ 1 .. DICT_CELL_COUNT - 1 ]

    do
      {
        uHash1 *= STRIDE_1; uHash1 += ( STRIDE_2 * *cbtWordCharCur );
        uHash2 *= STRIDE_2; uHash2 += ( STRIDE_1 * *cbtWordCharCur );
      }
    while( *( cbtWordCharCur++ ) ); // NB: инкремент!

    // #1: cbtWordCharCur указывает на символ за посл. '\0' в pcszWord,
    // будет использовано в #2

    uHash1 %= DICT_CELL_COUNT;
    uHash2 %= ( DICT_CELL_COUNT - 1 ); ++uHash2;

    while( uWordIdxByHashAr[ uHash1 ] != WORD_IDX_BAD  )
      {
        if ( !strcmp( pcszWord, szWordAr[ uWordIdxByHashAr[ uHash1 ] ] ) )
          return uWordIdxByHashAr[ uHash1 ];

        uHash1 += uHash2; uHash1 %= DICT_CELL_COUNT;
      }

    strcpy(
      szWordAr[
        uWordIdxByHashAr[ uHash1 ] = // NB: присвоение!
          uWordArSize
      ] = // NB: присвоение!
        ( char* )malloc(
          // длина pcszWord плюс 1:
          ( const char* )cbtWordCharCur - // #2: используем значение cbtWordCharCur из #1
            pcszWord
        ),
      pcszWord
    );

    return uWordArSize++; // NB: инкремент!
  } // unsigned int GetOrAddWordIdx( const char* const pcszWord )