Is there a name for a hashtable with a tree for each bin instead of a list?

Question

It is well-known that the worst case performance for a chaining hashtable, is O(n), where n is the number of objects in the table. The normal assumption is that the hash is either uniform, or secure, however this is not always the case.

One possible solution to this problem would be to use a tree, or other O($\log n$) data structure, instead of the list. This would result in the worst-case performance of O($\log n$) for insertion and retrieval, at the expense of adding an extra constraint on the import data, namely that it would need to be comparable.

Is there a name for such a data structure?

Answer 1

Yes, there is a name for it: Hashtable.

You can have whatever you want for collision bins: Lists, trees, hashtables, whatever you fancy.

Answer 2

You call them “the structure from Knuth 6.4 exercise 38”. This is a bit unfair because it does not give credit to P. F. Windley who has suggested this structure first, but then anyone can look up that information in Knuth easily.

Answer 3

You might want to take a look at Judy arrays:

http://en.wikipedia.org/wiki/Judy_array

http://judy.sourceforge.net/