The Challenge

Set ADT and Map ADT can be efficiently implemented using a Hash Table.

  • has/get(key): compute getIndex(key), check corresponding array element for entry with matching key.

  • insert/put(key, value): compute getIndex(key), add or update corresponding array element with entry for matching key.

  • remove(key): compute getIndex(key), find entry with matching key in corresponding array collection.

The performance of a hash table depends on how good the hashing procedure is, and how efficiently and effectively the collisions are handled.

A collision occurs when two different keys $x$ and $y$ map to the same position (array index) in the hash table, i.e., getIndex(x) == getIndex(y).