HashMap vs TrieMap

Developers
1

Provided you were fine using a non-stable object type, when would you use a HashMap vs a TrieMap?

I’m guessing they’re both roughly equally performant (constant vs log?)… It doesn’t seem like the keys in a TrieMap are sorted like they would be in a Java BST-based TreeMap either, so I’m not quite sure what’s the use case of a TrieMap over a HashMap.

2

I assume that TrieMap is a type of prefix trie, in which case it’s probably better suited to things like autocomplete where all the possible results have the same prefix.

3

That’s what I initially thought, but I believe it’s a hash trie, where the hashes of the keys (not the keys themselves) are stored in a trie.

I don’t think most devs need autocomplete on the hashes…

4

Again, not sure if it’s the same data structure, but Wikipedia has a section here comparing the pros and cons of tries with hash tables: Trie - Wikipedia

5

Interesting observation about the differences between the two by @PaulLiu:

As an aside, I’d recommend using TrieMap instead of HashMap because the latter has an unpredictable insertion cost: it may exceed the per-call cycle limit when a table has to be rehashed!

2 Likes