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).

  • a hash by definition may be equal for distinct objects so a badly/maliciously designed hash function will still defeat it and cause O(n) worst-case complexity – ratchet freak Jun 27 '14 at 8:27
  • @ratchetfreak If you use the full hash as the key for the BST, yes. There is also the possibility of using the actual key (the thing you hashed), with the slight disadvantage that you need to define an ordering if you haven't already. – user7043 Jun 27 '14 at 9:27
  • If I use the same hash as for the hashtable the collisions will end up being resolved as a linked list in rather than a tree as inserting the same element into a tree effectively forms a linked list, so I guess it doesn't actually make sense to use trees with hashtables? – newlogic Jun 27 '14 at 10:49
  • Maybe if you use two separate functions one to seperate the values in the hashtable, the other for the tree keys then it works? – newlogic Jun 27 '14 at 10:52
  • As an aside, it also means that inserts become O(log n) rather than O(1) (even the worst case insert for an unordered linked list is O(1)). This also assumes that the key is Comparable (or similar for whatever language) - keys that don't implement an ordering cannot be backed with a tree rather than a chain bucket. – user40980 Jul 27 '14 at 11:51

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.


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. – rurban Mar 18 '17 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.