4 ms·

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

• tialaramex 2y ago
  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.
  • tubs 2y ago
    They go to the same bucket because their hash *mod the size of the top array* collides.
    • tialaramex 2y ago
      This whole sub-thread is about the case where the entire hash collides Changing which bits we use changes nothing for this problem case.
      • tubs 2y ago
        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.