3 ms·

Lookup and operations on tree structures are is O(Log(n)). A hash is O(1) (on average). They have different uses; defaulting a dictionary to a hash is a valid l

Lookup and operations on tree structures are is O(Log(n)). A hash is O(1) (on average). They have different uses; defaulting a dictionary to a hash is a valid language decision IMHO, its lightweight and it fits the bill. And on average it will be faster. 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.

__david__ 13y ago
> Lookup and operations on tree structures are is O(Log(n)). A hash is O(1) (on average). 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.
- cpeterso 13y ago
  That's why C++ STL's std::map and std::set are typically implemented using (some flavor of) binary trees.
  - headgasket 13y ago
    standard C++11 added std::unordered_map which is hash backed. Previously gcc and ms had the STL hash in the std namespace, but it was not part of the standard. 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_problem http://en.wikipedia.org/wiki/Longest_common_subsequence_prob...

__david__ 13y ago

> Lookup and operations on tree structures are is O(Log(n)). A hash is O(1) (on average). 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.

cpeterso 13y ago
That's why C++ STL's std::map and std::set are typically implemented using (some flavor of) binary trees.
- headgasket 13y ago
  standard C++11 added std::unordered_map which is hash backed. Previously gcc and ms had the STL hash in the std namespace, but it was not part of the standard. 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_problem http://en.wikipedia.org/wiki/Longest_common_subsequence_prob...