Featured

Closed Hashing - (Linear Probing, Quadratic Probing & Double Hashing) | Collision Control



Published
In this video tutorial we will understand in detail what is Closed Hashing.
We will also study in detail the 3 different types of closed hashing(open adddressing) -
1. Linear Probing
2. Quadratic Probing
3. Double Hashing
In Open Addressing, all elements are stored in the hash table itself. So at any point, the size of the table must be greater than or equal to the total number of keys.
This entire procedure is based upon probing.

1) Linear Probing -
In linear probing, the hash table is searched sequentially that starts from the original location of the hash. If in case the location that we get is already occupied, then we check for the next location.
The function used for rehashing is as follows: rehash(key) = (n+1) % table-size.

2) Quadratic Probing (Mid-Square Method) -
In quadratic probing, the algorithm searches for slots in a more spaced-out manner. This is done to eliminate the drawback of clustering faced in linear probing. When a collision occurs, the algorithm looks for the next slot using an equation that involves the original hash value and a quadratic function. If that slot is also occupied, the algorithm increments the value of the quadratic function and tries again. This process is repeated until an empty slot is found.

3) Double Hashing -
In double hashing, we make use of two hash functions. The first hash function is h1(k), his function takes in our key and gives out a location on the hash-table. If the new location is empty, we can easily place our key in there without ever using the secondary hash function. However, in case of a collision, we need to use secondary hash-function h2(k) in combination with the first hash-function h1(k) to find a new location on the hash-table.
---------------------------------------------------------------------------------------------
Theory & Code article -
Full DSA playlist - https://www.youtube.com/watch?v=XCyuHSJS7XE&list=PLIY8eNdw5tW_zX3OCzX7NJ8bL1p6pWfgG
Full C++ Programming for Beginners Course - https://www.youtube.com/watch?v=AKNGgAXTark&list=PLIY8eNdw5tW_o8gsLqNBu8gmScCAqKm2Q
---------------------------------------------------------------------------------------------
Timecodes -
0:00 Intro & recap
0:54 Closed Hashing Introduction
3:04 Linear Probing with Example
15:00 Quadratic Probing with Example
23:05 Double Hashing with Example
30:00 Conclusion
---------------------------------------------------------------------------------------------
Support Simple Snippets by Donations -
Google Pay UPI ID - tanmaysakpal11@okicici
PayPal - paypal.me/tanmaysakpal11
---------------------------------------------------------------------------------------------
Simple Snippets Official Website -
http://simplesnippets.tech/
Simple Snippets on Facebook -
https://www.facebook.com/simplesnippets/
Simple Snippets on Instagram -
https://www.instagram.com/simplesnippets/
Simple Snippets on Twitter -
https://twitter.com/simplesnippet
Simple Snippets Google Plus Page -
https://plus.google.com/+SimpleSnippets
Simple Snippets email ID -
[email protected]

For More Technology News, Latest Updates and Blog articles visit our Official Website - http://simplesnippets.tech/
#closedhashing #hashing #collisioncontrol #hashdatastructure
Category
Management
Be the first to comment