How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?

Solution 1:

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 (see comments below)

Solution 2:

It all depends on what problem you're trying to solve. If all you need to do is insertions and lookups, go with a hash table. If you need to solve more complex problems such as prefix-related queries, then a trie might be the better solution.