why Hash table time complexity is o(1)

Question

if hashtables are arrays under the hood, then why its time complexity is o(1) for insert and delete operations. will it be stored as free memory slots rather than back to back memory slots? why we are not considering that copy operation for hashtable itself?

I tried searching for some online references but no significant answer is found.

Answer 1

Most of the hash table implementations have O(1) complexity on inserts and deletes in what called amortized time. That means that occasionally an operation might indeed take large amount of time (e.g. order of magnitude N - the number of elements in the table), but on any given infinite sequence of insert/delete queries average amount of operations per query will be limited by a constant. This is similar to a simple dynamic array's inserts being O(1) in amortized time even though occasionally an insert will cause full copy of an array which is definitely not a constant time operation.