Re:Trees, Hash Tables and Tries
by doty on Sunday April 04, 2010 @12:11PM
(#1240368)
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.
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.