хэш-таблица c ++, где ключи - это строки, а значения - векторы строк

Question

У меня есть большая коллекция уникальных струн (около 500к).Каждая строка связана с вектором строк.В настоящее время я храню эти данные в

map<string, vector<string> >

, и они работают нормально.Однако я хотел бы, чтобы поиск в карте был быстрее, чем log (n).При таких ограниченных обстоятельствах, как я могу создать хеш-таблицу, которая поддерживает поиск O (1)?Похоже, это должно быть возможно, так как я знаю все ключи заранее ... и все ключи уникальны (поэтому мне не приходится учитывать коллизии).

Приветствия!

Answer 1

Вы можете создать хеш-таблицу с boost::unordered_map, std::tr1::unordered_map или (на компиляторах C ++ 0x) std::unordered_map.Это требует почти нулевого усилия. Google sparsehash может быть еще быстрее и имеет тенденцию занимать меньше памяти.(Удаление может быть проблемой, но, похоже, вам это не понадобится.)

Если код все еще недостаточно быстр, вы можете использовать предварительные знания о ключах с минимальным идеальным хэшем, как предлагаетдругие, чтобы получить гарантированную производительность O (1).Стоит ли усилий по генерированию кода, это зависит от вас;помещение 500k ключей в такой инструмент, как gperf, может потребовать генератора генератора кода.

Вы также можете посмотреть на CMPH , который генерирует идеальную хеш-функцию во время выполнения, хотячерез C API.

Answer 2

Если вы не хотите столкновений для известной коллекции ключей, вы ищете perfect hash . Библиотека CMPH (мои извинения за C, а не C ++) является зрелой и может генерировать минимальные совершенные хэши для довольно больших наборов данных.

Answer 3

То, что вы ищете, это Perfect Hash . gperf часто используется для их генерации, но я не знаю, насколько хорошо он работает с таким большим набором строк.

Answer 4

Я бы хотел создать Perfect Hash Function для вашего стола.Это гарантирует отсутствие коллизий, которые являются дорогостоящей операцией для разрешения. Совершенные генераторы хеш-функции также доступны.