Trie vs Hashtable data structure

+2 votes
asked Jun 7, 2010 by Seb (2,267 points)
Is it practically possible (ie. proven with benchmarks) for an implementation of a patricia trie (or trie otherwise) to be as optimal/efficient at data retrieval as an implementation of a hashtable?

2 Answers

0 votes
answered Jun 7, 2010 by Harro (216 points)
i would not know if they have proven it with benchmark testing yet
commented Jun 7, 2010 by Seb (2,267 points)
This doesn't form an answer to my question. I'm aware that theoretically, a trie can be just as optimal as a hashtable in data retrieval and even more optimal in data insertion. I'd very much like to know if this has been achieved in practice.
0 votes
answered Jun 7, 2010 by strager (656 points)
Yes, because you can make any implementation of anything as slow as you'd like.  You can make a quick sort as slow as a bubble sort, for example.

Looking at algorithmic complexity, the only source I could find is Wikipedia which states:

> [A radix trie] supports the following main operations, all of which are O(k), where k is the maximum length of all strings in the set:
> Lookup: ...
> Insert: ...
> Delete: ...
> Find predecessor: ...
> Find successor: ...

You can think of O(k) as O(log N) if the tree is balanced.  Space complexity is at most O(N * k), because obviously every key needs to be stored once.  However, I am suspecting the space complexity hovers more toward O(k * log N) because of the string "joining" effect the radix trie depends upon.

Hash table implementations vary too widely to have specific algorithmic complexities.  However, in general, lookups are O(1 + k), where *k* is the number of elements in the bucket.  A hash table's space complexity is O(N * k) (*k* = 1 if the key isn't stored) plus some constant for storing the buckets.

If you have a balanced radix trie, and and imbalanced hash table, it is likely the trie (O(log N)) will perform better than the hash table (O(N)).  However, in the general case, with a good radix trie implementation and a good hash table implementation, the hash table will win.

A clear advantage of a radix trie is that a hash function is not required, and the keys do not need to be duplicated.  This may affect performance behaviour, especially with frequent string lookups and key-inspecting iterations and inserts.
commented Jun 7, 2010 by Seb (2,267 points)
There are a few good points here, thankyou. I still feel as though the question I meant to ask has not been answered, however you've enlightened me regarding the downfall of the question that came out. Thanks. I'll give it some thought, modify my question later and bump this question when I've done so.
Welcome to Q&A, where you can ask questions and receive answers from other members of the community.