Почему хэш-карты лучше, чем три-карты?

Question

Под Trie Map я подразумеваю ассоциативный массив, где полезные данные хранятся в Trie вместо хеш-таблицы.

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

Мне кажется, что при кодировании небольших объектов это будет использовать намного больше памяти (даже если вы разрешаете вводить только буквенные символы в нижнем регистре в ключах, это 26 указателей на узел и часто несколько узлов на ключ),но с другой стороны, вам никогда не придется беспокоиться об изменении размера.Почему хеш-карты так распространены, но я никогда не видел три-карту?

Answer 1

На тот случай, если вы являетесь программистом Scala, TrieMap является «параллельной поточно-ориентированной реализацией без блокировки блокировки дерева, отображенного в хеш-массиве». На данный момент в стандартной библиотеке Java нет ни одной.

Answer 2

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

(Строго говоря, каждый объект представляет собой последовательность битов, но тогда общая задача потребует от пользователя сериализации своего объекта до того, какхранить его в памяти. Это довольно неудобно по сравнению с определением пользовательских хеш-функций.)