Re:A hash table by any other name
by tubs on Friday July 26, 2024 @01:21PM
(#41080418)
They resize the top level array and rehash items into their new buckets.
[ Parent
| on HN ]
Re:A hash table by any other name
by tialaramex on Friday July 26, 2024 @02:38PM
(#41081079)
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.
Re:A hash table by any other name
by tialaramex on Friday July 26, 2024 @03:50PM
(#41081678)
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.