When the load factor of an open-addressed hashtable gets too high, you allocate a larger set of buckets and rehash the table’s existing contents into them. You

When the load factor of an open-addressed hashtable gets too high, you allocate a larger set of buckets and rehash the table’s existing contents into them. You’ll have to do this with a chained hashtable anyway, as performance will start to approach O(n) once the table is overloaded. This does mean that insertion time goes from a true O(1) to an amortized O(1), but that’s usually not an issue. (You can do the rehashing gradually if you really have to, but it’s probably not worth the complexity.)