hey guys so today we're going to be going over the hash table data structure now there are two different types of hash tables one is called one employs separate chaining and the other employees open addressing these are two different ways to really deal with collisions collisions occur when your key value pair in a hash table or you have multiple keys that have the exact same hash when that happens you need to either rehash a key such that it gets a different and unique hash or what you need to do is you need to say that's acceptable but this key will occupy a distinct space separate from the other key that resulted in the same hash we are going to be looking at separate chaining so using linked lists in order to prevent or rather deal with collisions so let's get started so of course we need our headers and we are going to be using linked lists of Lists include that our linked lists we're going to have a key value pair the key will be integer type and the value will be of string type the reason being is we're going to be using a hash table to implement a phonebook so let's just use a phone number three digit phone number and they're gonna have some of these names so let's say Jenny that's how the key value pair is going to look like so what exactly needs to be inside a hash table well first of all you need to decide how many groups when you're using ace we're using the separate chaining method you decide how many lists you're actually going to use so let's specify that at the beginning so we will have a constant amount of lists and that constant amount is going to be let's say 10 now we're going to have an array that's going to store lists and each list is going to store our pairs that might store no pairs that might have 20 pairs and may have million Paris so how that's going to look is we're going to have an array of type list that will have any there the pair will store a key of type names and a value of type string again we are storing phone numbers and names let's call that a rate table and it's going to be of size and groups cash groups which is 10 pence list 1 is going to be index 0 list 2 index 1 all right now that we understand how that works let's now look at the public functions we need to define there are several public functions but usually the first one you can think about in any data structure is whether that data structure is empty or not so I'll have a bool is update let's make it constant now we also need a hashing function hash table wouldn't be a hash table without that hash function is going to take our key and spit out an integer the next thing we need to do is we need to know how to insert an item now to pour that item we are going to need a key and a value this is considered one item one pair that will be inputted into our list here next we will be learning how to and because each key is distinct and each key only appears once we will only be removing one item when we call this function we also want to be able to search this hash table so what do we want to do to search we want to input a key and receive a string of value in return string search table let's also be a little more expressive and have a print table function that prints the contents of the hashtag awesome start with the easiest thing that's going to be whether it's empty so how do I know whether this hash table is empty well we have a hash table we have a table which is an array of several list objects each list object can have 0 pairs 1 pair as many pairs as it likes so what we need to do is we need to find out whether the cumulative size of each list list 1 lets tell us realist for etc is greater or equal to zero if it's equal to zero well we know that this whole entire hash table is empty if it's greater than zero then we know at least one of these lists has a pair a key value pair so let's call this variable sub now let's say now let's say for a nice lesson hash groups five plus plus you want to go over each hash strips or each list and ask it whether it's empty so we want to sum the size of each list this will give us a list I and we want to find its size now if sum is zero then what we want to do is we want to say yes it's empty sometimes not zero then we want to return false simple let's look at our next function and because there are only ten different lists that we have we want to return a value between zero and nine right arrays are zero zero based so how do we do that well we can simply return the modulus of this key with cash groups so if we have a key that let's say is Nidal five five in return this function will spit out five awesome okay this five will then be the sixth list in this table because this table is an array that's zero based awesome now let's move on to the insert function we need to insert a key and the value as a parent and this is where this gets a little more involved so when we think about it we have an array of lists now we put in a key and we want to put in a value that corresponds that as a pair that key will be hashed so we need a hash value to correspond to that key now whatever the result of this hash will signify which lists this key value pair needs to go into okay so we have a we'll call it a cell which will be the list that we will put in this key value parent to which will really be to the table at a given index awesome now we also need an iterator to the beginning of this list and before we actually go over and iterate upon the list we need to ask ourselves why we're iterating upon it to in the first place why don't we just push this pair into this list but we need to know whether the key that we're inputting exists or not now I'm going to give the program the benefit of the doubt and start it off assuming that this key doesn't exist but we need to validate that everything it sure doesn't exist so we'll be iterating over this respective list to make sure that this key does not exist if it does exist what we want to do is replace the value of that key with this new value that we're inputting just let's do that continues until the end chugs along until it reaches that it now if the first which is the key the key we would like to put in well then what we want to say is yes the key exists we also want to replace the value corresponding to that key then you want to break out of this loop because each key is distinct it will only appear once now let's be expressive and tell the user that a key has been replaced value has been replaced now you want to say okay let's say we've gone over this list and we notice that the key does not in fact exist so if it doesn't exist we want to do is we want to push this key value pair back into that list remember that this cell is indeed the list that we're interested in awesome all right let's look at our remove function our move function is also involved and to some extent mirror is this insert function but it only takes a key because each keys distinct it will either be in the hash table or it will not be in the hash table so let's copy some of this here because the beginning is quite similar you have to find a list of interests and we do so by finding the hash value of the key so give us a list we're interested in and we initiate or initialize an iterator to the beginning of that list we then gave it at the benefit of the doubt by assuming the key does not exist but if it does exist and we'd like to remove that key value pair so we iterate through and if we find this key then we say key does exist and now what we want to do is you want to expunge whatever that iterator is pointing to that key value pair so we use the list to do that we take the cell just a list of interest and we erase what the iterator is pointing to now this will in fact return us an iterator to the next two this will return an iterator to the next iterator of B etter so theater is that position two this will return us an integrator at position three now we can assign it to a new iterator but the fact that we've already gone through the motion we found in erased what didn't need what we needed to erase we can simply just reuse this old iterator because there's no need to continue we've a rate we found that we wanted to and we've erased it so let's just set it to this if we don't set it to something it's very likely will help me we'll have a bug and we will have a we will potentially have a segmentation fault bug even if we don't break so we still want to set the resultant return value of this to something so we're setting it equal to B inner now here we will give them some nice expressive info we will say hey I removed and we will break from this loop now the item wasn't removed then we will say hey and we will simply return cool we have one more function and that is to print everything and this one is also simple but let's think about it first we start off at the first list if the first list is empty there's nothing to print so we should skip it we should continue this process until we printed out everything so we want to do something like this you want to start at the first list so initialize I to zero and we have ten lists so we'll limit it by our hash group the erase index bit as your base so we start with zero and we go up till nine remember hash groups is 10 and we increment the iterator by one each time before awesome now if the size of the list at this position is zero then we want to continue we don't want to go keep keep going through the loop if it's not then hey we want to actually print the contents of that list so what we will do is we will say and we will create an iterator that points to that list beginning of that list and we will iterate through as long as beginner does not equal through and we will say hey I want the key first value of the pair and you value just a second on your fat pair awesome and that's all we need to do to print we can simply return here so as you can see we've implemented a hash table quite conveniently in under 100 lines and now let's put it to the test so we have a main function in our main function you want to create the hash table let's call it HT the first thing we want to do to make sure that our is MP function is correct is check if it's empty if it is indeed empty should return a 1 meaning the correct answer course wants a true let's reward ourselves for doing a good job otherwise now let's insert some stuff in it into the HT and there we go what we're going to do is we're going to insert a couple of names and numbers and since the we're taking modulus 10 really only the last digit matters to determine which list it will be in so just to make it easier on the eyes it's up to me 9 let's just put some random numbers here and we don't want to have a million gins so let's give them random names Tom sandi are now let's also check whether or not our key exists part of our item function works and we're going to insert a different person with the same number and see if that number of that value was later overridden so we will replace Rob with Rick cool now let's print the contents now let's start removing you know what Bob you're gonna bad day you're gonna be removed from our book just to make sure that our remove items is robust enough we will remove a random key that is not in this hash table cool and last but not least we will change check once again if our hash table is empty if it is indeed empty then we've made a mistake because this hash table has more items added to it than it has had removed from it but if it is not empty which means it will trigger false then hey good job awesome so let's give it a spin okay let's review so the list was empty because the correct answer came up this defaulted to one and that's correct good job now the next thing we do is we insert all these items we don't have any message that will tell us whether we've inserted the item or not but we do have a message whether the value of an existing key value pair was overridden as you can see we get the warning message that tells us the value of Rob was replaced with Rick we then printed out our table and we also removed successfully we then tried to remove an item it didn't exist and it told us hey this wasn't found no pair was removed and at the end of all this our hash table was indeed not empty so correct answer was shown that's it for today thanks for listening to the tutorial I hope that helped you I hope you learned a lot if you have any comments feedback questions feel free to email me or message me or leave something in the comments below and I look forward to the next tutorial bye guys