Хеш-таблица для поиска слов в большом тексте. O(1)

Question

Хеш-таблица для поиска слов в большом тексте. O(1)

Я должен создать хеш-таблицу со скоростью операции O(1) для большого текста (поиск, вставка, удаление). Это реально? Как минимизировать столкновения? Любой пример? Я никогда не использовал C++ позже. Я не могу найти пример хэш-таблицы со словарем для текста.
Целевой язык C++ (только STL).

-3

c++ algorithm dictionary hashtable hash-collision

Источник

user1560783 20 май '14 в 14:16

1 ответ

Решение

Другие вопросы по тегам c++ algorithm dictionary hashtable hash-collision

user812912 20 май '14 в 14:19 2014-05-20 14:19 · Accepted Answer · 2014-05-20 14:19

Вы можете использовать unordered_map или же unordered_set которые являются частью C++11 стандартный, или используйте версию этих контейнеров Boost, если C++11 это не вариант. Если вам нужно реализовать решение самостоятельно, я полагаю, что вы можете использовать реализацию в качестве справочного материала.

РЕДАКТИРОВАТЬ: как указатель на amit, он все еще не является константой, так как вам нужно хешировать строку, поэтому вам нужно пройти ее хотя бы один раз. Таким образом, сложность O(|S|) где S строка ищется Также ожидается сложностьO(|S|) независимо от того, насколько хороши могут возникнуть коллизии хеш-функций (и, за исключением очень редкого случая, когда можно использовать идеальный хеш, это произойдет с очень, очень высокой вероятностью из-за парадокса дня рождения).