Is there a known standard data structure which is a hash table that resolves collisions using a binary tree? If so what is the name of this data structure? I imagine such a structure would be useful as it should reduce the worst case search time down to O(log(n)) compared to O(n) in a hash table, and the best case would still be O(1).
2 Answers
Yes, but there isn't a standard name for it shorter than what you've already written.
Wikipedia says:
[...] by using a self-balancing tree, the theoretical worst-case time of common hash table operations (insertion, deletion, lookup) can be brought down to O(log n) rather than O(n). However, this approach is only worth the trouble and extra memory cost if long delays must be avoided at all costs (e.g. in a real-time application), or if one must guard against many entries hashed to the same slot [...]
and that's pretty much the reason why.
answered Jun 27, 2014 at 8:14
Knuth came up with the name "ordered hash table" for this bucket collision strategy, which can use any of the many log n search data structures. Most people are not aware of that and in practice I've seen only KyotoDB using it. Most others switched from simple linked lists to open addressing schemes (double hashing, Cuckoo, Robin Hood) for better cache performance.
"Ordered hash tables", O Amble, D Knuth 1973 http://comjnl.oxfordjournals.org/content/17/2/135.full.pdf
You can use a balanced tree, a trie, or just a simple ordered array with binary search, since mostly the bucket size will be < 8. It mostly a cache issue, so you will not want to use many pointers for a tree.
-
java also switched on too many collisions from a linked list to a tree.– rurbanCommented Mar 18, 2017 at 11:51
Comparable(or similar for whatever language) - keys that don't implement an ordering cannot be backed with a tree rather than a chain bucket.