VietMX Staff asked 3 years ago
Tries and hash tables are used for different things:
- If all you want is the ability to lookup a word, then a hash table will be faster. A well constructed hash table (i.e. a good hash function and a reasonable load factor) has
O(1)lookup time. - If you want to find common prefixes, ordered retrieval, or do similar things, then you want a trie. Lookup time in a trie is
O(m): it depends on the length of the string you’re looking up.
And memory wise:
- A hash table’s overhead is typically a constant multiple of the number of words it contains. That is, in addition to the memory required to store the strings, there is per-string overhead to store the mapping between hash code and string.
- Memory for a trie is a little more involved. In the worst case, there is one node per character. All those little node allocations start adding up. Imagine a dictionary that contains 200,000 words, and the average word length is five characters. That’s a million nodes of overhead.
