Как создать эффективную статическую хэш-таблицу?

Question

Мне нужно создать из него статические хеш-таблицы малого и среднего размера. Как правило, у них будет 5-100 записей. Когда хеш-таблица создана, все хеши ключей известны заранее (т. Е. Ключи уже являются хешами). В настоящее время я создаю HashMap, то есть сортирую ключи, чтобы получить O (log n) поиск, который 3-5 поиски в среднем по размерам мне небезразличны. Википедия утверждает, что простая хеш-таблица с цепочкой приведет в среднем к 3 поискам для полной таблицы, так что это пока не стоит для меня (то есть принятие хеша% n в качестве первой записи и создание цепочки .) Учитывая, что я знаю все хэши заранее, похоже, что должен быть простой способ получить быстрый статический идеальный хеш - но я не смог найти хороший указатель как. То есть Амортизированный доступ O (1) без дополнительных затрат. Как мне реализовать такую ​​статическую таблицу?

Важно использовать память, поэтому чем меньше мне нужно хранить, тем лучше.

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

Answer 1

Для c или c ++ вы можете использовать gperf

GNU gperf - идеальный генератор хеш-функций.Для заданного списка строк он создает хеш-функцию и хеш-таблицу в форме кода на C или C ++ для поиска значения в зависимости от входной строки.Хеш-функция идеальна, это означает, что хеш-таблица не имеет коллизий, а для поиска в хеш-таблице требуется только сравнение одной строки.

GNU gperf легко настраивается.Существуют опции для генерации кода на C или C ++, для генерации операторов switch или вложенных ifs вместо хеш-таблицы, а также для настройки алгоритма, используемого gperf.

Answer 2

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

swich (hash_string(*p))
{
case HASH_S16("test"):
    ...
    break;
case HASH_S256("An example with a long text!!!!!!!!!!!!!!!!!"):
    ...
    break;
}

Найдите код @ http://www.heeden.nl/statichashc.htm

Answer 3

Вы можете использовать Sux4j для генерации минимального идеального хэша в Java или C ++.(Я не уверен, что вы используете Java, но вы упомянули HashMap, поэтому я предполагаю.) Для C вы можете использовать библиотеку cmph .