Ответ 1
Что более эффективно в отношении константы, очень зависимо. С одной стороны, trie предлагает строгую временную сложность O(N) для вставки всех элементов, тогда как хэш-таблица может упасть до квадрического времени в худшем случае.
С другой стороны, попытки не очень эффективны, когда дело доходит до cache - каждый поиск требует O(|S|) запросы памяти произвольного доступа, что может привести к значительному снижению производительности.
Оба подхода действительны, и я думаю, что есть несколько соображений, которые следует принимать при выборе одного над другим, как максимум latency ( если это система реального времени), пропускная способность и время для разработки.
Если важна средняя производительность приложения, я бы предложил создать кучу файлов и выполнить статистический анализ какой подход лучше. Wilcoxon подписанный тест - это фактическое фактическое фактическое испытание гипотезы при использовании.
Что касается встроенных систем: оба подхода по-прежнему актуальны, но здесь: Каждый "Node" (или куча узлов) в trie будет на диске, а не на RAM. Обратите внимание, что это означает, что для диска произвольного доступа trie O (| S |) ищет для каждой записи, что может быть медленным.
Для хэш-решений у вас есть 10 МБ, скажем, они могут использовать 5 МБ из них для хэш-таблицы указателей на диск. Предположим также, что вы можете хранить 500 различных дисковых адресов на этих 5 МБ (пессимистический анализ здесь), это означает, что у вас осталось 5 МБ для загрузки ковша после каждого хеша, и если у вас есть 500 ковшей с коэффициентом нагрузки 0,5, это означает вы можете хранить 500 * 5 МБ * 0,5 ~ = 1,25 ГБ > 1 ГБ данных, таким образом, используя решение хеш-таблицы, поэтому с использованием хэширования - каждому поиску потребуется только O(1) случайный диск ищет, чтобы найдите ведро, содержащее соответствующую строку.
Обратите внимание, что если этого еще недостаточно, мы можем перерисовать таблицы указателей, очень похожие на то, что делается в таблице подкачки в механизм виртуальной памяти.
Из этого можно заключить, что для встроенных систем хеш-решение лучше для большинства случаев (обратите внимание, что он может по-прежнему страдать высокой задержкой в худших случаях, здесь нет серебряной пули).
PS, дерево оснований обычно быстрее и компактнее, чем trie, но страдает от тех же побочных эффектов trie по сравнению с хэш-таблицами (хотя и менее значительными, конечно).