VietMX Staff asked 3 years ago
A hash table can look up individual strings very quickly. It’s like a thoroughbred racehorse. That’s all it can do. A trie, on the other hand, is a workhorse that can do a lot of things. It’ll never be as fast at lookups as a hash table, but it can do lots of things that the hash table can’t do.
For example, finding all the words in a hash table that start with “pre” will take O(n) time because you have to search all of the words. With a trie, it takes three probes to find the subtree that contains all of those words, and then all you have to do is traverse that subtree. Sure, the worst case is O(n), but that’s only if all the words in your trie start with “pre”.
