Trees, Hash Tables and Tries

http://benlynn.blogspot.com/2007/04/trees-hash-tables-and-tries.html

by skorks • 16 years ago

32 23 16 years ago

benlynn.blogspot.com

timtadh• 16 years ago

I have also been getting into tries recently (last 6 months) and if you are interested in learning about them I recommend Sedgewick's Algorithms in C (parts 1-4) for a good introduction to the subject. Available on Safari if you have access to that.

liuliu2• 16 years ago

I will argue that a properly implemented tries are more compact but not necessarily faster than hash table. The fact is, there are some badly implemented tries which even worse than hash table in term of memory consumption. Also, I'd like to point out the actually trie implementation may not have a fix k child node. I most often use k = 256 or 512 for the first few layers and 4~8 for the last few one in order to get "hash table" like performance for the first few layers and "tree" like performance for a deeper lookup.

mhansen• 16 years ago

I will argue that a properly implemented tries are more compact but not necessarily faster than hash table.

Where do you argue this?

The fact is, there are some badly implemented tries which even worse than hash table in term of memory consumption.

Any data structure can be badly implemented. What use is comparing a badly implemented data structure to a well-implemented one?

liuliu2• 16 years ago

It seems in the article the author suggests that in certain case tries is faster than hash table.

Yes, you are right about every data structure can be badly implemented. But some data structures are more easily to get wrong. For example, everyone have no problem with selection sort, it is just hard to get it wrong. But for binary search, some decent programmer may write (a + b) / 2. Same case for tries, people more commonly (intuitively) write things like node_t* child[26];

AlisdairO7• 16 years ago

In the real world, it's unlikely that a trie of any real size will be comparably performant to a hash table with a sane hash function: trie algorithms involve moving from node to node, each of which will require an unpredictable retrieval from non-sequential memory. Memory latency is pretty high these days (~200 cycles), so hash tables will almost always be quicker.

This is not to say that radix tries aren't extremely useful - they're compact and fast - but they're unlikely to match a hash table for raw performance.

jules2• 16 years ago

Here's an interesting paper. It describes a cross between a trie and a hash table. Instead of storing the string itself in the trie, it first hashes the string and then stores that in a trie (in a smart way). The memory usage is claimed to be very good, and the benchmarks in the paper seem to show that it's faster than a hash table for lookup...

http://lampwww.epfl.ch/papers/idealhashtrees.pdf

AlisdairO7• 16 years ago

Thanks for the link! I'll be interested to take a look.

angstrom• 16 years ago

Another good example that can be more performant than a hash or a trie on a given alphabet is a directed acyclic word graph. Think of it as a trie that reuses edges, but has no cycles. This makes it very compact.

There's an implementation of one here that I've messed with, but it's a little expensive on the setup side.

http://www.pathcom.com/~vadco/dawg.html

The final result is that each node is stored in a 32bit word with the possible characters limited to a 5 bit field. 1 bit flag for word endings and I believe he employed offsets with the rest of the bits to perform the directed lookups of the other characters in a limited A-Z uppercase only alphabet. These types of graphs tend to extremely fast at runtime, but like I mentioned, the setup is costly. However, if you were embedding this in a device this would definitely be a worthwhile investigation. This is one of those cases where a data structure fits a very constrained, but well defined requirement.

elblanco5• 16 years ago

I've done a bit of work with tries and hash functions and found that in-memory tries are almost universally faster than in-memory hashes, no matter how good the hash function is.

The difference though is on average around 20-30% faster if both implementations are well optimized. But they come with lots of downsides that need to managed well, tries explode into memory very quickly requiring all kinds of memory optimizations to the naive tries to keep the tree depth short (usually with a small hash on the leaves). I remember building an in-memory trie library once in Perl that outperformed a native C hash library by 70%. The development team's jaws dropped when my code was running, they were insisting it wasn't actually doing anything at all and I was faking the output. "There is no way Perl code can outperform our C." It was an interesting learning experience all around. Suffix trees likewise are insane for full text searching.

Hashes on the other hand have a few benefits, they are more compact in memory, on average have fast lookups (though if you try and constrain the hash table growth algorithm too much the can spend a lot of time on both collisions and on table growth operations) and have many many more high quality implementations in most standard libraries, including many very good and very fast on-disk hashes that only consume another few percentage points (single digits usually) off of speed.

The problem with tries is not that they are fast, there really isn't anything faster (in memory) that I'm aware of for lookup and retrieval problems. But tries are like sports cars, really fast, but lots of downsides. Hashes are like an upper end practical family car.

If you try and put the trie on disk, you end up with all sorts of problems that you don't really see in modern on-disk hash implementations. Coming off of disk, hashes tend to be the better option (in fact many of the on-disk trie interfaces I've seen actually just use hashes for the on-disk portion and optimize for tree depth in memory to keep things small).

So it depends, if the set of things you want to use for lookups is relatively small and you can cram it all into memory in a raw trie, it'll be a bit faster. If the set is big, and you want to use it off of disk, go with a hash.

Also, if the values you wish to store don't map well to a trie, like floating point numbers, you pretty much have to go with a hash. Fortunately, the hash function in that case is really easy ;)

doty• 16 years ago

I've done a bit of work with tries and hash functions and found that in-memory tries are almost universally faster than in-memory hashes, no matter how good the hash function is.

Do you have any insight on why this would be? It's not very intuitive to me.

A hash-table with low load has relatively small hash buckets and so touches fairly little memory, and string keys are fairly local, so I would have expected memory costs to dominate. Insertion and deletion from a hash table should require fewer allocations than insertion and deletion from a trie.

AlisdairO7• 16 years ago

That's really interesting - but it's hard for me to understand. What makes them faster for lookup than a hash table with a really good, fast hash function (say, murmurhash)? Does it depend on factors like string length? Basically, what's the environment?

My assumption is that it's faster because you might end up performing fewer string comparisons with the trie - if you have strings with common prefixes/sizes, this could cost you time on a hash with collisions. Although it seems like unless you have a lot of strings with common prefixes/sizes, this still ought to be pretty fast. And if you do have a lot of similar strings, you could store the hash value as well to speed this up.

My work on cache-sensitive data structures is in the integer space, so perhaps my ignorance when it comes to working with strings is showing :-).

Dellort• 16 years ago

If I do recall correctly if you do not require dynamic insertion/removal; That is, you can make do with a one time construction. You will not need to traverse pointers but can put the trie into one contiguous block of memory.

AlisdairO7• 16 years ago

That is absolutely true - it's been done with B+Trees, for example, as CSS-Trees. This does make finds faster (because you eliminate the space in the cache that pointers would require), but you're still going to be doing a lot of nonsequential access when performing finds.

signa11• 16 years ago

what about judy-arrays[http://judy.sourceforge.net/] ? they seem to be pretty seriously cache-optimized...

AlisdairO7• 16 years ago

I've not encountered them before, but yes, they do seem to be very heavily optimised. I guess with relatively large nodes the quantity of cache misses is relatively low.

senderista• 16 years ago

In the same way, any naively "constant space" algorithm that indexes into an array with a fixed number of pointers or indices is technically O(log n) in space, since you need log n bits to index n objects. So a space factor of log n can generally be treated as constant in practice.

Trees, Hash Tables and Tries

Related Stories