Hash tables are `O(1)`

**average and amortized** time complexity case complexity, however it suffers from `O(n)`

**worst case** time complexity (when you have only one bucket in the hash table, then the search complexity is `O(n)`

). A hashtable typically has a space complexity of `O(n)`

.

Hash tables suffer from `O(n)`

worst time complexity due to two reasons:

- If too many elements were hashed into the same key: looking inside this key may take
`O(n)`

time (for linked lists) - Once a hash table has passed its
*load balance*– it has to rehash (create a new bigger table, and re-insert each element to the table).

However, it is said to be `O(1)`

average and amortized case because:

- It is very rare that many items will be hashed to the same key if you chose a good hash function and you don’t have too big load balance.
- The rehash operation, which is
`O(n)`

, can at most happen after`n/2`

ops, which are all assumed`O(1)`

: Thus when you sum the average time per op, you get :`(n*O(1) + O(n)) / n) = O(1)`