Why are hash maps better than trie maps?

Question

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

When I'm using a hash map/table, the keys I use are typically strings. What are the advantages of a hash map over some trie based map? I have read that a hash map is faster - but it seems to me that a consistent hash functions would have to check each element of the (char) array for the final hash - iterating over the array once. In a trie you would similarly have to iterate over the array just once.

It does seem to me that this would use a lot more memory when encoding small objects (even if you only allow lower case alpha characters in the keys, it's 26 pointers per node and often multiple nodes per key), but on the plus side you never have to worry about resizing. Why is it that hash maps are so common, but I've never seen a trie map?

Enounce

Answer 1

Hash maps are more common than trie maps because they are more generic: they can be made to work on any object that is hashable, while a trie works on sequences. Hash tables also have better locality of reference in common implementations because they store elements close together.

(Strictly speaking, every object is a sequence of bits, but then a generic trie would require the user to serialize their object before storing it in the trie. That's pretty inconvenient compared to defining custom hash functions.)

Fahy

Actually, it's also quite possible to build tries of trees. – Capitulary

Answer 2

Just in case you are a Scala programmer, TrieMap is a "concurrent thread-safe lock-free implementation of a hash array mapped trie". There's none in Java standard lib this moment.

Annam