Time complexity of Hash table

Question

I am confused about the time complexity of hash table many articles state that they are "amortized O(1)" not true order O(1) what does this mean in real applications. What is the average time complexity of the operations in a hash table, in actual implementation not in theory, and why are the operations not true O(1)?

Answer 1

For some uses of hash tables, it's impossible to create them of the "right" size in advance, because it is not known how many elements will need to be held simultaneously during the lifetime of the table. If you want to keep fast access, you need to resize the table from time to time as the number of element grows. This resizing takes linear time with respect to the number of elements already in the table, and is usually done on an insertion, when the number elements passes a threshold.

These resizing operations can be made seldom enough that the amortized cost of insertion is still constant (by following a geometric progression for the size of the table, for instance doubling the size each time it is resized). But one insertion from time to time takes O(n) time because it triggers a resize.

In practice, this is not a problem unless you are building hard real-time applications.

Answer 2

It's impossible to know in advance how many collisions you will get with your hash function, as well as things like needing to resize. This can add an element of unpredictability to the performance of a hash table, making it not true O(1). However, virtually all hash table implementations offer O(1) on the vast, vast, vast majority of inserts. This is the same as array inserting - it's O(1) unless you need to resize, in which case it's O(n), plus the collision uncertainty.

In reality, hash collisions are very rare and the only condition in which you'd need to worry about these details is when your specific code has a very tight time window in which it must run. For virtually every use case, hash tables are O(1). More impressive than O(1) insertion is O(1) lookup.

Answer 3

From Wikipedia:

Amortized Analysis finds the average running time per operation over a worst-case sequence of operations. Amortized analysis differs from average-case performance in that probability is not involved; amortized analysis guarantees the time per operation over worst-case performance.

Consider the worst case, where all the hashes coincide, in a hash table of size m(m<<n). Let the entry that you are looking for be the last one inserted. Hence, you would have to search m entries (ie.the whole table), to get to your desired entry. If you wish to lookup another entry, you can be sure that it would take less than m searches to get to your desired entry.

Let us assume that you perform a lookup n times, & always look for the last entry inserted. Hence, the worst-case sequence of operations gives, m + m + ... + m n times, which is O(n).

Hence, the amortized time per operation is,

  total time complexity       O(n)  
__________________________  = ____ = O(1)
total number of operations     n