Что такое TrieMap и каковы его преимущества/недостатки по сравнению с HashMap?

Ответ 1

A Scala TrieMap представляет собой реализацию масштабируемой карты параллельной на основе trie. В отличие от обычных trie-карт, Scala TrieMap имеет эффективную, неблокирующую операцию O (1) time snapshot (и немного оптимизированную операцию readOnlySnapshot).

Абсолютная производительность TrieMap немного ниже JDK8 ConcurrentHashMap, но преимущество заключается в том, что она обеспечивает согласованные итераторы, что обычно не существует в параллельных структурах данных. Это означает, что вы можете захватить все элементы в trie в один момент времени (номера производительности и анализ здесь). Вы должны использовать TrieMap, если вам нужно сразу удалить все элементы (например, чтобы просмотреть все его элементы в пользовательском интерфейсе или последовательно проанализировать их).

Ответ 2

TrieMaps - это Карты, использующие структуру данных trie, которые являются по существу мелкими деревьями. Например, если у вас есть 32-битный хеш, вы разбиваете его на разделы, например, 4 раза 8, и на каждом уровне дерева вы переходите к 256 под деревьям. Очевидно, что это дает O (1) производительность из-за фиксированного размера хеша (при условии нескольких столкновений).

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

В качестве побочной заметки, которую я упомянул, поскольку trieMap также использует хеш, это также hashmap, поэтому я бы рекомендовал называть его trie backed hashmap vs array backed hashmap.