A hash function is a mathematical function that takes a value and maps it to a different kind of value, known as the hash value, hash code, digest, or hash. Various algorithms are used to calculate hash values, including those used in cryptography, such as storing passwords.

Collision

A collision occurs when two distinct keys generate the same hash value.

Handling Collisions

Chaining

• Create a hash and map it to a linked list that stores (key, value).
• When the same hash is generated for different keys, link the (key, value) to the end of the linked list.

Open Addressing

• When a collision occurs, find the next available slot in the hash table and store the (key, value) there.

• There are three types of Probings:

  • Linear Probing
  • Quadratic Probing
  • Double Hasing