Advantages of tries:
The basics:
- Predictable O(k) lookup time where k is the size of the key
- Lookup can take less than k time if it's not there
- Supports ordered traversal
- No need for a hash function
- Deletion is straightforward
New operations:
- You can quickly look up prefixes of keys, enumerate all entries with a given prefix, etc.
Advantages of linked structure:
- If there are many common prefixes, the space they require is shared.
- Immutable tries can share structure. Instead of updating a trie in place, you can build a new one that's different only along one branch, elsewhere pointing into the old trie. This can be useful for concurrency, multiple simultaneous versions of a table, etc.
- An immutable trie is compressible. That is, it can share structure on the suffixes as well, by hash-consing.
Advantages of hashtables:
- Everyone knows hashtables, right? Your system will already have a nice well-optimized implementation, faster than tries for most purposes.
- Your keys need not have any special structure.
- More space-efficient than the obvious linked trie structure
Read full article from algorithm - How Do I Choose Between a Hash Table and a Trie (Prefix Tree)? - Stack Overflow
