Реализация хеш-таблицы для C

Question

Что такое хорошая реализация хеш-таблицы для C?Мне нужно использовать его с компилятором mpicc.Функция удаления не требуется.

Answer 1

Один в glib очень хорош. Не уверен, что он слишком большой и / или его можно изолировать от остальной части glib.

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

Answer 2

Если все ключи известны заранее, вы можете использовать генератор perfect hash , чтобы избежать нехватки пространства, неявного в хеш-таблицах.

Если, с другой стороны, вам действительно нужен полный хэш-стол, я бы предложил вариант Cuckoo Hashing (например, d-ary версия).

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