Okay, let's talk about something super, super cool. And that is hash tables and separate chaining. Alright, let's 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 of the same value, we need to have some sort of way of handling that within our hash table. So that's still functional.

Well, what separate chaining does is it maintains an auxiliary 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 link lists for this, but it's not limited to only linked lists. You can use array binary trees, so bouncing trees or even a hybrid approach. Okay, so suppose we have the following hash table, which is 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 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 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 three. So we're going to put in in that slot three, Lia, age 18 hash to four.

Since she has to four, we're going to put her at index four. So the hash is a way to index into the array. Okay, Rick, age 61 hash to put them there. And re age 25 hash one. Okay, we're starting to get a little bit full in our hash table here. So maybe 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 link lists and see if alera exists and if Lera does not exist, then we're going to add a layer at the very end of the chain. Okay, so Ryan also hash to one, but then we look and Ryan is not equal to array, so we need to add a new entry at position one Lera, age 34 hash to four. So, nope, and o layer already existed in our hash table. So we're good. And she says the same age so we don't need to update it. So fin age 21 hash two three.

So easier hash collision with will who has also hash Two, three. So what we're going to do is we're going to append Finn to the end of the length list chain. So note that even though that will and Finn both hashed to same value, that is index three. And they have the same age, we tell them apart because we store both the key and the value as an entry in our linkless 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 linked list at index four 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 we're going to do is given a name we want to find well what the person's age is. So suppose we have Ryan and 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 have to scan this linked list for Ryan. So So Ray No. So here we're comparing the key. So we're comparing the key Ryan to the key array, and there's not a match.

So keep going. Compare Ryan. Ryan, there's a match. Okay, we found Ryan and then inside that entry, you say, oh, his age is 56. So return 56. Okay, 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 found in position four. Okay, so we look in the bucket for scan through. Oh, last one is Mark. So return age 10. So it might happen that the value or the key looking for doesn't think exists and so it doesn't exist the return No. 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 linkless chains? 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 a larger capacity and rehash all your items and re insert them into this new, 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 in the length list.

That's another question. How do I use? Can I use another data structure to model the bucket behavior of separate chaining? Yes, of course. And common data structures using several linked lists include arrays, binary trees, by self balancing trees. And Java uses a hybrid approach in our hash map.

So once they get to a certain chain length, they switch to a binary tree or maybe a self balanced spanning tree I'm not too sure. However, these alternative methods are a bit more memory intensive and complex to implement, which is why they may be less popular, but they might be a lot faster to 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 going to be one@github.com slash will empezar slash do dash structures. And I will also be going over some source code in the next video so stay tuned for that.

Thanks so much for watching. Catch you later