Hash table open addressing code

Key Takeaways

all right today we're going to be having a look at some source code for a hash table that uses open addressing as a collision resolution scheme and you can find all the source code on github at William Sousa slash data structures and then just go to the hash table folder to find a whole bunch of hash table implementations I have three different open addressing implementations here and particularly we have a quadratic probing linear probing and double hashing they're all very similar to each other so I will only be looking at one right now but if you're curious you can go on github and check them out for yourself the one that's really different or slightly more different is the double hashing but other than that they are really essentially the same thing so today I've decided that we're going to have a look at the quadratic probing file so let's dive into the code all right here we are inside the code for the hash table that uses quadratic probing so let's dive right in so I have a class called hash table quadratic probing and notice that it takes in two generic types K and V so this is the key type and this is the value type so you're going to specify these when you instantiate an object which is a hash table for quadratic probing so I have a bunch of instance variables that we're going to need the first is the load factor so this is going to be like the maximum load factor that we're willing to tolerate the current capacity of our hash table the maximum threshold we're willing to tolerate the modification count this is for the iterator next I have two instance variables that keep track of the total number of buckets being used and the key count which tracks the number of unique keys are currently inside hash table now since we're doing open addressing we are storing these key value pairs directly inside an array so instead of having one array with a wrapper class for an entry I've decided just allocate two different arrays one for keys and one for values it makes the code a lot easier and shorter actually okay this is just an instance variable we're going to be using or rather setting when we call the get method so this is the tombstone I was talking about in the last video this is the marker we're going to be using for deletions so every time we delete an entry we're going to mark it with a tombstone and we know this tombstone object is unique all right so these are just some default constants so whenever you want to initialize a hash table without any parameters you can use these constants so this is a default load factor I set it pretty low but you can change it up as you like so you can visualize it with our default capacity and this is a designated constructor so let's have a look so the capacity can't be negative or zero and I check if the user passed in some sort of a weird load factor because we don't want that so then set the max value for the load factor then calculate the capacity and to ensure that the capacity is a power of two I need to essentially round up the capacity so that's going to be with this method next to power essentially it it finds the power of two that is just above this current number or it will also take the default capacity which itself is a power of two so we don't have to worry about that so either way it's going to give power of two then we compute the threshold which is just load factor times the capacity and initialize our tables all right so let's get rolling so this is the quadratic probing function I chose so P of X so you give it the variable X and then we compute x squared plus X divided by 2 so this is really important method the normalized index so given a hash value it essentially strips the negative sign and mods by the capacity so it dumps our hash value inside the domain 0 to the capacity not inclusive this is a clear method this is pretty self-explanatory just a clearly content to the cat of the hash table and start fresh and some helper methods sighs get the key count and check if our hash table is empty and put at an insert or essentially all the same method so let's look at the insert method this inserts a key value pair inside the hash table or update a value if the key already exists all right we don't want to allow null Keys that happens we throw an exception if the number of buckets use is greater than or equal to the threshold were tolerating we're going to resize the table before doing anything else otherwise we want to calculate the hash value from the key using the built-in hashcode method and you can override this for your particular object okay now I need to explain what I J and X are so I is going to be the current index or @ in the hash table because we're going to be bouncing around this I value is going to change a lot then J is the position of the first tombstone we encounter if we encounter one otherwise it's minus 1 and we're going to be using this for an optimization and then X is just the probe offset which I've set to 1 initially okay so this is a do-while loop it's a little long but it's pretty easy to understand alright so first we check in the key table have we hit a tombstone if we have and j is equal to minus one that means we haven't hit tombstone yet so save where we found this tombstone okay so this next check checks if the key table has an entry that's not null meaning there's a key inside of it so we have to check if the key re exists in the hash table so that's what this does it compares the current key at index I with the key we're trying to insert this key and if j is equal to minus 1 meaning we haven't hit tombstone then just update the value if we've hit a tombstone then we want to do a swap with the tombstone and up the modification count and always return like the old value that was there before just just the case won't use it all right next up the current cell is no so we can do an insertion Oh so J is equal to minus 1 means that we haven't seen a tombstone so far so increment number of use buckets and a key count and then store our key value pair otherwise we have a seen a tombstone instead of inserting where your element I where the null event is inserted where the deleted token was found so we're inserting at J instead of I so here we're inserting at I but stay with and sorry J with tombstone is and we're going to return null because there was nothing there before okay and if if we do a loop so we get through all these if statements and we haven't returned that means that we need to keep probing we had a hash collision and we the cell we landed on or I have something in it so we need to probe so we need to offset where we first originally has to plus the probing index or the probe position and increment X at the same time so this will just hop the next spot and we do this while we haven't found an empty slot and we will find them to slot all right so it contains key and has key just check if I key exists within the hash table and to do this I'm being pretty lazy and I'm just calling the get method and I'm setting an instance variable in there called contains flag which gets set to true or false whether keys inside of hash table or not because the highest key in the get method would look would have essentially the same code so that's a bad code smell all right so let's look at the get method since it's getting used in the hash key method so same kind of setup find the original hash index is equal to the hash set J and X to what they were before so essentially do all the same stuff or mostly except set the flag so that's different we set the flag to be true when we identify that the key is indeed inside the hash table and here our else condition is just shorter we return if we hit a null cell instead of inserting a new element and set the contains flag to be false okay so pretty easy and the remove method is actually quite a bit shorter interestingly so the same setup checks the key is now find the hash set X to be equal to one here we don't really care about tombstones too much so we don't have a J position so we're going to start the hash index and quadratically probe until we find a spot so for every loop we're going to increment I or find a new offset position if this loop gets completed so here's what we do we ignore tombstones so we just skip over those so this happens if the key was not found in the hash table we can return null otherwise the key we want to remove is in the hash table and we can do this check because we check for Tinnell before so we're not going to get a null pointer so decrement the key count up the modification count extract the old value and dump it tombstones here and just wipe whatever value is in there so this is where we set the tombstones in the remove method and then just return the old value for good measure all right and okay these two methods are pretty self-explanatory they just return all the keys and return all the values are contained within our hash table so the next really interesting method is this resize table method so this is this gets called when we're inserting new elements and we need to grow the table size and remember that in this particular quadratic probing implementation we always need the capacity to be a power of two but since we know that the capacity is already a power of two multiplying by two will keep it a power of two so that's fine so recompute the new threshold allocate some new memory for a new table I called it old table but it's actually going to be the new table shortly so here I are kind of interesting maneuver here I swapped the current table that is a smaller table with this new table which I call it old table in order to be able to call the insert method down here we'll get to that so swap the key tables swap the value tables reset the key count and the bucket count and this reason I called it old key table was because since the swap well the the new table is actually the current pointer for what was the old table that I might sound confusing but I'm using the table we had before to do insertions on or the pointer to it alright so loop through the old table values and if we encounter a token or a pointer that's not know and not a tombstone and we want insert it so because we're ofwhat waiting in reinserting tombstones we're getting rid of all the tombstones so even though our table might have been cluttered with tombstones we're just getting rid of all of them here alright so that's that the iterate here you can probably have a look at this yourself it's just looping through all the keys and returning on one out of time that's a pretty standard teucer method so that's how you do quadratic probing with open addressing guys if you learn something like this video and drop a comment thank you so much for watching