Hacker News Reader

Comment by _benedict | Hacker News Reader

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.

View on HN

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

Why is it mistaken?

...because its not new

I feel like you misread his comment if you're asking that. His next sentence explains why it's mistaken...

I missed the word new, thanks. Deleted the comment.

Edit: Apparantly I can no longer delete the comment. Stupid HN.

You cannot delete a comment once someone replies to it.

Nor should you. It breaks the conversation for anyone reading it afterwards and makes the replies essentially off topic.

As '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.

And with one fell swoop, the thesis went pop

Reply on news.ycombinator.com