Co to jest TrieMap i jakie są jego zalety/wady w porównaniu z HashMap?

Question

Scala ma kolekcję TrieMap.

Co to jest TrieMap i jakie są jego zalety/wady w porównaniu z HashMap?

Answer 1

Scala TrieMap jest opartą na trocie implementacją skalowalnej mapy . W przeciwieństwie do normalnych map Trie, Scala TrieMap ma wydajną, nie blokującą operację O (1) czasową snapshot (i nieco zoptymalizowaną).

Absolutna wydajność z TrieMap jest nieco poniżej JDK8 ConcurrentHashMap, ale zaletą jest to, że zapewnia spójnych iteratory coś, co współbieżnych struktur danych zazwyczaj nie mają. Oznacza to, że możesz przechwycić wszystkie elementy w trie w jednym momencie (numery wydajności i analiza here). Powinieneś użyć TrieMap, jeśli chcesz uchwycić wszystkie elementy naraz (np. Aby wyświetlić wszystkie elementy w interfejsie lub konsekwentnie je analizować).

Answer 2

TrieMaps to Mapy wykorzystujące strukturę danych Trie, które są w zasadzie płytkimi drzewami. Na przykład, jeśli masz 32-bitowy skrót, podziel go na sekcje, na przykład 4 razy 8 i na każdym poziomie drzewa, które rozgałęzisz, aż do 256 pod drzew. Oczywiście daje to wydajność O (1) ze względu na rozmiar skrótu (przyjmując kilka kolizji).

Strukturę trie można sprawić, że jest niezmienna, ponownie wykorzystując strukturę trieta, aby utworzyć nowy trie z dodanym lub usuniętym elementem. Względna wydajność w czasie/pamięci wpływa na GC zależy w dużej mierze od wdrożenia i obciążenia, a więc spróbuj ogólną odpowiedź Powiedziałbym, uruchomić test porównawczy. Chociaż w przypadku pojedynczego wątku bez wymogu niezmienności, klasyczna niedziała zwykle zapewnia lepszą średnią wydajność i gorszą wydajność w najgorszym przypadku.

Jako wzmiankę na marginesie wspomnę, ponieważ trieMap również używa skrótu, jest także hashmapem, więc poleciłabym wywołanie go jako trash backed hashmap vs hashmap z tablicą.