<p>Yes, there is a name for it: Hashtable.</p>

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

CC BY-SA 3.0
2012-06-29T18:25:58.147Z
2012-06-29T18:25:58.147Z
Thomas Eding
<p>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.  </p>

CC BY-SA 3.0
2012-06-30T22:37:53.950Z
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.
Josephine Moeller
CC BY-SA 3.0
2012-06-29T20:37:27.343Z
2012-06-29T20:37:27.343Z
Zsbán Ambrus
<p>You might want to take a look at Judy arrays:</p>

<p><a href="http://en.wikipedia.org/wiki/Judy_array" rel="nofollow">http://en.wikipedia.org/wiki/Judy_array</a></p>

<p><a href="http://judy.sourceforge.net/" rel="nofollow">http://judy.sourceforge.net/</a></p>

CC BY-SA 3.0
2012-06-28T21:37:14.440Z
2012-06-28T21:37:14.440Z
user1366430
<p>It is well-known that the worst case performance for a <a href="http://infoweekly.blogspot.nl/2010/01/basic-hashtables.html" rel="nofollow">chaining hashtable</a>, 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 <a href="http://armoredbarista.blogspot.de/2012/02/investigating-hashdos-issue.html" rel="nofollow">not always the case</a>.</p>

<p>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.</p>

<p>Is there a name for such a data structure?</p>

CC BY-SA 3.0
2012-06-29T23:59:47.750Z
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?
Radu GRIGore
<ds.data-structures><terminology>
Is there a name for a hashtable with a tree for each bin instead of a list?
Paul Wagland
# Is there a name for a hashtable with a tree for each bin instead of a list?

(Asked by: username_0 on 2012-06-24)

It is well-known that the worst case performance for a [chaining hashtable](http://infoweekly.blogspot.nl/2010/01/basic-hashtables.html), 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](http://armoredbarista.blogspot.de/2012/02/investigating-hashdos-issue.html).

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?

**Tags:** ds.data-structures, terminology

> **Comments:**
> **username_1**: 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?  

---

## 3 answers

### Answer by username_2 on 2012-06-29. Score: 2 | Accepted answer

Yes, there is a name for it: Hashtable.

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


---

### Answer by username_3 on 2012-06-29. Score: 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.

> **Comments:**
> **username_4**: 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.  

---

### Answer by username_5 on 2012-06-28. Score: -1

You might want to take a look at Judy arrays:

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

<http://judy.sourceforge.net/>


---

