Collision Resolution Chaining

A method for Collision Resolution that involves storing a Double Linked List at each entry of a hash table. An element with key $k_1$ and element with key $k_2$ can be stored at position $h(k_1)=h(k_2)$

Complexity Analysis

• insert(k,v) takes $\Theta (1)$ time
• delete(k) takes $\Theta (1)$ time after search
• search(k) worst case $\Theta (n)$ where every entry of table has no elements except for target entry with $n$ elements