Table of Contents
What is Hashing?
It is a way of converting one information into another information, in a way that it is not convertible back to its original form. It is used in storing key/value pairs <K,V> for quick access with the help of a data structure called as Hashtable. Hashing is a widely used concept, it is used from start of your system to dividing loads in massive Architecture.
Is it different from Encryption?
It is different from encryption of data because encryption means that there is a way to get the original data back from the encrypted data with help of decryption. In hashing, once hashed the output hold no meaning on its own, it is just an identifier which is not different then other identifiers.
For eg: When you encrypt hello, you get jgnnq. Now this can be converted back to hello by using shift cipher decryption of shift factor 2. Now, lets say same thing was hashed and the output was we43$jsde462cfh@gd, this output holds no value of its own, it is only meaningful to the hash logic.
Hash Table
While hashing is used every now and then for seperate use cases, Hash tables is still the most widely used implementation of hashing.
Hash table stores data in the form of Key/Value pairs for fast lookup. It does that by hashing the user given keys to a hash number(generally address(array index) in the memory) and then storing the <k,v> in that address(array index). So when the user has to read/update/delete the entry they can do so in O(1) in best case scenario.
Now, while creating a hash table one will face following challenges:
- How to ensure that i can store key of any type like: string, int, float, char, etc?
- How to know what size of array needs to be created so that i can accomodate all the writes?
- Is it guaranteed that every key will be mapped to a unique address or there are collisions? if yes, how are they rectified?
Any type of key supported
In order to convert the key to address(array index), we use hash function.This hash function takes care of converting the key to a number. when User has a need to change a whole class to a key then they provide their own hash function and it is used to generate the hash.
flowchart LR
f1["Hash Function"]
Aneesh --> f1
abc123 --> f1
2343.5635 --> f1
classAnimal["class animal
{ int legs; int eyes;}"] --> f1
f1 --> 43542432
f1 --> 9798332
f1 --> 69
f1 --> 7714
Size of HashTable Array
It is obvious that for best results, one must take the whole memory size as the length of array. But, the problem is that other programs also need to run in the same computer. To overcome this issue, we limit the size of the array initially and increase it as and when required duting runtime. To make sure that generated large integers from hash function are getting stored in the limite alloted space, we use a secondry hashing function. This function helps in bringing the output of hash function in our required range. This function can be a simple modulo with size of array or a very complex one.
flowchart LR
f1["Hf1()"]
f2["Hf2()"]
Aneesh --> f1
abc123 --> f1
2343.5635 --> f1
classAnimal["class animal
{ int legs; int eyes;}"] --> f1
f1 --> 43542432
f1 --> 9798332
f1 --> 69
f1 --> 7714
43542432 --> f2
9798332 --> f2
69 --> f2
7714 --> f2
f2 --> 2
f2 --> 3
f2 --> 1
f2 --> 2
Collision Handling
As we are mapping bigger number ranges to a smaller number ranges, we are bound to get coollisions. To rectify those collisions we have different approaches.
Chaining
When 2 different keys are mapped to same location, we create a chain(linked list) for storing all those entries one after another.
While this solves the collisioning, it also makes search/read/update become O(n) in worst case scenario.
graph TD
%% Hash table buckets
Bucket0["Index 0"]
Bucket1["Index 1"]
Bucket2["Index 2"]
Bucket3["Index 3"]
%% Chains for each bucket (example chains)
Bucket1 --> Node1_1["Key: 7714, Value: 45"]
Bucket2 --> Node2_1["Key: 9798332, Value: 98"]
Node2_1 --> Node2_2["Key: 43542432, Value: 34"]
Bucket3 --> Node2_3["Key: 7714, Value: 133"]
This can be improved by using other data structures like a Self balancing Binary Search Tree. That way we can reduce the wors-case searching to O(log(n)) or O(h).
graph TD
%% Hash table buckets
Bucket0["Index 0"]
Bucket1["Index 1"]
Bucket2["Index 2"]
Bucket3["Index 3"]
%% BST for Bucket 0
Bucket0 --> N0_10["10"]
N0_10 --> N0_5["5"]
N0_10 --> N0_15["15"]
%% BST for Bucket 1
Bucket1 --> N1_20["20"]
N1_20 --> N1_17["17"]
N1_20 --> N1_25["25"]
N1_25 --> N1_22["22"]
%% BST for Bucket 3
Bucket3 --> N3_7["7"]
Open Addressing
It is based on the idea of using the hash table to its full capacity. It tries to search an empty location until it has searched all the array. This is done with the help of a probing function, which is responsible to give the next index to be checked in the hashtable. In this a search, read, update become O(n) in worst cse scenario.
In this approach we also need to keep track of what is deleted rather than just deleting it strightaway, this is because that while searching we will need that info to recusively reach to our desired element.
There 2 type of probing functions:
Linear Probing
This only shifts one by one with some set value to get the new index. major drawback is that it is highly depending on has function’s quality. It suffers with cluster sollisions where 1 colliding key can induce collisions to its nearby non colliding keys, making all the keys as colliding keys.
flowchart TD
Start([Start Insertion])
InputKey[/Input Key k/]
Hash["Compute h(k)"]
CheckSlot["Is slot h(k) empty?"]
Insert["Insert key at h(k)"]
Collision["Slot occupied → Collision"]
Probe["Probe next slot: (h(k)+i) % table_size"]
FoundSlot["Found empty slot?"]
InsertProbed["Insert key at probed slot"]
Fail["All slots checked → Table full"]
End([End])
%% Flow
Start --> InputKey --> Hash --> CheckSlot
CheckSlot -- Yes --> Insert --> End
CheckSlot -- No --> Collision --> Probe --> FoundSlot
FoundSlot -- Yes --> InsertProbed --> End
FoundSlot -- No --> Probe
Probe -->|Loop| Fail
Quadratic Probing
Similar to that of linear probing its next point is predicted based on the quadratic function. this is done to reduce clustered collision.
flowchart TD
Start([Start Insertion])
InputKey[/Input Key k/]
ComputeHash["Compute h(k)"]
CheckSlot["Is slot h(k) empty?"]
Insert["Insert key at h(k)"]
Collision["Slot occupied → Collision"]
InitI["Set i = 1"]
ComputeProbe["Compute new slot: (h(k) + c1·i + c2·i²) % table_size"]
CheckProbedSlot["Is probed slot empty?"]
InsertProbed["Insert key at probed slot"]
IncrementI["Increment i"]
Full["All slots checked → Table Full"]
End([End])
%% Flow
Start --> InputKey --> ComputeHash --> CheckSlot
CheckSlot -- Yes --> Insert --> End
CheckSlot -- No --> Collision --> InitI --> ComputeProbe --> CheckProbedSlot
CheckProbedSlot -- Yes --> InsertProbed --> End
CheckProbedSlot -- No --> IncrementI --> ComputeProbe
ComputeProbe -->|Loop until success or full| Full --> End
Important thing to note is that with a good hash function linear probing can be better than quadratic probing, because it leverages CPU cache well. When a particular index is referenced in memory its subsequent indexes are also brought in because they are of the part of same record. This makes its next probing indexes to be already present in the cache and hence faster access. This is not the case in quadratic probing as in that the indexes are farther.
Double Hashing
In this Rather than a probing function to iterate, we use a hash function. This brings randomness in traversing, resulting in reduced collisions.
flowchart TD
Start([Start Insertion])
InputKey[/Input Key k/]
ComputeH1["Compute h1(k)"]
ComputeH2["Compute h2(k) = R - (k % R)"]
CheckSlot["Is slot h1(k) empty?"]
Insert["Insert key at h1(k)"]
Collision["Slot occupied → Collision"]
InitI["Set i = 1"]
ComputeProbe["Compute new slot: (h1(k) + i × h2(k)) % table_size"]
CheckProbedSlot["Is probed slot empty?"]
InsertProbed["Insert key at probed slot"]
IncrementI["Increment i"]
Full["All slots checked → Table Full"]
End([End])
%% Flow
Start --> InputKey --> ComputeH1 --> ComputeH2 --> CheckSlot
CheckSlot -- Yes --> Insert --> End
CheckSlot -- No --> Collision --> InitI --> ComputeProbe --> CheckProbedSlot
CheckProbedSlot -- Yes --> InsertProbed --> End
CheckProbedSlot -- No --> IncrementI --> ComputeProbe
ComputeProbe -->|Loop until success or full| Full --> End
What is Better?
- Chaining is better than open addressing when the table size is smaller.
- Otherwise, Open addressing outperforms.
- In open addressing, Linear probing saves time with cache, but spends time due to clustered collision.
- Quadratic probing reduces clustering but, is not able to use caching efficiently.
- Double Hashing removes clustering completely but caching usage is also absent here. It proves better in longer run than linear probing.
Modulo Hashing Vs Consistent Hashing
While there are tons of research done to design a perfect Hashing Mechanism, when it comes to diverting load to different DB Instances or Server Pods, Hashing algorithm is always a concern.
architecture-beta
service client(app)[Client]
service server(server)[Server hashfunction modulo 3]
service db1(database)[Database 1]
service db2(database)[Database 2]
service db3(database)[Database 3]
client:R --> L:server
server:R --> L:db1
server:T --> B:db2
server:B --> T:db3
Modulo Hashing
In modulo hashing, An incoming request is hasheda dn mapped to one of the instance using a modulo based hash function.
lets say id of incoming request is abc123, now to assume H(abc123) is 3214. This will result in the 3214%3 = 1 bucket.
But,
There are some issues with this type of hashing approach:
-
A new DB Instance is added
- All the events are now needed to be redistributed with mod 4 approach.
- this can cause huge spikes in DB load, resulting in low availability.
- Might introduce downtime to the whole system.
-
A DB Instance just died
- All the events are now needed to be redistributed with mod 2 approach.
- this can cause huge spikes in DB load, resulting in low availability as not only the dead DB's load needs to be distributed, but the whole load needs to be redistributed.
- Might introduce downtime to the whole system.
-
Some die of Thirst, Some die drowning
- There is a possibility that one Instance might get excessive load
- There is also a possibility of one instance not getting enough load
Consistent Hashing
Consistent hashing, also known as circular hashing, is hashing in circle. Here fixed number point hash ring is formed and DB Instances are kept at equal distance apart.
lets say id of incoming request is abc123, now to assume H(abc123) is 3214. We will generate a hash of this and it will be in the range of the numbers we wrote in our ring. This hash will be used to generate the closest Instance. say we numbered out ring with 1 to 100.
radar-beta
axis h0["DB1"], h33["DB2"], h67["DB3"]
max 100
min 0
Now a request with hash value of 45 will come. Then it will get map to next closest instance in the clockwise direction, which is 67. so, it will get mapped to DB3. This way we are taking care of all the 3 problems that were there in modular hashing.
-
A new DB Instance is added
radar-beta
axis db0["DB1"],filler1[""], filler2[""], db2["DB2"], filler3[""], filler4[""], filler5[""], db3["DB3"], filler6[""], db4["DB4"]
max 100
min 0
Only the events from 67 to 83 needs to be redistributed rest can stay as it is.
-
A DB Instance just died
radar-beta
axis db0["DB1"],filler1[""], filler2[""], db2["DB2"], filler3[""], filler4[""], filler5[""], db3[""], filler6[""], db4[""]
max 100
min 0
Only the events from 33 to 66 needs to be redistributed rest can stay as it is.
-
Some die of Thirst, Some die drowning
radar-beta
axis a0["DB1"]
axis a15["VDB2"]
axis a30["VDB3"]
axis a45["VDB1"]
axis a60["DB2"]
axis a75["VDB3"]
axis a90["VDB1"]
axis a105["VDB2"]
axis a120["DB3"]
axis a135["VDB1"]
axis a150["VDB2"]
axis a165["VDB3"]
With virtual nodes spread accross the ring, it is impossible for 1 Instance to feel underwhelmed or overwhelmed.
Summary
This is Based on the Various blogs and YT resources. This info is not comprehensive. References are attatched below.
|