Hash table open addressing

Key Takeaways

I'm pretty excited we're going to be talking about the open addressing collision resolution technique for hash tables so let's get going first let's just do a quick recap on hash table so that everyone's on the same page so the goal of the hash table is to construct a mapping from a set of keys to a set of values and the keys need to be hashable now what we do is we define a hash function on the keys to convert them into numbers then we use the number obtained through the hash function as a way to index into the array or the hash table however this is a foolproof method because from time to time we're going to have hash collisions that is two keys that hash to the same value so we need a way to resolve this an open addressing is a solution for that alright so whenever you're going to be using the open addressing collision resolution technique the one thing you need to keep in mind is the actual key value pairs themselves are going to be stored in the table itself so as opposed to say an auxilary data structure like in the separate chaining method we saw in the last video so this means that we care a great deal about the size of the hash table and how many elements are currently in the hash table because once there are too many elements inside the hash table will also be really hard to find an open slot or a position to place our element so just an important piece of terminology we say that the load factor is the ratio between the number of items in the table and the size of the table so this means we need to keep tabs on the load factor here's a neat chart from Wikipedia so on the chart what you can see are two different methods one of them is chaining that is separate chaining and linear probing and open addressing a technique and we can see from the linear probing one is that once it gets to a certain threshold it gets exponentially bad so you don't want to go anywhere near that say point eight mark in fact we're going to be keeping it a lot lower than that usually and what this says is we always need to keep the load factor which we denote by the Greek letter alpha below a certain threshold and we need to grow the size of our table once that threshold is met all right so when we want to insert a key value pair into our hash table here's what we do we take the key we use our hash function to find out our key and we hash the value and this gives us an original position inside the hash table for where the key should go but suppose there's a hash collision and there's already a key in that slot well we can't have two keys in the same slot that's not how arrays work so what we do is we use a probing sequence which I will define as P of X so now on to tell us where to go next so we hashed to the value H of K the original position and now we're going to probe along using this probing function in such a way that we're going to eventually find an open spot along the way so as it turns out there are actually an infinite amount of probing sequences to choose from so here are a few of them we have linear probing which probes via a linear function so given an input parameter X so when we're probing we start usually x at 0 or 1 and as we're unable to find free slots then we just increment X by 1 and it works the same for all of these probing functions for linear probing we use a linear function for quadratic probing we use a quadratic function and then there's double hashing which is super neat actually what we do is we define a secondary hash function on our key find its value and then use that inside the probing function and the last one is the pseudo random number generator probing function that we can use so given a random number generator we're going to seed it using the hash value of our key which we know is deterministic so it's always going to be the same thing and then we can use that inside our probing function which is pretty neat and increment by X each time and we know x increments by one so we're just getting the next number in the random number generator then the next one after that all right so here's a general insertion method for open addressing suppose we have a table size n and here's how the algorithm goes first we initialize X to be 1 so X is a constant or sorry a variable that we're going to use for the probing and we're going to increment X each time we fail to hit a free position then we get the key hash just by hashing our key and that is actually going to be the index where we're going to look at a table first so while the table index is occupied meaning it's not equal to null we're going to say our new index is the key hash or the original position we hash to plus the probing function mod n so that we always land back inside the table and then we're going to increment X so the next time we run this loop while we probe at a different position and then eventually we're going to find a free position we always set up our probing function in such a way that we will always find problems a sorry we will always find a free slot because we know that the load factors been kept below a certain amount alright so here's the big issue with open addressing and it's that most probing sequences that we choose modulo n we're going to end up producing some sort of cycle shorter than the table size itself so imagine you're probing sequence just hops between three different values and cycles and your table is of size 10 but you're only ever able to hit three slots because it's stuck in a cycle and on all of those three slots are full well you're stuck in an infinite loop so this is very problematic and something we absolutely absolutely need to handle all right so somebody looking at an example so right here I have a hash table and that using open addressing and it's got some key value pairs already inserted and assume that the circle of the bar through it is the null token further assume that we're using the probing sequence P of x equals 4x and suppose you want insert a new key value pair into the table and that the key hashes to eight so that means we want to insert that key value pair at position eight but oh it's already occupied because there's key five value five already there so what we do well we probe so we compute P of 1 which is 4 X at 1 so we get 8 plus 4 my 12 well that's 0 so then we go slot 0 and we see oh that is also occupy because the key 1 and value 1 is already there so now we compute P of 2 and then that gives us 16 ma 12 which is 4 then oh that cell is already occupied and then we keep probing and as you see right now we've entered a cycle so we would keep probing and probing and probing and we'd always be getting back to the same position so although we have a proving function it does not work in this particular situation the probing function is flawed so that's quite concerning because not all probing functions are viable they produce cycles which are shorter than the table size how do we handle this and in general the consensus is that we don't handle this issue instead we try to avoid it altogether by restricting the domain of probing functions that we choose to be those which produce a cycle of exactly length n and those probing functions do exist I have a little asterisks here and it says there are a few exceptions and this is true there are some probing functions we can use which don't produce a full cycle but still work and we're going to have a look at I think one of those in the quadratic probing video all right so just to recap technique such as linear probing and quadratic probing double hashing they're all subject to this issue of the cycles and what we need to do is redefine probing functions which are very specific that produce a cycle of length and to avoid not being able to insert an element and being stuck in an infinite loop so this is a bit of an issue with the open addressing scheme but it's something we can handle although notice that this isn't something you have to worry about if you're in the separate chaining world just because we have that auxilary data structure that just captures all our collisions so the next video we're going to be going to great detail on linear probing so guys if you learn something please like this video and subscribe I'll catch you in the next video and dropper comment I always love reading those thank you