Hash table linear probing

Key Takeaways

okay this is going to be a fun one we're going to be talking about hash tables and the linear probing technique to get started let's recap how open addressing works so in general if we have a table of size n here's how we do open addressing no matter what your probing function is so we start our constant or sorry variable X at one the key hash is just going to be whatever our hash function gives us for our key and our first index we're going to check is going to be the original hash position and while the table at the index not equal to null meaning that position is already occupied then we're going to offset the index by where the key hash is plus the probing function mod n and every time we do this we incr M the variable X so that our probing function pushes us along one extra position and then once we found a position then we can insert the key value pair into the table at that position all right so what is linear probing so linear probing is simply a probing method which probes According to some linear formula specifically the linear function p ofx = a of x + b and we have to make sure that a is not equal to zero otherwise we're just adding a constant which does nothing I have a small note right here which says the constant B is Obsolete and if you know why Post in the comments and have a discussion with the others and as we saw in the last video there's a slight problem with this currently and it's that some linear functions are unable to produce a full cycle of order n and we might end up getting stuck in a cycle here's an example of that if we picked our linear function to be P ofx = 3x and say our key K hashed to four and for some reason our table size was nine then we would end up with the following cycle occurring assuming that position S 4 7 and one are already taken by other key value pairs so the fact that we're only probing at those three locations means we're unable to reach all the other buckets which is really bad and hence we're again stuck in an infinite Loop we cannot get stuck in this situation ever so how do we avoid it so that's the question which values of the constant a in P of x equals ax produce a full cycle modulo n it turns out that this happens when the constant A and N the table size are relatively prime to each other so two numbers are relatively prime if their greatest common denominator is equal to one so that is a and N have a g DCd of one and when that happens the probing function will always be able to generate a complete cycle and we will always be able to find an empty bucket awesome all right here's an example with linear probing so suppose we have an originally empty hash table and we want to insert some key value Pairs and we selected our probing function to be P of X = 6x and our table size to be N = 9 and then we also selected a Max load factor of alpha equals uh about 2/3 and the threshold will then be six so we resize once we he hit six elements okay so based on the probing function we chose and the table size are we likely to run into an infinite Loop while inserting based on what I told you in the last few slides and the answer is yes the greatest common denominator of 9 and 6 is equal to three which is not one so let's go ahead and attempt to insert some elements regardless we may or may not hit any problems okay so first let's insert so I guess on the left I have some key value pairs I want to insert and we're going to insert K1 first so suppose that the hash value for K of 1 is equal to 2 then we would say all right the hash of K1 plus the probing sequence at zero mod 99 is equal to 2 so we're going to insert that key value pair at position two all right next one so now suppose K of 2 is equal to 2 again so we're going to try insert this key value pair at position two but oh snap we have a hash Collision so we're going to increment X and now try the offset at the probing function at one instead of probing function at zero so that is instead of inserting it now at two we're going to insert it at 8 all right so that went in because that slot was free now let's try inserting key3 so key3 suppose that hashes to three then we can insert at position three and there's no issue now notice that we're trying to reinsert K2 which already exists within our hash table so instead of inserting it we're actually going to be updating its value because it exists in the hash table all right so from before we know that the hash value for K2 is two so so then we look at position two and K2 is not there and there's a hash Collision so we increment X offset it by P of one and now we're able to find K2 and now we can update the value right there let's go to K5 okay so suppose K5 has a hash value of8 so eight is taken so we're going to probe and that leads us to index 5 so we're going to insert the key value pair there now let's try to insert k6 suppose k6 hashes to five then let's probe uh one so now that so 5 + 6 mod 9 gives us two okay now the hash Collision let's keep probing so now 5 + 12 mod 999 is equal to eight all right another hash Collision so we have to increment X and keep probing and now we're back to five so we've hit a cycle all right so we're trapped in a cycle but we kind of expected this to happen because we knew that we picked two numbers whose gcd was equal to three and not one so if we look at all the possible a values we could have selected instead of six we see that the ones that give a greatest common denominator of one with n the table size are 1 2 four five 7 and 8 while any multiple of three would give us something else so this comes to the realization that for our choice of P of x if we choose P of x to be 1 * X then the the greatest common denominator of N and one is always going to be one no matter what our choice of the table size is which is why P of x = 1 * X is a very popular probing function Choice all right now suppose we have another hash table and we wish to insert more key value pairs but this time we're actually going to pick a probing function that works so that we don't ever have any issues so I'm going to pick the table size to be 12 and our probing function to be 5x so no cycle should occur all right so let's go with inserting the first guy so suppose that K1 has a hash value of 10 then at index 10 we get to put K1 V1 suppose K2 has a hash value of eight then slot 8 free so let's pop those right in there so I'll now suppose K3 is equal to 10 oh hash collision with K one in there so we need to keep probing all right so if we use our probing function which is p of X = 5x so that'll give us 3 modul n when we add it to the hash value move not insert K4 now suppose the hash value for K4 is 10 then we have to keep probing so then we hit K3 which we inserted last time and then oh we also hit K2 but we're able to pull out eventually when we hit the third probing value however now notice that we've actually reached the threshold of our table if I go back a few slides we can see that I picked Alpha to be 0.35 so n which is the table size times Alpha gave us four and we just finished inserting the fourth element so it's time that we resize the table so how we usually resize the table is via some exponential fashion such as doubling or tripling or so on but we need to double in such a way that the gcd of N and a still holds so after doubling n is equal to 24 and the gcd property is still good uh Alpha is a constant so it's still 3.5 so our new threshold is just going to be eight and we don't change the pring function all right so let's allocate a new chunk of memory for this new table and now we need to place all the old elements in our old table into this new table using the new table size for n all right so if we scan across all these elements we start at zero nothing there move along so from before we knew that hash value for K4 was 10 so inside the new table it's soon want to go position 10 right scan along nothing here from before you know that K3 was 10 so it should go in position 10 in this new table but we have a hash Collision so we have to keep probing so if we add our probing function at 1 which is 5X then we get 10 + 5 which is 15 so we going to insert it at position 15 in the new table keep probing nothing here nothing here nothing here So eventually we hit K2 so we know from before K2 is equal to 8 uh so we're going to insert at position 8 now we know K1 is equal to 10 so we're going to try and insert at position 10 that's taken so have to probe so the next position is also taken so add five again that gives us 20 so we're K1 V1 at 20 all right so now we throw away the old table and we keep this new table and this is the new hash table we're working with and we were at inserting K5 now suppose K5 is equal to two and that spot is free so we are good so here's a frequently Asked question sweet I know how insertion works now how do I remove key value pairs from the hashtable using open addressing and my answer to this is that this topic is going to Merit its own video and we're going to do it after we see all the other open addressing techniques because it's actually non-trivial all right so guys thank you for watching if you like this video please hit the like button and subscribe and drop a comment see you later