Какой быстрый и эффективный способ найти предмет?

Question

Привет, поэтому мне нужен БЫСТРЫЙ способ поиска слова в словаре.

Словарь содержит около 500 тыс. Слов.

Я подумываю об использовании хэш-карты, где каждая ячейка содержит не более 1 слова.

Идеи о том, как это сделать или есть что-то лучше?

Answer 1

A Trie - это эффективный способ хранения словарей, имеющий очень быстрый поиск, O (m), где m - длина слова.

Хеш-карта будет менее эффективной с точки зрения памяти, но время поиска - это постоянная величина для идеального хэша, O (1), но вы все равно тратите O (m) на вычисление хэша. Несовершенный хеш будет иметь худший худший случай, чем Trie.