Hacker News Reader

Comment by o11c | Hacker News Reader

That would be fine, except that in v2 the buckets are fixed size.

What happens when more than 20 objects end up with the exact same hash?

Yes it does seem like a problem, by my reading this will just endlessly try to "split" the bucket of 20 items, hoping that eventually one of the items goes into a new bucket leaving space, but if they have the same hash that never happens, disaster.

If I'm wrong I don't think this code does a good enough job of explaining what's going on, and if I'm correct it's defective and should not ship.

Even if this situation "shouldn't" happen, it clearly can happen, you just have to get unlucky, and it's difficult to compute how unlikely that is for real systems, so better to ensure that "We got unlucky" isn't a disaster for the kernel.

No desaster. On an actual attack (eg if the seed leaked) you count the collisions and return empty on some low threshold. Like 100 on 32bit

Where in the code is this "no disaster" routine you describe?

The code is not security hardened yet. seed attacks are not yet accustomed for. But it's no disaster, as it's trivial to prevent. They say seeds are secure, so no chance to attack it. Which is a bit childish.

It would just be a disaster if they follow Miller's networking code, which uses slower hashes to prevent seed attacks. But every other popular language/library does the very same wrong thing.

If it were my hash table, the arrays would just be unrolled linked lists.

So a "twenty object" bucket would actually store 19 objects, and if the last one wasn't null it would contain a pointer to the next bucket.

I'm willing to presume these folks know what they're doing, so that's probably what's happening here.

They resize the top level array and rehash items into their new buckets.

Sure. There were 20 items in the bucket with the same hash, we wanted to add one more.

So we grow the top level hash table and we put all of the twenty items in the same new bucket, because they have the same hash, and then we... oh, we don't have enough room. Try again? (The code presented does). Too bad, that can't help.

In your understanding, why does this not happen? That's the question. How do this code ensure this can't happen? If it doesn't, if it's just hoping to get lucky the code must not be used.

They go to the same bucket because their hash *mod the size of the top array* collides.

This whole sub-thread is about the case where the entire hash collides

Changing which bits we use changes nothing for this problem case.

I see what you mean here, sorry.

I guess I'd argue if you have 20 items whose full hash collides then something is pretty seriously wrong with the hashing algorithm - raise an error/exception/panic/(whatever is appropriate for the situation) and surface it.

I think they address this in the article. They use arrays instead of linked lists. Which makes direct key comparison very fast, because it's all in CPU cache.

"I just use an array" doesn't solve the problem "What if the array is full?".

In fact it makes that problem acute. A linked list structure will degrade gradually as we shove more entries with the same hash into it, every look-up incurs a pointer chase down the entire list, slower is eventually unacceptable but we do get signs first -- but with arrays we're just screwed, in C it's pretty likely we end up with an illegal dereference or we lose data once there's no room.

If it's designed to be used for caching, then replacing an old entry or throwing away the new one is quite possibly a perfectly reasonable "out."

If it's designed to be used for other purposes as well, not so much.

(I wasn't entirely sure which from reading the article)

Reply on news.ycombinator.com