Я из тех, кто всерьёз задумывается о проектировании и реализации хеш-таблиц. Недавно обнаружился донельзя милый вариант, который заслуживает широкой огласки. Это робин-гудовская открытая адресация с применением линейного зондирования, где размер самой таблицы увеличивается как степень двойки. Если вы не знакомы с терминологией хеш-таблиц, то все эти слова могут показаться вам каким-то невразумительным салатиком, но, когда мы разберём этот пример с привлечением кода — всё должно стать понятнее.
Чтобы не пришлось усложнять код, начнём со следующих допущений:
Ключи — это распределённые случайным образом 32-разрядные целые числа.
Значения — тоже 32-разрядные целые числа.
При наличии ключа 0 его значение не равно 0.
Таблица может занимать не более 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-банк памяти. Одной хеш-таблицы на все случаи жизни не подобрать, ��о та, которую я показал здесь, хорошо подходит мне для многих моих задач.