Специализированные алгоритмы хеширования для динамических / статических / инкрементальных данных

Question

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

Теперь данные на самом деле представляют собой 3 несколько разных типа наборов данных:

1. Некоторые наборы могут быть изменены (ключи добавлены, удалены, заменены и т. Д.) По желанию
2. Для некоторых наборов данные могут быть добавлены, но почти никогда не заменены / удалены (то есть это может случиться, но на практике это очень редко)
3. Для некоторых наборов данные добавляются один раз, а затем только просматриваются, они никогда не изменяются после загрузки всего набора.

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

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

Answer 1

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

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

Для случая «набор данных никогда не меняется», вам следует обратиться к идеальным генераторам хешей. Если вы знаете ваши ключи во время компиляции, у меня были хорошие результаты с gperf . Если ваши ключи недоступны до времени выполнения, попробуйте C Minimal Perfect Hash Library .

Answer 2

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

Очевидно, что ключевые тела должны быть в последовательной памяти или их хешах. Но если вы сможете получить это в одну или две строки L1 cache.lines, они полетят.

Что касается больших хэшей, прямая цепочка может потерять открытую адресацию?

Вы можете исследовать хеш-таблицы и попытки " сознающие кеш ".

В статье wikipedia подробно рассматриваются строки кэша, описывающие различные компромиссы.