2 ms·

How is that possible? I insert three pathological keys. The third one collides with both, so it rebuilds the table. The third one still collides with both, so i

How is that possible? I insert three pathological keys. The third one collides with both, so it rebuilds the table. The third one still collides with both, so it rebuilds the table again. Repeat. Eventually either we fail or we end up in something that’s worse than constant time.

jolux 8y ago
Have you read about how the algorithm works?
- mikeash 8y ago
  A bit. When you collide in both tables, you switch to a different hash function and try again. With real-world data, that should work great. But with pathological data (i.e. the worst case behavior) that will never succeed.