Как выбрать между хэш-таблицей и Trie (префиксное дерево)?

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

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

создание огромных хэш-таблиц для эффективного поиска не является элегантным решением в большинстве промышленных сценариев, где даже небольшая задержка/масштабируемость имеет значение (например, высокочастотная торговля). Вы должны заботиться о структурах данных, которые будут оптимизированы для пространства, которое он занимает в памяти, чтобы уменьшить промах кэша.

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

использовать дерево:

1. Если вам нужна функция автозаполнения
2. найти все слова, начинающиеся с " А " или "топор" и так далее.
3. суффиксное дерево-это особая форма дерева. Суффиксные деревья имеют целый список преимуществ, которые хэш не может покрыть.

есть что-то, что я не видел, чтобы кто-то упоминал явно, что я думаю, важно иметь в виду. Как хэш-таблицы, так и попытки различных типов обычно имеют O(k) операции, где k длина строки в битах (или эквивалентно в chars).

это предполагает, что у вас есть хорошая хэш-функция. Если вы не хотите "ферма" и "Ферма животных" с хэш-то же значение, то хэш-функция должна использовать все биты ключа, а так хэширования "сельскохозяйственные животные "должны занимать примерно в два раза больше времени, чем" ферма " (если вы не находитесь в каком-то скользящем сценарии хэша, но есть несколько похожих сценариев экономии операций с попытками тоже). И с ванильной попыткой понятно, почему вставка " сельскохозяйственных животных "займет примерно в два раза больше времени, чем просто"ферма". В долгосрочной перспективе это верно и для сжатых попыток.

HashTable реализация пространства эффективна по сравнению с basic Trie реализация. Но со строками порядок необходим в большинстве практических приложений. Но HashTable полностью нарушает лексический порядок. Теперь, если ваше приложение выполняет операции на основе лексического порядка (например, частичный поиск, все строки с заданным префиксом, все слова в отсортированном порядке), вы должны использовать попытки. Для только поиска, HashTable должен использоваться (как возможно, это дает минимальное время поиска).

П. С.: помимо этого, Троичные Деревья Поиска (TSTs) было бы отличным выбором. Его время поиска больше, чем HashTable, но эффективно по времени во всех других операциях. Кроме того, его более эффективное пространство, чем пытается.

вставка и поиск на trie линейны с длиной входной строки O (s).

хэш даст вам O(1) для вставки поиска ans, но сначала вы должны вычислить хэш на основе входной строки, которая снова является O (s).

сотрясение, асимптотическая временная сложность линейна в обоих случаях.

У trie есть еще некоторые накладные расходы с точки зрения данных, но вы можете выбрать сжатый trie, который снова поставит вас, более или менее на связь с хэш-таблица.

чтобы разорвать связь задайте себе этот вопрос: мне нужно искать только полные слова? Или мне нужно вернуть все слова, соответствующие префиксу? (Как в системе предиктивного ввода текста). Для первого случая, пойти на хэш. Это более простой и чистый код. Более легкий для того чтобы испытать и поддержать. Для более эллаборированного случая использования, когда префиксы или суфиксы имеют значение, перейдите к trie.

и если вы делаете это просто для удовольствия, реализация trie поставит воскресный день на хороший использовать.

некоторые (обычно встроенные, в режиме реального времени) приложения требуют, чтобы время обработки не зависело от данных. В этом случае хэш-таблица может гарантировать известное время выполнения, в то время как trie зависит от данных.