LINUX.ORG.RU

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

 ,


1

4

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

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

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

anonymous ()
Ответ на: комментарий от ymuv

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

CatsCantFly ()

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

hippi90 ★★★★ ()
Ответ на: комментарий от CatsCantFly

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

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

andreyu ★★★★★ ()
Ответ на: комментарий от CatsCantFly

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

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

Kroz ★★★★★ ()
Ответ на: комментарий от Kroz

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

CatsCantFly ()

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

slovazap ★★★★★ ()

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

dave ★★★★★ ()

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

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

vmx ★★ ()

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

annulen ★★★★★ ()
Ответ на: комментарий от RazrFalcon

gperf?

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

%define initializer-suffix , INVALID_INDEX

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

hasher.gperf:22: junk after declaration

KennyMinigun ★★★★★ ()

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

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

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

SZT ★★★ ()