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

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?

• The brouhaha around that "HashDOS attack" baffled me: It's essentially the standard motivation given for universal hashing, in undergrad algorithm classes. Why were people acting so surprised? Jun 29 '12 at 23:59

Yes, there is a name for it: Hashtable.

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

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.

• This isn't really an answer but a comment. Would probably be better in the future to use the comments section for commentary, since you have enough rep for comments. Jun 30 '12 at 22:37

You might want to take a look at Judy arrays:

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

http://judy.sourceforge.net/