Benchmark

This benchmark compares the memory usage and the performance of the trie when storing n entries in the trie then trimming the trie/optimizing it for read-only operations, an then performing a lookup of every key in an order which is different from the insertion order. Times are given in milliseconds and memory usage is given in bytes.

All implementations are instantiated with the default constructor.

The CompositeTrie implementation uses a FastArrayTrie for the first 2 levels and CompactArrayTries then.

The BloomFilteredTrie implementation wraps a CompactArrayTrie and uses the same hashing function as Strings with a bloom filter of 1024*64 bits.

Since keys are looked-up as Strings, HashMap is given an advantage because the hash is pre-computed, but the hash computation is very fast, so HashMap would still be faster if it had to compute the hash every time. If you want to have an idea of how slower HashMap would be without caching the hash code, you can look at the difference in time between CompactArrayTrie and BloomFilteredTrie given that a lookup costs the same plus one hash computation and one BitSet lookup.

English dictionary

This test has been done on the aspell dictionary for the english language (generated with aspell -l en dump master | aspell expand | sort | uniq then randomized) which contains 138349 words.

	Insertion time	Trimming/read optimization time	Read time	Size in memory after insertion	Size in memory after trimming/optimization
HashMap	33	0	54	8590936	8590936
TreeMap	231	0	242	9961192	9961192
CompactArrayTrie	129	180	81	7297072	4365696
BloomFilteredTrie	142	185	90	7319728	4388352
FastArrayTrie	174	397	126	23628576	16583784
CompositeTrie	95	89	71	9145248	4544416
CompactArrayRadixTrie	247	218	117	8143592	2876896

As you can see, the best trie implementations (CompositeTrie and CompactArrayTrie) are not far from being as fast as a HashMap. Regarding memory, except FastArrayTrieMap, Trie implementations are 2 to 3 times as memory efficient as HashMap.