Hashing

• Hashing is a way to map the 🔑 of any type whether it's a string or any other object to a random position in the memory.
• If we can do that we will be able to map that key to the corresponding array index.
• A Hash function is responsible for mapping a key to an address.
• The hash function maps to a slot of the array.

Mapping hash in HashTable

• Observe that there are <Key,Value> pairs.
• Now in the hash function we pass a key to it and the function returns the address at which the value is located.
• There can be a simple formula to calculate the address.
  • The size of the array that holds the values is 10(Just for assumption).
  • Now make the operation (key % Size-of-array) = Remainder
  • Remainder will be the address at which the value will be taken.
• If the remainder will be the same for multiple keys, It leads to collision which needs to be handled.

Collision

When we pass the key to a hash generating function and it gives back a key that is already mapped to another object, We say collision has occurred.

Ways to resolve collision

(a)-Chaining

(b)-Open Addressing

Preventing the collision using chaining

• Here we use a mathematical formula (It can be anything), Now let's say it gives a key as an integer.
• We again use the same operation (key % Size-of-array) = Remainder.
• And in the place of remainder at that address, We store the value.
• Now say, We have an element already at this position, We will follow the below approach to avoid the collision.
  • We shall consider each position as buckets.
  • Now on each of the locations will be a linked-list chain.
  • If we find the same address we prepend/append the list at that address with the value.
  • Now if we need to get a value, We will go to the position and keep iterating the list until we find the element
  • Ideally we must keep a healthy size of array to manage such that the bucket size also does not increase continously.