Summary
Full Transcript
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
Continue this lesson in the app
Install CourseHive on Android or iOS to keep learning while you move.
