Hash table separate chaining

Key Takeaways

okay let's talk about something super super cool and that is hash tables and separate chaining all rights dive right in what is separate chaining so separate chaining is just one of many many hash collision resolution techniques and how it works is when there's a hash collision meaning two keys hash to the same value we need to have some sort of way of handling that within our hash table so it's still functional well what separate chaining does is it maintains an auxilary data structure to essentially hold all the collisions and so we can go back and look up inside that bucket or that data structure of values for the item we're looking for and usually we use the linked list for this but it's not limited to only linked lists can use arrays binary trees cell balancing trees or even a hybrid approach okay so suppose we have the following hash table it's just a fancy name for an array of key value pairs of age and names and we associate an arbitrary hash value that has been computed with some hash function so those are our hash values they don't really matter for now we're just going to see how we can use separate chaining to handle the collisions okay so on the left is our hash table so our array and I'm going to be inserting all of these key value pairs into this hash table via separate chaining and you'll see how easy it is okay so our first person is will his ages 21 and he hashed to 3 so we're going to put him in that slot 3 Leah age 18 hash to 4 since she has to 4 we're going to put her at index for so the hash is a way to index into the array okay Rick age 61 hash to going to put them there and Ray age 25 hash one okay we're starting to get a little bit full in our hash table here so make some collisions pretty soon okay lera age 34 hash to four but we say oh shoot leah is already there what do we do well in separate chaining we just chain along so essentially each each position in the array is actually a linked list data structure so we're going to scan through the linked list and see if Alera exists and if Lehrer does not exist then we're going to add lera at the very end of the chain okay so Ryan also hash to one but then we look and Ryan is not equal to R a so we need to add a new entry at position one al era age 34 hash to four so nope and Oh layer already existed in our hash table so we're good and she has the same age so we don't need to update it so thin age 21 hash to 3 so easy our hash collision with will who has also hash to 3 so what we're going to do is we're going to append sin to the end of the length less chain so note that even though that will and Finn both hashed to same value that it'll index 3 oh and they have the same age we tell them apart because we store both the key and the value as an entry in our linked list block so that's how we're able to tell them apart okay now I want insert mark whose age is 10 and who has to four so scan through the link list at index 4 for mark and he's not found so we have to append mark at the very end all right now let's have a look at how we can do lookups in this structure so it's basically the same thing so what we're going to do is give it a name we want to find well what the person's age is so suppose we have Ryan Ryan when we hash and we get one so we suspect that Ryan should be in bucket one when I say a bucket I just mean whatever data structure we're using at index one and in our case a linked list so I just scan this linked list for Ryan so start right now so here we're comparing the key so we're comparing the key Ryan to the key array and there's not a match to keep going compare right Ryan there's a match okay we found Ryan and then inside that and true say oh his age is 56 so returned 56 let's do another one find the age of Mark hash mark and since our hash functions are deterministic we know that if there's a mark then it's going to be fine in position four okay so we look in the bucket for scan through oh last one is a mark so we return age 10 so it might happen that the value or the key looking for doesn't exist and so it doesn't exist you turn now okay so here's a good question how do we maintain a constant time insertion and lookup time complexity if the hash table gets really full and I have some long linked list chains good question and the answer is that once there's a lot of elements within your hash table you'll actually want to create a new hash table with the larger capacity and rehash all your items and reinsert them into this new a larger table because tables are fixed size okay and another good question how do I remove key value pairs from my hash table with separate chaining well the answer is basically the same procedure you hash your key and instead of doing a lookup well you would remove particular entry and the length list that's it another question how do I use can I use another data structure to model the bucket behavior of such a mean yes of course and clumb data structures that are used inside a linked list include arrays binary trees up by self balancing trees java uses a hybrid approach in our hash map so once we get to a certain chain length they switch to a binary tree or maybe a self balance by a tree I'm not too sure however these alternative methods are a bit more memory intensive and complex to implement which is wighting maybe less popular but they might be a lot faster - I haven't actually implemented them myself so have a look at those okay so that's it for this video next video we're going to be going over hash tables with open addressing which I'm really excited about the guys if you want an implementation of a hash table with separate chaining there's joint be one at github.com slash will infuse a slash dated - structures and I will also be going this or some source code in the next video so stay tuned for that thanks so much for watching catch you later