System Design #11 Hashing

Purpose of Hashing

1 Hashing is used to index a data

2 In Cryptographic application

3 Sharding the keys

4 Finding duplicate records

• Hashing is generating a value or values from a string of text using a mathematical function called the Hash Function
• Hashing is one way to enable security during message transmission when the message is intended for a particular recipient only.

Hashing

hashing is done by Hash Table & Hash Function

H(x)= x mod 10

The Hash table consists of 0 to 9

• 21,56,72,39,48,96 will be stored as per x mod 10
• 56 & 96 will occur in the same cell so they will be override

What is good function:

• Easy to compute
• Even distribution
• Less collision

How to resolve collision (Simple collision handling):

• We can have separate chaining when more than 1 item is in the cell. The new item will be at the front.
• This way, we can insert all items, but searching & deletion will take time.
• This is open hashing as we’ll create a linked list to add collision.

Open addressing (Closed hashing)

• In this, data goes inside the table, no need to make a linked list

By linear probing

If x mod 10 is already present, do it on (x + 1) mod 10, if it’s present too, do it on (x + 2) mod 10

The issue is there’ll block of data in chucks, not evenly distributed

For it, quadratic probing

• In this

H(x) = (Hash(x) + f(I))

f(i) = i ^ 2;

Double Hashing :

f(i) = i * Hash2(x)

Hash2(x) = R — x mode R (i.e R = 7)