Hash Search

Store the element by a hash function. The hash function is an algorithm that compute a key into an index of buckets. The average case is O(1), and the worst case is O(n).

Collision

Collision is the situation that two or more key are mapping to the same value. When collision happens, we can apply linked-list or binary tree to store the elements in the same buckets.

Resize

When the entries become more, we need to expand the table size. (java: resize when entries is 3/4 of table size)

Time Complexity

Average

O(1)

Worst Case

O(n)

The worst case happens when all the element are inserted in the same buckets.