The standard hash table has buckets, though, not just a single array that is probed through in case there's no space for a value in the slot determined by the hash function?
Right, that's the beauty of this simple approach: there's only one array and it doubles as the storage for buckets. But yes, the table will have a maximum size after which you cannot add more entries. That is, in practice you would create a new hashtable with a larger capacity and rehash all the existing entries into the new, bigger table (in practice, you would do that even sooner than that, namely when a certain load factor is passed - see my previous comment where I alluded to the role of the load factor).
The cool thing, however, is: if the size of the new hashtable is double the size of the old hashtable, your amortized insertion costs are still only O(1)!
(And you don't just have to take my word for it: take my original comment and paste it into the AI interface of your choice and have it create a concrete implementation. Ask it to add a remove operation, and an automatic doubling of the array size + rehashing when the table reaches a load factor of, say, 0.7 -- the resulting code should be very manageable, and then you can run your own tests and measure times!
This is maybe not the smartest way to do hashing, but its appeal lies in its simplicity and hence compactness of implementation. There are many cases where you don't even need a 'remove' operation, and where you never have to worry about growing the array because you know that you're only ever going to hash a certain number of elements at most.)
Let's say we have removed all elements from the hash. Then all following contains -calls will need to be O(n), if I understood correctly? They need to check every slot in the array to confirm inexistence, rather than just one bucket.
There are different ways on how to implement remove, but one way to do it is to overwrite the (key, value) pair to be removed with a special "tombstone" symbol that is different from null. Another way is to shift all elements with the same hash value as the one to be removed one index to the left, and null the final position.
There are cases where contains or get would have to iterate over the whole array, basically when all the previously added elements hash-collide, i.e., are mapped to the same start-index. But every hash-implementation has pathological cases where the access methods get slow -- but if the keys are sufficiently random, you don't expect such cases to occur in practice.
