hash map с заранее известным множеством ключей.

Это нужно сделать в рантайме или можно на этапе компиляции / сборки пакета сделать?

Так не подойдет?

std::map<int, int> testMap {{1,1}, {2,2}};
std::unordered_map<std::string, int> testMap2{{«1», 1}, {«2», 2}};

gperf?

придумать не удалось, нагуглить тоже

Perfect hash function?

множество возможных ключей известно заранее, количество естественно тоже

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

Ключи все известны на этапе компиляции. Значения, связанные с ними, на этапе компиляции не известны

Проблема похожа, стоит разобраться

Используй struct. /thread

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

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

Ключи все известны на этапе компиляции. Значения, связанные с ними, на этапе компиляции не известны

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

Ключи все известны на этапе компиляции. Значения, связанные с ними, на этапе компиляции не известны

Да, деталей не хватает, но пока выглядит как обыкновенный массив. А ключи - имена констант, за которыми кроются индексы массива. Или constexpr функция по трансформации ключа в индекс массива (кстати, по идее не очень оптимально). Но это при условии, что эти ключи не приходят откуда-то извне, если массив заполнен изначально + и уйма других assumption'ов.
Вобщем, примерь эту идею: подходит ли?

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

Тебе не нужен хэш, тебе нужно построить конечный автомат. Он не только будет быстрее и проще, он сможет вернуть результат даже не читая весь ключ. Например, на множестве ключей { «a», «b» } он сможет сказать что ключа «cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc» в мапе нет прочитав всего один байт.

Если бы были еще известны вероятности запроса по заданным ключам, то можно было бы оптимизировать. Забыл детали, но что-то по типу кода Хаффмана

Как вариант - подобрать идеальную или близкую к идеальной хеш-функцию. Без коллизий и с минимальным диапазоном.

Хотя фиг знает, будет ли быстрее, чем просто сбалансированное двоичное дерево или хештаблица

Это и будет автомат.

То есть фактически нужно быстро матчить строки и получать их идентификатор? Тогда берите какой-нибудь лексический анализатор.

re2c ( http://re2c.org ) генерирует довольно быстрый direct code. С большой вероятностью это будет быстрее вычисления хэша

Для упрощения работы можно вместо gperf заюзать re2c, он строго говоря не идеальные хэши создает, но близкие к этому. Для re2c не нужен отдельный входной файл, директивы пишутся внутри комментариев в С или С++ коде, что упрощает интеграцию. Особенно удобно если это хэш будет использовать при парсинге, тогда на re2c можно сделать лексер, выделяющий клбчевые слова из потока и выполняющий на них определенные действия

У gperf тоже вполне себе direct code

Для генерации автомата лучше взять ragel.

gperf - если ключей меньше 10^3 (gperf долго генерит исходник), иначе - bsearch из glibc.

gperf?

Кстати, может знаешь как в секции декларации вставить значение с пробелом? Т.е.

%define initializer-suffix , INVALID_INDEX

Ибо в таком виде валится с ругательствами:

hasher.gperf:22: junk after declaration

Не сталкивался.

Можно сделать двоичный поиск в массиве структур вида {ключ, значение}, отсортированных по ключам, а потом получить значение, соответствующее этому ключу. Типа:

{{"aaa", "val1"}, {"aab", "val2"}, {"aac", "val3"}}

«aaa» «aab» «aac» это ключи, двоичным поиском за логарифмическое время можно найти структуру с нужным ключом и из нее извлечь значение