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

Простой массив из пар ключей и значений

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

Добавление элемента в такой контейнер устроено очень легко - просто дописываем элемент в конец массива. Алгоритмическая сложность O(1). Если, конечно, у нас не кончится память выделенная под массив и не придётся запрашивать у ОС новый кусок, но этот выходит за рамки данной статьи.

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

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

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

Отсортированный массив из пар ключей и значений

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

В таком случае мы сможем использовать бинарный поиск и для собственно поиска нужного ключа, и для его вставки. В итоге поиск будет иметь алгоритмическую сложность O(logN), что значительно лучше предыдущего варианта. Вставка будет иметь сложность в худшем случае O(N), потому что хоть место вставки мы и можем найти на O(logN), но в зависимости от того куда нам нужно вставить элемент, нам потребуется двигать все элементы, которые расположены после него. Удаление тоже будет иметь сложность O(N) по той же причине сдвига элементов.

Можно отойти от массива в сторону бинарного дерева, тогда вставка и удаление станут также как и поиск O(logN).

По такому принципу устроен контейнер std::map из C++, а также TreeMap из Java.

Ещё мы получаем побочный эффект, что мы в любой момент можем обойти все элементы контейнера в порядке возрастания/убывания ключей. Это может быть полезно (например, для вывода на экран в отсортированном виде).

Из минусов, собственно, что нам нужно иметь эту самую функцию сравнения "больше"/"меньше" для нашего типа ключей. И если для чисел и даже строк вопросов обычно не возникает, то при использовании более сложных ключей интуитивной функции сравнения может и не быть (ну, например, как сравнить две трёхмерные координаты?). Конечно, всегда можно придумать фиктивную функцию сравнения, но это уже не так удобно.

Ну и ещё алгоритмы работы с бинарными деревьями часто весьма нетривиальны для понимания и написания, если по какой-то причине мы не можем воспользоваться готовой библиотекой.

Хеш-таблица

Как было бы удобно, если бы все ключи имели однозначное соответствие числам, причём небольшим числам (относительно объёма памяти компьютера, которую мы морально готовы отдать под хранение наших данных). Тогда можно было бы просто использовать их как индексы в массиве.

void print_char_count(const char *s) {
  int counts[256];
  memset(counts, 0, sizeof(counts));
  while (*s) {
    counts[(unsigned char) *s]++;
    s++;
  }
  for (int i = 0; i < 256; i++) {
    if (counts[i] > 0) {
      printf("%c: %i\n", i, counts[i]);
    }
  }
}

Например, в задаче подсчёта количества повторений символов в строке мы можем просто завести массив из 256 элементов, зная, что код символа в ASCII не может превышать 255. И когда нам нужно узнать или увеличить счётчик повтора символов, просто использовать числовой код символа как индекс в этом массиве. Алгоритмическая сложность доступа к одному счётчику - O(1).

Однако, часто тип ключа имеет слишком много возможных значений. Например, даже обычный числовой ключ int имеет больше 4 миллиардов возможных значений. Строки вообще условно бесконечное количество значений (на практике ограничено размером ОЗУ компьютера). Нет никакой возможности заводить массивы такой размерности.

Однако, существует решение этой проблемы и этим решением является применение хеш-функции. Хеш-функция - это одностороннее преобразование с потерей информации, позволяющее свести большую область значений к меньшей. Простейшей хеш-функцией будет, например, взятие остатка от деления. Например, беря остаток от деления на 1000 мы сводим множество из 4 миллиардов значений int к 2000 значений (из-за отрицательных чисел, для unsigned int множество стало бы ещё меньше - всего 1000 значений).

Ну вот мы и придумали хеш-таблицы. Чтобы построить хеш-таблицу нужно совершить два действия: вычислить хеш от ключа, а затем найти его остаток от деления на длину массива, в котором мы решили хранить наши данные (исходя из доступных нам ресурсов и ожидаемого объёма данных). Этот результат и будет индексом, по которому нужно сохранять наш элемент или наоборот извлекать. Неиспользуемые ячейки массива можно пометить каким-нибудь образом (сохранить туда "невозможное" значение ключа, либо завести дополнительную карту занятости ячеек).

Однако, такое простое решение не могло бы не иметь подвоха. Поскольку мы сводим большее множество значений к меньшему, неизбежны коллизии. Например, для хеш-функции остатка от деления на 1000, числа 123, 1123, 2123, 1000123 дадут один и тот же результат. В итоге все эти значения должны будут быть сохранены в одной и той же ячейке нашего массива, но мы можем хранить только одно значение. Что же делать?

Существует два основных подхода к решению этой проблемы.

Во-первых, кто сказал, что одна ячейка массива не может хранить множество значений? Пусть у нас будет не массив значений, а массив связанных списков наших значений (или массив динамических массивов наших значений). Если случается коллизия, то просто добавляем новый элемент в список. При поиске ключа если в ячейке несколько значений, то ищем нужное обычным перебором (поэтому хеш-таблице важно, чтобы для ключей была определена не только хеш-функция, но и функция сравнения, но в отличии от подхода с отсортированным массивом, функции сравнения нужно выдавать только "равно"/"неравно" и её легко интуитивно определить для любого типа ключа). Таким образом теоретически имеем алгоритмическую сложность O(N), но на практике принято говорить о "средней" сложности O(1). Так как для худшего случая нам должно очень неповезти и для абсолютно всех элементов нашего контейнера должно совпасть значение хеш-функции. На практике хеш-функции выбираются таким образом, чтобы коллизии были весьма редки (особенно на конкретном типе наборов данных, с которыми будет работать программа).

У этого подхода есть минус - как уже было сказано выше, связанные списки плохо дружат с кешами современных процессоров, потому что данные оказываются размазаны по всему адресному пространству вместо того, чтобы быть расположенными рядом. К тому же, каждое добавление элемента будет вызывать обращение к менеджеру памяти за новым кусочком памяти, что тоже весьма небыстрое дело. Конечно, можно использовать вместо связанного списка динамический массив, но это не сильно спасает ситуацию. Если под саму хеш-таблицу мы можем заранее выделить память по принципу "мы ожидаем получить N элементов, значит создадим массив на (N + некая констата) элементов", то поступить так с внутренними массивами элементов мы не можем, иначе наша программа будет потреблять N^2 памяти, что редко бывает допустимо. Угадать какой именно ячейке хеш-таблицы "не повезёт" заранее и выделить много памяти только ей, мы тоже едва ли можем.

Этот подход использует std::unordered_map из C++ и HashMap из Java. Также его использует uthash.

К счастью, есть ещё одно решение. Допустим, мы вычислили хеш и обнаружили, что в соответствующей ему ячейке хеш-таблицы уже лежит значение. Не беда! Просто посмотрим в следующую за ней ячейку (значение хеша + 1). Если и там занято, смотрим следующую за ней и т. д. При достижении последнего индекса массива, переходим к нулевому. Если хеш-таблица имеет размер N, то по такому алгоритму мы гарантированно сможем положить в неё не меньше N элементов (для N + 1 элемента мы не найдём свободного места перебрав все элементы и единственным выходом будет увеличить её размер). Алгоритм поиска аналогичен - вычисляем хеш элемента, а затем сравниваем ключ с тем, что реально лежит по этому индексу. Если там лежит что-то не то, то смотрим ключ следующего элемента. Повторяем, пока не найдём нужный элемент, пока не сделаем полный круг, либо пока не встретим пустое место. По нашему алгоритму вставки, мы не могли пропустить пустое место, если бы пытались вставить нужный нам ключ, так что обнаружение пустого места гарантирует, что этого элемента в таблице нет.

Несложно догадаться, что при полной заполненности хеш-таблицы и при поиске отсутствующего элемента, мы гарантированно обойдем все элементы массива, получая сложность O(N). Звучит не круто, поэтому держать такие хеш-таблицы полными не принято, а принято говорить о "коэффициенте заполнения" при превышении которого хеш-таблица увеличивается в размере несмотря на то, что технически в неё ещё можно было вставить элемент. Считается хорошим значением коэффициента заполнения число близкое к 75%. Это значит, что хеш-таблица на 100 элементов, в которую реально вставлено 75 элементов, при вставе 76-го обязана вырасти в размере несмотря на наличие свободных мест. Такой подход создаёт некоторый оверхед по памяти, зато даёт значительный выигрыш в скорости. К тому же чем больше свободных элементов, тем ниже вероятность коллизии хеш-функции в целом.

Итак, мы имеем худшую сложность вставки O(N), среднюю O(1). При этом наша структура данных имеет отличную локальность (все элементы хранятся рядом), что хорошо для работы процессора с кешем. Если известно максимальное число элементов, можно заранее создать хеш-таблицу нужного размера и гарантированно избежать перевыделения памяти. Идеально же?

Конечно, не бывает ничего идеального. Можно легко догадаться, что каждая коллизия в такой таблице повышает вероятность следующей коллизии - ведь элемент, у которого случилась коллизия, займёт место, куда должны был встать другой элемент. И этот элемент тоже будет вынужден занять не своё место и т. д. Для многих наборов данных и хеш-функций это не является большой проблемой, однако существует модификация алгоритма выбора места в среднем улучшающая ситуацию - квадратичный поиск (quadratic probing). Идея в том, что мы после первого обнаруженного занятого места, смотрим в следующее. Если и оно занято, то смотрим не в следующее, а через одно. Если и там занято, то через два и т. д. То есть каждая неудачная попытка занять место увеличивает на единицу шаг, с которым происходит выбор следующего места. На практике согласно исследованиям это часто даёт лучшие результаты.

Этот подход использует absl::flat_hash_map из библиотеки Abseil для C++ и HashMap из стандартной библиотеки Rust.

Итак, мы определились со структурой данных, которую будем реализовывать.

Удаление элементов

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

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

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

Ещё одна оптимизация

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

Реализация

Ну вот, теперь мы знаем достаточно для того, чтобы приступить к практической части статьи.

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

Итак, начнём с определения структуры данных, которая будет хранить нашу хеш-таблицу:

#define HT(key_type, value_type) struct { \
	size_t size, max_size, capacity; \
	char *flags; \
	key_type *keys; \
	value_type *values; \
}

Мы объявили макрос HT, который принимает желаемый тип ключа и значения и объявляет структуру, содержащую следующие поля:

• capacity - текущий размер хеш-таблицы. Обязан быть степенью 2, либо нулём, если память под хеш-таблицу ещё не была выделена.

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

• max_size - максимальный размер хеш-таблицы до увеличения. Всегда меньше capacity из-за "коэффициента заполнения". Мы могли бы считать его при каждой вставке элемента, но с целью оптимизации будем расчитывать его только при увеличении размера хеш-таблицы и сохранять

• flags - массив из capacity флагов, каждый из которых задаёт состояние соответствующей ему ячейки хеш-таблицы. 0 - свободна, 1 - занята, 2 - удалена. Можно было бы использовать битовую карту, которая бы занимала в 4 раза меньше памяти (2 бита на элемент), но это бы усложнило код, к тому же было бы спорным решением с точки зрения производительности (так как процессору пришлось бы выполнять дополнительные битовые операции для определения состояния элемента), а оверхед не такой большой (например, для хеш-таблицы с ключами и значениями int, оверхед составит всего лишь 1/8).

• keys - массив ключей.

• values - массив значений. На самом деле опционален и можно легко убрать его из структуры и из всех функций, превратив наш HashMap в HashSet. Но сегодня мы реализуем именно Map.

Этот макрос можно использовать как для объявления нового типа, так и напрямую при объявлении переменной или поля другой структуры:

typedef HT(int, int) IntToIntMap;
...
struct MyStruct {
  HT(int, int) int_to_int_map;
};
...
HT(int, int) int_to_int_map;

Удобно!

Теперь реализуем конструктор и деструктор для нашей структуры:

#define ht_init(h) do { \
	(h).size = (h).max_size = (h).capacity = 0; \
	(h).flags = NULL; \
	(h).keys = NULL; \
	(h).values = NULL; \
} while (0)

#define ht_destroy(h) do { \
    free((h).values); \
    free((h).keys); \
    free((h).flags); \
} while (0)

Используем стандартный трюк с do { ... } while (0), чтобы записать в макросе несколько команд. Если бы мы не обрамили их в цикл, то пользователь получил бы весьма неожиданный результат при попытке вызова наших "функций", например, в комбинации с if. Можете представить во что развернулся бы такой код, если бы не было цикла:

if (we_need_hash_table) ht_init(my_hash_table);

При этом из-за ложного условия в while, цикл гарантированно выполнится лишь один раз.

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

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

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

Теперь напишем несколько тривиальных геттеров:

#define ht_size(h) ((h).size)
#define ht_max_size(h) ((h).max_size)
#define ht_capacity(h) ((h).capacity)
#define ht_key(h, index) ((h).keys[(index)])
#define ht_value(h, index) ((h).values[(index)])

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

Напишем первую функцию модификации контейнера - его очистку:

#define ht_clear(h) do { \
    (h).size = 0; \
    if ((h).flags) { memset((h).flags, 0, (h).capacity); } \
} while (0)

Очистка хеш-таблицы выполняется тривиальным образом - мы просто обнуляем счётчик элементов и сбрасываем все флаги их состояний в значение 0 (свободно).

Так как это C, а не C++, никаких деструкторов у элементов нет, предполагается, что если элементы нуждаются в каком-то нетривиальном удалении (например, они содержат в себе указатели на данные в куче, для которых нужно сделать отдельный free), пользователь сначала выполнит его вручную перебрав все элементы (как это сделать, мы рассмотрим дальше), а уже потом вызовет нашу функцию ht_clear. Кстати, ht_destroy это тоже касается.

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

Теперь перейдём к более сложной части - напишем функцию поиска элемента по ключу. Тут мы сталкиваемся с первой проблемой макросов C, что мы не можем вернуть значение из макроса как из обычной функции. Точнее, на самом деле нам доступно что-то такое за счёт оператора "запятая" (вычисляются все подвыражения разделённые запятой, при этом всё выражение целиком будет равно последнему вычисленному, а порядок вычисления фиксирован и не является UB):

/** Round up a 8-bit integer variable `x` to a nearest power of 2  */
#define roundup8(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, ++(x))

Но этот способ подходит только для простых алгоритмов без циклов, локальных переменных и с ограниченными ветвлениями (на тернарном операторе).

Нам остаётся только принимать в качестве одного из параметров макроса имя переменной, куда нужно положить результат:

#define ht_get(h, key, result, hash_func, eq_func) do { \
	if (!(h).size) { \
		(result) = 0; \
		break; \
	} \
	size_t ht_mask = (h).capacity - 1; \
	(result) = hash_func(key) & ht_mask; \
	size_t ht_step = 0; \
	while ((h).flags[(result)] == 2 || ((h).flags[(result)] == 1 && !eq_func((h).keys[(result)], (key)))) { \
		(result) = ((result) + ++ht_step) & ht_mask; \
	} \
} while (0)

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

if (!(h).size) {
	(result) = 0;
	break;
}

Первым делом выполняем проверку, что в хеш-таблице в принципе есть элементы. Иначе в ситуации, когда capacity == 0, мы можем устроить разыменовывание NULL указателя обратившись к массиву flags. Однако, проверять на ноль size вместо capacity лучше, потому что так мы дополнительно тем же числом операций обработаем ситуацию с пустой хеш-таблицей, в которой раньше были элементы и поэтому память для неё уже выделена.

Возвращаем нулевой индекс, который, впрочем, гарантированно ссылается либо на свободный, либо на удалённый элемент (если flags вообще не равен NULL). Почему важно хоть что-то вернуть рассмотрим дальше. Также можно обратить внимание на использование оператора break в качестве преждевременного возврата из "функции", который работает за счёт того, что наш код обрамлён в цикл.

size_t ht_mask = (h).capacity - 1;
(result) = hash_func(key) & ht_mask;

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

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

size_t ht_step = 1;
while (
        (h).flags[(result)] == 2 || 
        (
            (h).flags[(result)] == 1 && 
            !eq_func((h).keys[(result)], (key))
        )
) {
	(result) = ((result) + ht_step) & ht_mask;
    ht_step++;
}

Выполняем цикл поиска элемента. Если элемент удалён (флаг равен 2), то просто пропускаем его. Если элемент занят, то вызываем функцию сравнения ключа. Так или иначе, если мы решаем пропустить элемент, то увеличиваем индекс на величину шага (не забывая найти остаток от деления на размер хеш-таблицы, чтобы не выйти за границу) и затем увеличиваем шаг (вспомните про quadratic probing). В принципе хеш-таблица будет работать и если бы мы использовали линейный поиск (главное, использовать одинаковый алгоритм во всех функциях работающих с таблицей):

(result) = ((result) + 1) & ht_mask;

На этом как ни странно всё, сразу после завершения цикла, код нашей функции заканчивается. На выходе в result будет лежать либо индекс элемента с запрошенным ключом, либо индекс свободного элемента (у которого flags[result] == 0). Это единственные два варианта выхода из цикла.

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

#define ht_valid(h, index) ((h).flags && (h).flags[(index)] == 1)

Функция возвращает true только если под массив флагов выделена память, а в соответствующей индексу ячейке флагов лежит единица, обозначющая статус "занят".

Теперь нашей функцией поиска элемента можно пользоваться как-то так:

HT(const char*, int) my_hash_table;
...
size_t i;
ht_get(my_hash_table, "Hello", i, ht_str_hash, ht_str_eq);
if (ht_valid(my_hash_table, i)) {
    // Действия, если элемент найден. Например:
    printf("%s = %i", ht_key(my_hash_table, i), ht_value(my_hash_table, i));
} else {
    // Действия, если элемент не найден
}

Теперь реализуем функцию добавления элемента в хеш-таблицу:

#define ht_put(h, key_type, value_type, key, index, absent, hash_func, eq_func) do { \
	bool ht_success; \
	size_t ht_new_size = (h).size ? (h).size + 1 : 2; \
	ht_reserve((h), key_type, value_type, ht_new_size, ht_success, hash_func); \
	if (!ht_success) { \
		(absent) = -1; \
		break; \
	} \
	size_t ht_mask = (h).capacity - 1; \
	(index) = hash_func(key) & ht_mask; \
	size_t ht_step = 0; \
	while ((h).flags[(index)] == 2 || ((h).flags[(index)] == 1 && !eq_func((h).keys[(index)], (key)))) { \
		(index) = ((index) + ++ht_step) & ht_mask; \
	} \
	if ((h).flags[(index)] == 1) { \
		(absent) = 0; \
	} else { \
		(h).flags[(index)] = 1; \
		(h).keys[(index)] = (key); \
		(h).size++; \
		(absent) = 1; \
	} \
} while (0)

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

Вначале нам необходимо убедиться, что в хеш-таблице достаточно места для нового значения и если это не так, то расширить её:

bool ht_success;
size_t ht_new_size = (h).size ? (h).size + 1 : 2;
ht_reserve((h), key_type, value_type, ht_new_size, ht_success, hash_func);
if (!ht_success) {
	(absent) = -1;
	break;
}

Здесь мы вызываем пока не реализованную функцию ht_reserve, её задачей является убедиться, что в хеш-таблице можно сохранить не менее ht_new_size элементов (с учётом коэффициента заполнения), в противном случае она должна переаллоцировать хеш-таблицу с увеличением её размера. Она также возвращает результат своей работы в булева-переменной ht_success, которая будет false, если случилась ошибка выделения памяти и true во всех остальных случаях (в том числе в ситуации, когда выделять память не потребовалось).

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

size_t ht_mask = (h).capacity - 1;
(index) = hash_func(key) & ht_mask;
size_t ht_step = 0;
while ((h).flags[(index)] == 1 && !eq_func((h).keys[(index)], (key))) {
	(index) = ((index) + ++ht_step) & ht_mask;
}

Дальше идёт копипаста из функции поиска элемента, только мы не пропускаем удалённые элементы, а также на этот раз мы не оставливаемся на обнаружении элемента (или обнаружении его отсутствия), а пойдём дальше:

if ((h).flags[(index)] == 1) {
	(absent) = 0;
} else {
    (h).flags[(index)] = 1;
	(h).keys[(index)] = (key);
	(h).size++;
	(absent) = 1;
}

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

В случае если место не пустое, в хеш-таблице уже существует элемент с таким ключом, ничего не делаем с ним, а просто возвращаем absent = 0.

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

На этом наша функция вставки завершена. Её можно использовать как-то так:

HT(const char*, int) my_hash_table;
...
size_t i;
int absent;
ht_put(my_hash_table, const char*, int, "Hello", i, absent, ht_str_hash, ht_str_eq);
if (absent) { // Игнорируем ошибку выделения памяти
    // Действия, если элемент был вставлен
    ht_value(my_hash_table_size) = 10;
} else {
    // Действия, если элемент уже существует
}

Нам не хватает одной важной детали - функции ht_reserve. Это будет самая длинная функция нашей библиотеки:

#define ht_reserve(h, key_type, value_type, new_capacity, success, hash_func) do { \
	if (new_capacity <= (h).max_size) { \
		(success) = true; \
		break; \
	} \
	size_t ht_new_capacity = (new_capacity); \
	roundupsize(ht_new_capacity); \
	if (ht_new_capacity <= (h).capacity) { \
		ht_new_capacity <<= 1; \
	} \
	char *ht_new_flags = malloc(ht_new_capacity); \
	if (!ht_new_flags) { \
		(success) = false; \
		break; \
	} \
	key_type *ht_new_keys = malloc(ht_new_capacity * sizeof(key_type)); \
	if (!ht_new_keys) { \
		free(ht_new_flags); \
		(success) = false; \
		break; \
	} \
	value_type *ht_new_values = malloc(ht_new_capacity * sizeof(value_type)); \
	if (!ht_new_values) { \
		free(ht_new_keys); \
		free(ht_new_flags); \
		(success) = false; \
		break; \
	} \
	memset(ht_new_flags, 0, ht_new_capacity); \
	size_t ht_mask = ht_new_capacity - 1; \
	for (size_t ht_i = 0; ht_i < (h).capacity; ht_i++) { \
		if ((h).flags[ht_i] != 1) continue; \
		size_t ht_j = hash_func((h).keys[ht_i]) & ht_mask; \
		size_t ht_step = 0; \
		while (ht_new_flags[ht_j]) { \
			ht_j = (ht_j + ++ht_step) & ht_mask; \
		} \
		ht_new_flags[ht_j] = 1; \
		ht_new_keys[ht_j] = (h).keys[ht_i]; \
		ht_new_values[ht_j] = (h).values[ht_i]; \
	} \
	free((h).values); \
	free((h).keys); \
	free((h).flags); \
	(h).flags = ht_new_flags; \
	(h).keys = ht_new_keys; \
	(h).values = ht_new_values; \
	(h).capacity = ht_new_capacity; \
	(h).max_size = (ht_new_capacity >> 1) + (ht_new_capacity >> 2); \
	(success) = true; \
} while (0)

Для начала мы проверяем, нужно ли вообще расширять хеш-таблицу. Возможно, в ней ещё достаточно места:

if (new_capacity <= (h).max_size) {
	(success) = true;
	break;
}

Если мы достигли порога расширения, нужно вычислить новую ёмкость:

size_t ht_new_capacity = (new_capacity);
roundupsize(ht_new_capacity);
if (ht_new_capacity <= (h).capacity) {
	ht_new_capacity <<= 1;
}

Мы округляем запрошенную ёмкость до ближайшей большей степени двойки с помощью вспомогательной функции roundupsize (рассмотрим её ниже), а если результат получился меньше текущей ёмкости, умножаем его на 2. Мы могли бы всегда просто умножать текущую ёмкость на 2, однако так мы делаем функцию ht_reserve универсальнее - её может вызывать не только ht_put, но и сам пользователь, если он заранее знает сколько элементов ожидается в его хеш-таблице, чтобы избежать лишних перевыделений памяти.

Теперь, когда мы знаем новую ёмкость, можно выделить новую память под все структуры (именно для этого нам нужен key_type и value_type, к сожалению, пока в C нету оператора аналогичного typeof из C++, чтобы мы могли автоматически вывести нужные типы из типов полей структуры):

if (!ht_new_flags) {
	(success) = false;
	break;
}
key_type *ht_new_keys = malloc(ht_new_capacity * sizeof(key_type));
if (!ht_new_keys) {
	free(ht_new_flags);
	(success) = false;
	break;
}
value_type *ht_new_values = malloc(ht_new_capacity * sizeof(value_type));
if (!ht_new_values) {
	free(ht_new_keys);
	free(ht_new_flags);
	(success) = false;
	break;
}

К сожалению, нам нужно содержимое всех старых структур и именно в том порядке, в котором они в них находятся, поэтому мы не можем так просто использовать realloc для оптимизации выделения памяти. Существует алгоритм, который позволяет выделять с нуля память только для флагов, а ключи и значения расширить с помощью realloc, но я не буду его реализовывать в данной статье, поэтому что она и так вышла весьма длинной, а выигрыш от данной оптимизации проявляет себя далеко не всегда (realloc не гарантирует возможность обойтись без перевыделения памяти, а зависит от текущей фрагментации кучи, в C++ стандартные контейнеры в принципе лишены возможности его использовать, так как они используют только new и delete).

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

Наконец, память выделена и больше ничего не может пойти не так. Очищаем новые флаги (новая хеш-таблица пока пуста) и выполняем перехеширование:

memset(ht_new_flags, 0, ht_new_capacity);
size_t ht_mask = ht_new_capacity - 1;
for (size_t ht_i = 0; ht_i < (h).capacity; ht_i++) {
	if ((h).flags[ht_i] != 1) continue;
	size_t ht_j = hash_func((h).keys[ht_i]) & ht_mask;
	size_t ht_step = 0;
	while (ht_new_flags[ht_j]) {
		ht_j = (ht_j + ++ht_step) & ht_mask;
	}
	ht_new_flags[ht_j] = 1;
	ht_new_keys[ht_j] = (h).keys[ht_i];
	ht_new_values[ht_j] = (h).values[ht_i];
}

Если вы хорошо поняли алгоритм вставки, то этот алгоритм должен быть достаточно просто для понимания.

Мы итерируемся по всем элементам хеш-таблицы пропуская свободные и удалённые:

for (size_t ht_i = 0; ht_i < (h).capacity; ht_i++) {
	if ((h).flags[ht_i] != 1) continue;
	...
}

Затем для каждого элемента мы вычисляем хеш и ищем ему место в новой таблице:

size_t ht_j = hash_func((h).keys[ht_i]) & ht_mask;
size_t ht_step = 0;
while (ht_new_flags[ht_j]) {
	ht_j = (ht_j + ++ht_step) & ht_mask;
}

Поскольку в новой таблице пока не может быть удалённых элементов (флаг равен 2), мы можем просто проверять состояние элемента на отличность от нуля, а не сравнивать его с единицей.

Очень важно, что мы используем одинаковый алгоритм инкрементирования индекса в случае коллизии во всех трёх функциях ht_get, ht_put и ht_reserve.

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

ht_new_flags[ht_j] = 1;
ht_new_keys[ht_j] = (h).keys[ht_i];
ht_new_values[ht_j] = (h).values[ht_i];

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

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

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

free((h).values);
free((h).keys);
free((h).flags);
(h).flags = ht_new_flags;
(h).keys = ht_new_keys;
(h).values = ht_new_values;
(h).capacity = ht_new_capacity;
(h).max_size = (ht_new_capacity >> 1) + (ht_new_capacity >> 2);
(success) = true;

В качестве нового максимального размера мы используем примерно 75 процентов от новой ёмкости:

(h).max_size = (ht_new_capacity >> 1) + (ht_new_capacity >> 2);

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

/** Round up a 8-bit integer variable `x` to a nearest power of 2  */
#define roundup8(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, ++(x))

/** Round up a 16-bit integer variable `x` to a nearest power of 2  */
#define roundup16(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, ++(x))

/** Round up a 32-bit integer variable `x` to a nearest power of 2  */
#define roundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))

/** Round up a 64-bit integer variable `x` to a nearest power of 2  */
#define roundup64(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, (x)|=(x)>>32, ++(x))

#if SIZE_MAX == UINT64_MAX
/** Round up a size_t variable `x` to a nearest power of 2  */
#define roundupsize(x) roundup64(x)
#elif SIZE_MAX == UINT32_MAX
/** Round up a size_t variable `x` to a nearest power of 2  */
#define roundupsize(x) roundup32(x)
#elif SIZE_MAX == UINT16_MAX
/** Round up a size_t variable `x` to a nearest power of 2  */
#define roundupsize(x) roundup16(x)
#elif SIZE_MAX == UINT8_MAX
/** Round up a size_t variable `x` to a nearest power of 2  */
#define roundupsize(x) roundup8(x)
#endif

Кажется, мы забыли реализовать последнюю обязательную операцию - удаление элемента.

Оно реализуется на удивление просто:

#define ht_delete(h, index) do { \
	(h).flags[(index)] = 2; \
	(h).size--; \
} while (0)

Просто переводим элемент в состояние "удалено" и уменьшаем счётчик количества элементов.

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

Реализуем последнюю операцию - перебор элементов.

У нас уже есть пример как это делать из функции ht_reserve:

for (size_t ht_i = 0; ht_i < (h).capacity; ht_i++) {
	if ((h).flags[ht_i] != 1) continue;
	...
}

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

#define ht_begin(h) (0)
#define ht_end(h) ((h).capacity)

Теперь пользователь может обойти все элементы хеш-таблицы как-то так:

for (size_t i = ht_begin(my_hash_table); i != ht_end(my_hash_table); i++) {
    if (!ht_valid(my_hash_table, i)) continue;
    // Делаем что-то с элементом используя ht_key и ht_value для доступа.
}

Кстати, во время такого цикла обхода элементов совершенно безопасно вызывать ht_delete для текущего элемента (и на самом деле для любого другого), что позволяет реализовать удаление элементов хеш-таблицы по заданному критерию. А вот ht_put вызывать не очень хорошая идея, потому что любая вставка может вызвать перехеширование, а перехеширование нарушит порядок итерации (мы не выйдем за границу массива, потому что его размер может только увеличиваться, но можем посетить некоторые элементы дважды, а некоторые не посетить ни разу, явно не то что ожидаешь от цикла for each). Аналогично, после ht_put нельзя использовать все предыдущие индексы полученные с помощью ht_get и ht_put, потому что они могут начать указывать совсем в другое место (в том числе на несуществующий или удалённый элемент).

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

Самый очевидный вариант:

#define ht_for_each(ht, index, code) \
for (size_t index = ht_begin((ht)); index != ht_end((ht)); index++) { \
    if (!ht_valid((ht), index)) continue; \
    code; \
}

Имеет недостатки. Дело в том, что препроцессор C разбирает выражения совсем не так как это делает сам компилятор. Если в code встретиться запятая, он посчитает всё, что идёт после неё как дополнительные параметры макроса (потому что он понятия не имеет о смысле фигурных скобок, только о смысле круглых), что будет не очень хорошо. Технически проблему можно обойти используя __VA_ARGS__, но всё равно операторные скобки внутри аргументов макроса выглядят чужеродно, к тому же ломают автоматическое форматирование кода в некоторых средах и утилитах. Нужно более элегантное решение. Что-то вроде такого:

#define ht_for_each(ht, index) \
for (size_t index = ht_begin((ht)); index != ht_end((ht)); index++)

Тогда можно будет использовать этот макрос как-то так:

ht_for_each(my_hash_table, i) {
    // Делаем что-то с i-ым элементом с использованием ht_key, ht_value и ht_delete
}

Красиво, неправда ли? Практически как родной цикл foreach из языков, где он поддерживается.

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

Хорошая новость в том, что алгоритм поиска следующего индекса вообще никак не зависит от типов ключей и значений, а также функций хеширования и сравнения, а значит не обязан быть макросом (хотя сам цикл for each обязан, потому что должен принимать разные типы структуры хеш-таблицы):

static inline size_t ht_next_valid_index(const char *flags, size_t capacity, size_t index) {
	while (index < capacity && flags[index] != 1) {
		index++;
	}
	return index;
}

#define ht_for_each(h, index) for ( \
	size_t index = ht_next_valid_index((h).flags, (h).capacity, ht_begin((h))); \
	index != ht_end((h)) && ht_valid((h), index); \
	index++, index = ht_next_valid_index((h).flags, (h).capacity, index) \
)

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

Функция описана как static, так что не будет ошибкой линковки то, что она будет объявлена в каждой единице трансляции, которая включает наш заголовочный файл. Также она очень маленькая и почти наверняка будет заинлайнена компилятором при оптимизации, ну а для большей убедительности мы добавили модификатор inline (который, впрочем, современными компиляторами считается рекомендацией, а не обязанностью).

Теперь мы можем красиво итерироваться по всем элементам:

ht_for_each(my_hash_table, i) {
    printf("%s=%i\n", ht_key(my_hash_table, i), ht_value(my_hash_table, i));
}

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

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

Примеры хеш-функции

Чтобы хеш-таблицей можно было пользоваться, необходимо реализовать hash_func и eq_func. Для полноты материала привожу примеры хеш-функций для чисел и строк:

#define ht_int_hash(x) ((size_t) (x))
#define ht_int_eq(a, b) ((a) == (b))

static inline size_t ht_str_hash(const char *s) {
	size_t h = (size_t) *s;
	if (h) {
		for(++s; *s; ++s) {
			h = (h << 5) - h + (size_t) *s;
		}
	}
	return h;
}
#define ht_str_eq(a, b) (strcmp((a), (b)) == 0)

Хеш-функция для чисел является простым приведением числа к size_t. Это может не очень хорошо работать на некоторых типах данных (например, в нашем случае, если вы захотите хранить в хеш-таблице исключительно степени двойки, то будет много коллизий), но, кстати, Java использует такой же подход для реализации метода hashCode для Integer.

Тесты производительности

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

Для сравнения будем использовать алгоритм построения икосферы с использованием последовательных подразделений меша (будем использовать 4 итерации подразделения). Сравнивать будем с реализациями на C++ и Rust. Можно было бы использовать std::unordered_map в C++ и получить выигрыш моей реализации в несколько раз, но это не мой путь, поэтому все реализации достаточно сильно оптимизированы (а сам алгоритм генерации переписан между языками практически дословно).

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

• Версия для C++. Использует absl::flat_hash_map из библиотеки Abseil, которая реализует quadratic probing. Бенчмарк использует хеш-функцию аналогичную той, которая используется реализацией на C.

• Версия для Rust. Использует AHashMap из одноимённого пакета (стандартный HashMap тоже неплох, но в нём присутствуют дополнительные защиты от атаки Denial of service через умышленный вызов большого количества коллизиций хешей, однако эта защита не нужна для ситуации, когда мы контролируем генерируемые данные, а не получаем их извне). Реализует quadratic probing.

• Хеш-таблица из этой статьи.

Все алгоритмы используют методы reserve соответствующих контейнеров, чтобы избежать перевыделений памяти в процессе. Каждый алгоритм вызывается 10 тысяч раз, измеряется общее время выполнения и делится на количество итераций (так как одиночное выполнение алгоритма занимает сабмиллисекундное время и при замере одной итерации была бы слишком большая погрешность). Между итерациями все используемые структуры данных уничтожаются и создаются заново (таким образом симулируются реальные условия, когда ты посчитать размеры контейнеров и сделать reserve заранее можешь, но инициализировать контейнеры всё равно придётся).

Все проекты собирались со стандартными опциями релизной сборки (CMAKE_BUILD_TYPE=Release для C/C++, cargo build --release для Rust).

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

Результаты (время одной итерации алгоритма):

Как можно заметить, реализация на C скомпилированная любым компилятором выигрывает результаты на C++ и Rust скомпилированные любыми компиляторами. При этом лучшее время для C в полтора раза меньше лучшего времени для Rust и С++.

Также интересным наблюдением является то, что компилятор от Microsoft ощутимо хуже оптимизирует C++ код, чем C, чем остальные компиляторы (разница более чем в 2 раза, в то время как у MinGW и Clang отрыв меньше).

Заключение

Разработанная структура данных имеет потенциал для следующих улучшений:

• Использование realloc для keys и values в функции kh_reserve.

• Использование битовый карты вместо массива char для хранения состояний элементов (уменьшит оверхед по памяти, но не гарантирует улучшение быстродействия).

• Реализовать возможность хранения только ключей, без значений (достаточно тривиальным образом убрать код выделения памяти для значений и копирования значений), чтобы получился HashSet вместо HashMap. Непонятно как сохранить лаконичный интерфейс макросов.

• Реализовать хранение ключений вместе со значениями вместо хранения в раздельных массивах. Позволит уменьшить на треть число аллокаций, а также улучшит cache locality для пользовательского кода (который скорее всего одинаково часто обращается и к ключам, и к значениям), однако немного уменьшит cache locality для kh_get и kh_put (так как они не обращаются к значениям, только к ключам и флагам).

Также следует отметить, что макросы kh_reserve, kh_get, kh_put содержат достаточно много кода, поэтому их повсеместное использование над одним и тем же типом контерйнера приведёт к распуханию кода приложения (что в свою очередь не очень хорошо для кеша процессора). Если алгоритм требует вызова этих функций больше 1-2 раз на одной и той же структуре данных, имеет смысл обернуть вызов этих макросов в функцию.

Выигрыш по производительности по сравнению с C++ и Rust, вероятно, вызван следующими факторами:

• Принудительный инлайнинг кода из-за применения макросов.

• Отсутствие в С деструкторов, а также конструкторов перемещения и копирования (конечно, в бенчмарке все значения тривиально копируемые и удаляемые, но, возможно, в компиляторе или самих структурах данных отсутствуют какие-то оптимизации из-за того, что нужна поддержка вызова конструкторов копирования и деструкторов).

Библиотека

Рассмотренная в статье структура данных была мною опубликована в составе библиотеки https://github.com/KivApple/CEssentials. Также в этой библиотеке присутствует обобщённая реализация вектора (динамического массива) и динамические строки совместимые с обычными нуль-терминизированными сишными строками, а также набор строковых утилит недостающих в стандартной библиотеке. Библиотека распространяется под лицензией MIT и не имеет внешних зависимостей, может быть подключена к проекту путём простого копирования файлов, однако имеется CMakeLists.txt для удобства подключения к существующему CMake-проекты через add_subdirectory.

При разработке хеш-таблицы я опирался на аналогичную реализацию из Klib (в репозитории висят Issue и Pull Request уже более двух лет, очень скудная документация, специфический интерфейс макросов). Идея реализации динамических строк совместимых с сишными была взята из библиотеки SDS.

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