An explicit language construct for radix trees is an interesting idea, but once you really need trees you might be closer to needing a real RDBMS, or an in process extension such as sqlite.
An explicit language construct for radix trees is an interesting idea, but once you really need trees you might be closer to needing a real RDBMS, or an in process extension such as sqlite.
Sure, but remember it also takes time to compute the actual hash value. That process itself is O(n) where n is length of the key. For large keys sizes and small set sizes the tree probably wins (for some definition of "large" and "small").
The critbit algorithm walks the tree while simultaneously moving through the key bytes/bits. It seems to me that for most modestly sized sets it has the advantage.
I always wondered why. In my coding experience, for most generic coding tasks, key-value dictionary backed by a hash was a better go-to construct. I wonder if it has something to do with processor branch prediction; a random guess would be that it would be hard to do b-tree branch prediction on a well balanced tree, while hash is constant.
Its a very good point that when it comes to hashing a very long key string this crit-bit tree structure has interesting properties. I wonder if this structure could be used to implement a good(better?) average case implementation of the LCS problem. http://en.wikipedia.org/wiki/Longest_common_subsequence_prob...