Хеш-таблица для поиска слов в большом тексте. O (1)
Я должен создать хеш-таблицу со скоростью операции O (1) для большого текста (поиск, вставка, удаление).
Это реально? Как минимизировать столкновения? Любой пример? Я никогда не использовал C ++ позже. Я не могу найти пример хэш-таблицы со словарем для текста.
Целевой язык C ++ (только STL).
Решение
Вы можете использовать unordered_map или же unordered_set которые являются частью C++11 стандартный, или используйте версию этих контейнеров Boost, если C++11 это не вариант. Если вам нужно реализовать решение самостоятельно, я полагаю, что вы можете использовать реализацию в качестве справочного материала.
РЕДАКТИРОВАТЬ: как указатель на amit, он по-прежнему не является константой, так как вам нужно хэшировать строку, поэтому вам нужно пройти ее хотя бы один раз. Таким образом, сложность O(|S|) где S строка ищется Также сложность ожидаемый O(|S|) как бы ни были хороши коллизии хеш-функций (и за исключением очень редкого случая, когда можно использовать идеальный хеш будут с очень, очень высокой вероятностью из-за парадокса дня рождения).
Другие решения