5 ms·
This is great, and I don't want to take away from it, but the idea that limiting the number of probes before a rehash is a new contribution is mistaken. I've c
by _benedict 10y ago
This is great, and I don't want to take away from it, but the idea that limiting the number of probes before a rehash is a new contribution is mistaken.
I've certainly done this in hash tables I've implemented at times, and I've seen this in library hash tables too.
One public well-known example that springs to mind is Cliff Click's NonBlockingHashMap in Java.
- cat199 10y agoAnd with one fell swoop, the thesis went pop
- 3pt14159 10y agoWhy is it mistaken?
- setr 10y ago...because its not new
- tossaway1 10y agoI feel like you misread his comment if you're asking that. His next sentence explains why it's mistaken...
- 3pt14159 10y agoI missed the word new, thanks. Deleted the comment. Edit: Apparantly I can no longer delete the comment. Stupid HN.
- dpark 10y agoYou cannot delete a comment once someone replies to it.
- dkersten 10y agoNor should you. It breaks the conversation for anyone reading it afterwards and makes the replies essentially off topic.
- grzm 10y agoAs 'dpark noted, you can't delete a comment once it's been replied to: I believe this is to ensure that there aren't dangling comments. If the comment is still new enough (less than 2 hours old, I think), you may still edit the comment. For example, in this case you could chose to include your note about missing the word new in that comment itself.
- deleted 10y ago[deleted]
- bradleyjg 10y agoOne approach I've read about is to keep a metric for the number of probes as it relates to the overall capacity of the table. If a single bucket starts to fill up while the table itself is at relatively low capacity it is assumed that the data structure is under attack and it is rehashed with a DoS resistant hash function. This allows a fast, but non-resistant, hash function to be used most of the time without incurring a huge penalty in the pathological case.