Why is hash map better than trie map?

Question

By trie map, I mean an associative array where the payload is stored in a trie instead of a hash table.

When I use a hash map / table, the keys I use are usually strings. What are the advantages of a hash map over some three-dimensional map? I read that the hash map is faster - but it seems to me that sequential hash functions would have to check each element of the array (char) for the final hash - iterate through the array once. In trie, you would also need to iterate over the array only once.

It seems to me that when encoding small objects it will use much more memory (even if you only allow alphabetic letters in keys, these are 26 pointers to a node and often several nodes per key), but on the plus side, you never have to worry about resizing . Why hash maps are so common, but have I never seen a trie map?

Answer 1

Hash maps are more common than tri-maps because they are more universal: they can be made to work on any object that is hashed, and trie works with sequences. Hash tables also have better link locality in common implementations because they store items close to each other.

(Strictly speaking, each object is a sequence of bits, but then a common three will require the user to serialize his object before storing it in trie. This is quite inconvenient compared to defining custom hash functions.)

Answer 2

Just in case, if you are a Scala programmer, TrieMap is a "parallel, thread-safe hash array implementation matched by trie". There is no Java lib standard at this point.