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

Чтобы не пришлось усложнять код, начнём со следующих допущений:

1. Ключи — это распределённые случайным образом 32-разрядные целые числа.

2. Значения — тоже 32-разрядные целые числа.

3. При наличии ключа 0 его значение не равно 0.

4. Таблица может занимать не более 32 ГиБ памяти.

Любая ячейка в таблице либо пустует, либо содержит ключ и значение. Благодаря сочетанию свойств (1) и (2), можно хранить пару ключ/значение в виде 64-разрядного целого числа, а свойство (3) позволяет представлять пустую ячейку при помощи 64-разрядного значения 0 (в некоторых вариантах хеш-таблиц, но не в этом, также требуется специальное значение, чтобы представлять надгробия). Нет ничего проще, чем скомбинировать ключ и значение в 64 разряда. В нижних 32 разрядах будет содержаться ключ, а в верхних 32 разрядах — значение.

В структуре, закладываемой для таблицы, понадобится указатель, направленный на массив ячеек, нужно будет указать длину этого массива и количество непустых ячеек. Поскольку длина всегда является степенью двойки, целесообразнее хранить не length, а length - 1, что приводит нас к использованию mask вместо length. Наконец, свойство (4) означает, что mask можно сохранить в 32 разрядах. Поскольку коэффициент заполнения не должен превышать 100%, можем исходить из того, что count < length, следовательно, для count также хватит 32 разрядов. В результате приходим к вполне будничному:

struct hash_table_t {
  uint64_t* slots;
  uint32_t mask;
  uint32_t count;
};

В соответствии со свойством (1) нам не требуется хешировать ключи, так как они уже распределены случайным образом. У любого возможного ключа K есть «естественная позиция» в массиве, которая определяется просто как K & mask. При возникновении коллизий бывает и так, что на самом деле ключ оказывается не там, где находится его естественная позиция. Что касается предусматриваемого при проектировании «линейного зондирования», вот о чём речь: если K не может быть в своей естественной позиции, далее переходим к рассмотрению ячейки (K + 1) & mask, а если и в этой ячейке значения не найдём, то перейдём к (K + 2) & mask, затем (K + 3) & mask и т.д. В результате можем дать такое определение «цепочки»: если K — это некоторый ключ, присутствующий в таблице, то CK означает последовательность ячеек, которая начинается с естественной позиции K и заканчивается фактической позицией K. Здесь мы опираемся на обычное свойство открытой адресации: ни одна ячейка в CK не пуста. «Робингудовский» аспект конфигурации привносит в неё ещё одно довольно интересное свойство: для каждой ячейки S в CK, Score(S.Index, S.Key) ≥ Score(S.Index, K), где:

• S.Index — это индекс S в массиве slots (а не её индекс в CK).

• S.Key — это ключ, находящийся в ячейке S (т.e., он занимает нижние 32 разряда slots[S.Index]).

• Score(Index, Key) — это (Index - Key) & mask.

В соответствии с этими свойствами вырисовываются условия завершения для алгоритма поиска: имея возможный ключ K, мы просматриваем каждую ячейку, начиная с естественной позиции K, и находим либо K, либо пустую ячейку, либо ячейку с Score(S.Index, S.Key) < Score(S.Index, K). В каждом из двух последних двух случаев K гарантированно отсутствует в таблице. В приведённой ниже функции Score(S.Index, K) отслеживается как d. В языке с современной системой типов поиск даст нам Optional<Value>. Но, если придерживаться чистого C, то нечто подобное достижимо через свойство (3): при отсутствии ключа 64-разрядный результат будет равен нулю. В противном случае значение будет записано в нижних 32 разрядах результата (они тоже могут быть нулями, но полный 64-разрядный результат будет ненулевым). Логика такова:

uint64_t table_lookup(hash_table_t* table, uint32_t key) {
  uint32_t mask = table->mask;
  uint64_t* slots = table->slots;
  for (uint32_t d = 0;; ++d) {
    uint32_t idx = (key + d) & mask;
    uint64_t slot = slots[idx];
    if (slot == 0) {
      return 0;
    } else if (key == (uint32_t)slot) {
      return (slot >> 32) | (slot << 32);
    } else if (((idx - (uint32_t)slot) & mask) < d) {
      return 0;
    }
  }
}

При использовании насыщенной 64-разрядной архитектуры ЦП многие выражения из приведённой выше функции не так затратны, как могут показаться на первый взгляд:

• slots[idx] требует дополнить idx нулями для перехода от 32 разрядов к 64, умножить его на sizeof(uint64_t), прибавить к slots, а затем загрузить с того адреса. В архитектурах x86-64 или arm64 всё это укладывается в одну инструкцию.

• key == (uint32_t)slot требует сравнения с участием нижних 32 разрядов 64-разрядного регистра, это совершенно стандартная операция в архитектурах x86-64 или arm64.

• (slot >> 32) | (slot << 32) — это поворот на 32 разряда, опять же, укладывающийся всего в одну инструкцию в архитектурах x86-64 или arm64.

С другой стороны, если вы работаете на riscv64, то всё складывается не так хорошо:

• При применении дополнения Zba, sh3add.uw — это всего одна инструкция, нужная, чтобы дополнить idx нулями от 32 разрядов до 64, с умножением этой величины на sizeof(uint64_t) и добавлением к slots. Если нет, то каждый шаг укладывается в отдельную инструкцию. Правда, дополнения нулями можно избежать, слегка переформулировав код. Так мы подталкиваем компилятор к тому, чтобы нагрузка, связанная с дополнением нулями, ложилась на table->mask (поскольку riscv64 обычно по умолчанию выбирает бесплатное расширение знака — в противовес архитектурам x86-64/arm64, где обычно обеспечивается бесплатное дополнение нулями. Как бы то ни было, загрузка всегда происходит в рамках отдельной инструкции.

• key == (uint32_t)slot натыкается на пробел, имеющийся в архитектуре riscv64: здесь нет никаких инструкций для сравнения 32-разрядных чисел, поэтому можно реализовать лишь вычитание 32-разрядных чисел с последующим 64-разрядным сравнением с нулём, либо расширение обоих операндов с 32 до 64 разрядов с последующим сравнением двух 64-разрядных чисел.

• При наличии расширения Zbb поворот укладывается в отдельную инструкцию. Если такого расширения нет, то на такую операцию нужны три инструкции, поэтому становится практически целесообразно переделать компоновку ячеек так, чтобы ключ помещался в верхние 32 разряда, а значение — в нижние 32 разряда.

Переходя от поиска к вставке, видим различные варианты действий, когда у нас уже есть ключ, который нужно вставить. Покажу вам вариант, в котором возвращается старое значение (в той же форме, в какой оно возвращается от table_lookup), которое затем затирается новым значением — хотя, очевидно, есть и другие варианты. В общем виде логика структурирована точно так же, как мы видели в table_lookup:

uint64_t table_set(hash_table_t* table, uint32_t key, uint32_t val) {
  uint32_t mask = table->mask;
  uint64_t* slots = table->slots;
  uint64_t kv = key + ((uint64_t)val << 32);
  for (uint32_t d = 0;; ++d) {
    uint32_t idx = ((uint32_t)kv + d) & mask;
    uint64_t slot = slots[idx];
    if (slot == 0) {
      // вставка нового значения (причём ранее ячейка была пуста)
      slots[idx] = kv;
      break;
    } else if ((uint32_t)kv == (uint32_t)slot) {
      // затирание имеющегося значения
      slots[idx] = kv;
      return (slot >> 32) | (slot << 32);
    } else {
      uint32_t d2 = (idx - (uint32_t)slot) & mask;
      if (d2 < d) {
        // Вставка нового значения, перемещение имеющейся ячейки
        slots[idx] = kv;
        table_reinsert(slots, mask, slot, d2);
        break;
      }
    }
  }
  if (++table->count * 4ull >= mask * 3ull) {
    // Расширение таблицы после того, как она заполнится на 75% 
    table_rehash(table);
  }
  return 0;
}

Чтобы не допускать чрезмерной заполненности таблицы, вышеприведённая функция иногда наращивает таблицу, вызывая для этого следующую вспомогательную функцию:

void table_rehash(hash_table_t* table) {
  uint32_t old_mask = table->mask;
  uint32_t new_mask = old_mask * 2u + 1u;
  uint64_t* new_slots = calloc(new_mask + 1ull, sizeof(uint64_t));
  uint64_t* old_slots = table->slots;
  uint32_t idx = 0;
  do {
    uint64_t slot = old_slots[idx];
    if (slot != 0) {
      table_reinsert(new_slots, new_mask, slot, 0);
    }
  } while (idx++ != old_mask);
  table->slots = new_slots;
  table->mask = new_mask;
  free(old_slots);
}

Как table_set, так и table_rehash использует вспомогательную функцию, очень напоминающую table_set. Но ей не требуется ни проверять затирание имеющегося ключа, ни обновлять count:

void table_reinsert(uint64_t* slots, uint32_t mask, uint64_t kv, uint32_t d) {
  for (;; ++d) {
    uint32_t idx = ((uint32_t)kv + d) & mask;
    uint64_t slot = slots[idx];
    if (slot == 0) {
      slots[idx] = kv;
      break;
    } else {
      uint32_t d2 = (idx - (uint32_t)slot) & mask;
      if (d2 < d) {
        slots[idx] = kv;
        kv = slot;
        d = d2;
      }
    }
  }
}

Итак, мы рассмотрели поиск и вставку, далее поговорим об удалении ключа. Как я уже намекал выше, в спроектированной таким образом хеш-таблице не нужны надгробия. Вместо этого, чтобы удалить ключ, нужно найти ячейку, в которой он находится, а затем сдвигать ячейки влево до тех пор, пока не будет найдена пустая ячейка либо ячейка с Score(S.Index, S.Key) == 0. Такая стратегия работает, поскольку у таблицы есть два удобных эмерджентных свойства:

• Если ячейке S свойственно Score(S.Index, S.Key) != 0, то для S.Key допустимо находиться в (S.Index - 1) & mask (может быть, тут понадобится дополнительное переупорядочивание, чтобы заполнить пробел, оставшийся от перемещения S.Key).

• Если ячейке S свойственно Score(S.Index, S.Key) == 0, и S входит в состав некоторой цепочки CK, то S находится в самом начале CK. Таким образом, вполне можно превратить (S.Index - 1) & mask в пустую ячейку, не разрывая при этом никаких цепочек.

Так получается функция удаления, не содержащая надгробий, при работе следующая устоявшемуся паттерну, когда возвращается либо старое значение, либо ноль:

uint64_t table_remove(hash_table_t* table, uint32_t key) {
  uint32_t mask = table->mask;
  uint64_t* slots = table->slots;
  for (uint32_t d = 0;; ++d) {
    uint32_t idx = (key + d) & mask;
    uint64_t slot = slots[idx];
    if (slot == 0) {
      return 0;
    } else if (key == (uint32_t)slot) {
      uint32_t nxt = (idx + 1) & mask;
      --table->count;
      while (slots[nxt] && ((slots[nxt] ^ nxt) & mask)) {
        slots[idx] = slots[nxt];
        idx = nxt;
        nxt = (idx + 1) & mask;
      }
      slots[idx] = 0;
      return (slot >> 32) | (slot << 32);
    } else if (((idx - (uint32_t)slot) & mask) < d) {
      return 0;
    }
  }
}

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

void table_iterate(hash_table_t* table, void(*visit)(uint32_t key, uint32_t val)) {
  uint64_t* slots = table->slots;
  uint32_t mask = table->mask;
  uint32_t idx = 0;
  do {
    uint64_t slot = slots[idx];
    if (slot != 0) {
      visit((uint32_t)slot, (uint32_t)(slot >> 32));
    }
  } while (idx++ != mask);
}

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

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

Функции table_lookup, table_set и table_remove получают key = hash(key) в самом начале работы, но в остальном не модифицируются. При этом отметим: если хеш-функция является инвертируемой, то равенство хешей подразумевает равенство ключей — поэтому нет необходимости явно проверять равенство ключей. В свою очередь, table_iterate модифицируется так, чтобы сначала применялась обратная функция, а затем шёл вызов visit. Если у вас в распоряжении имеются аппаратные инструкции CRC32 / CRC32C (так и есть в большинстве относительно современных чипов x86-64 и arm64), то их можно задействовать для этой задачи. Хотя, вычислять их обратные довольно возможно, так что такой вариант неидеален, если операция перебора является важной. Если работа с CRC32 не подходит, то вот один из многих имеющихся вариантов:

Если ключи и значения больше 32 разрядов, то такой проект можно дополнить отдельным массивом пар ключ/значение. Получим вариант, показанный выше, где содержится 32-разрядный хеш ключа и массив индексов пар ключ/значение. Чтобы в данном случае соблюсти свойство (3), нужно либо выбрать такую хеш-функцию, которая никогда не будет равна нулю, либо хранить не «индекс массива», а «индекс массива плюс один». В данном случае не получится сделать хеш-функцию инвертируемой, так что table_lookup, table_set и table_remove действительно придётся расширять, чтобы проверить равенство ключей уже после подтверждения равенства хешей. При переборе придётся обойти отдельный массив пар ключ/значение, а не структуру хеша. Это тем более удобно, потому что вставка связана с порядком перебора, а не с порядком хеша. Вот ещё одна интересная грань этой проблемы: если как ключи, так и значения имеют переменный размер, то спроектированную нами таблицу можно дополнить отдельным массивом байт. Где-то в этом массиве сериализуются пары ключ/значение, а структура хеша содержит 32-разрядный хеш ключа и байтовый сдвиг пар ключ/значение (внутри массива).

Разумеется, у такого дизайна есть пределы растяжимости. Если вам нужна хеш-таблица, обеспечивающая конкурентную неблокирующую обработку — поищите другой вариант. Если вы уверены, что сможете опираться на 128-разрядные SIMD-инструкции, то попробуйте сгруппировать пары ключ/значение по 16 штук, храните 8-разрядный хеш каждого ключа и полагайтесь на SIMD-инструкции, которые могут параллельно выполнять 16 операций сравнения хеша. Если вы разрабатываете аппаратное, а не программное обеспечение, то, возможно, вы предпочтёте иметь множество хеш-функций, каждая из которых адресует собственный SRAM-банк памяти. Одной хеш-таблицы на все случаи жизни не подобрать, но та, которую я показал здесь, хорошо подходит мне для многих моих задач.