Cos'è una TrieMap e quali sono i suoi vantaggi/svantaggi rispetto a una HashMap?

Question

Scala ha una collezione TrieMap.

Che cos'è un TrieMap e quali sono i suoi vantaggi/svantaggi rispetto a un HashMap?

Answer 1

A Scala TrieMap è un basato su trie implementazione mappa scalabile. A differenza delle normali mappe trie, Scala TrieMap ha un'operatività efficiente, non bloccante, con O (1) tempo snapshot (e un'operazione leggermente ottimizzata readOnlySnapshot).

prestazioni assoluta di una TrieMap è leggermente al di sotto della JDK8 ConcurrentHashMap, ma il vantaggio è che fornisce iteratori coerenti, qualcosa che le strutture di dati simultanei in genere non hanno. Ciò significa che è possibile acquisire tutti gli elementi nel trie in un determinato momento (numero di prestazioni e analisi here). Dovresti utilizzare lo TrieMap se è necessario acquisire tutti gli elementi contemporaneamente (ad esempio elencare tutti i suoi elementi nell'interfaccia utente o analizzarli in modo coerente).

Answer 2

TrieMaps sono mappe che utilizzano la struttura di dati che sono essenzialmente alberi poco profondi. Ad esempio, se si dispone di un hash a 32 bit lo si suddivide in sezioni, ad esempio 4 volte 8 ea ogni livello dell'albero si dirama fino a 256 sub-alberi. Ovviamente questo dà prestazioni O (1) a causa delle dimensioni fisse dell'hash (assumendo poche collisioni).

Una struttura trie può essere resa immutabile in modo efficace, riutilizzando la struttura di un trie per creare un nuovo trie con un elemento aggiunto o rimosso. Le prestazioni relative all'effetto memoria/tempo su GC dipendono molto dall'implementazione e dal caricamento, quindi piuttosto tentare una risposta generica, direi eseguire un benchmark. Sebbene per un singolo thread senza requisiti di immutabilità, una hashmap classica normalmente produrrà prestazioni medie migliori e prestazioni peggiori nel caso peggiore.

Come nota a margine, menzionerò poiché il trieMap usa anche un hash, è anche un hashmap, quindi mi raccomando di chiamarlo hashmap con backed di trie backed array.