Карта хеша оптимизирована для поиска

Question

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

Обновление:

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

Answer 1

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

Хотя, конечно, std::unordered_map, как в C ++ 11, тоже может быть, хотя, возможно, с несколькими коллизиями.

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

(Заметьте, кстати, что O (log (N)) вполне может быть быстрее, чем O (1) в таком случае, потому что big-O не считает такие вещи.)

Answer 2

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

---

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

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

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

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

Answer 3

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

Answer 4

Попробуйте google-sparsehash: http://code.google.com/p/google-sparsehash/

An extremely memory-efficient hash_map implementation. 2 bits/entry overhead! 
The SparseHash library contains several hash-map implementations, including 
implementations that optimize for space or speed.