That’s not really a trick?
It’s an open addressing hash table (https://en.wikipedia.org/wiki/Open_addressing), with a linear probing collision resolution (https://en.wikipedia.org/wiki/Linear_probing).
It’s an open addressing hash table (https://en.wikipedia.org/wiki/Open_addressing), with a linear probing collision resolution (https://en.wikipedia.org/wiki/Linear_probing).
When it's full, insertion requires rehashing into a bigger table. (Or you can use an overflow list when the table is full or nearly full, if you don't want to rehash and prefer to treat this case as rare and ok to be slow.)
So for a general purpose open addressing / closed hashing hash table where you don't know the number of items in advance, rehashing to a bigger table is done at some threshold before it's actually full.
As long as you do rehashing using a multiplier, for example doubling the size at 50% full (as opposed to adding a fixed amount to the size), it stays fast on average, but the rehashing operations are of course individually slow. They just don't happen often, so the average stays at O(1) time. This is called amortised O(1) time complexity. The ideal threshold for resizing depends on the probing type.
Linked list hash tables, (also called closed addressing or open hashing - I think linked list is a clearer name) don't suffer from catastrophic slowdown with size in the same way as the open addressing / closed hashing type. Nor abrupt failure when full, because they're never full. These can still be resized and this is required if O(1) time is required to arbitrary numbers of items, but the resizing threshold is not as critical. If not resized they gradually degrade to O(N) time performance when filled too much. Many applications use fixed size linked list hash tables safely because of this.
Array-of-arrays hash tables behave similarly to linked list hash tables.
Usually yes, though it’s also possible to perform gradual resizing that’s less efficient so it’s only used when needed (e.g. real time systems which can’t afford a full resize).
> What are the Performance implications of that?
Same as a vector. That’s why hashmaps generally provide an amortized insertion time.
> What we didn't look at though was, what happens when the hash table is full?
Of note: a hash table never gets full, hash tables have a load factor (which mostly depends on the collision resolution algorithm, as that informs how performances degrade as collisions increase), and the table will resize when it exceeds its load factor, to maintain a “healthy” rate of collisions.