Все знают хеш-таблицу и ее использование, но это не совсем постоянное время поиска, это зависит от размера хеш-таблицы, сложности вычислений хеш-функции.
Создание огромных хеш-таблиц для эффективного поиска не является элегантным решением в большинстве промышленных сценариев, где важна даже небольшая задержка / масштабируемость (например, высокочастотная торговля). Вы должны позаботиться о том, чтобы структуры данных были оптимизированы под пространство, которое также занимает память, чтобы уменьшить потерю кэша.
Очень хорошим примером, когда Trie лучше соответствует требованиям, является промежуточное программное обеспечение для обмена сообщениями. У вас есть миллион подписчиков и издателей сообщений различных категорий (в терминах JMS - темы или обмены), в таких случаях, если вы хотите отфильтровать сообщения по темам (которые на самом деле являются строками), вам определенно не нужно создавать хеш-таблицу за миллион подписок с миллионами тем. Лучшим подходом является сохранение тем в три файла, поэтому, когда фильтрация выполняется на основе совпадения тем, ее сложность не зависит от количества тем / подписок / издателей (зависит только от длины строки). Мне это нравится, потому что вы можете проявить творческий подход к этой структуре данных, чтобы оптимизировать требования к пространству и, следовательно, снизить кэш-память.