Lookup in a trie is O(L) where L is the length of the key; not that different if you take into account that to lookup into a hashtable, you also have to compute

Lookup in a trie is O(L) where L is the length of the key; not that different if you take into account that to lookup into a hashtable, you also have to compute the hash of the key.