All right, I know a lot of you have been anticipating the Remove video for how we remove elements from a hash table using the open addressing scheme. So let's have a look first at what issues there are when we remove elements, if we do it naively, I think this is valuable. So suppose that we have an originally empty hash table, and we're using a linear probing function. So P of x is simply going to be equal to x. And we want to perform the following operations we want to insert three keys, k one, k two and K three, and then remove k two and then get the value of k three after. And for the sake of argument, let's assume that we have a hash collision between K one k two and K three all equal to one, this is a possible scenario.

So let's insert them. So k one hashes to one. So we're going to insert at position one. So let's insert k two. So it has a hash collision with K one which is already in the table. So we're going to linearly probe, so insert it in the next slot over.

That's insert key three. It also hashes to one. So let's probe Okay, another hash collision. So let's keep probing and finally we insert it in position three. Now, we are going to remove k two and we're going to use the naive removing method where we're just going to clear the contents of the bucket to find k two, we hash K to get one, but k one is not equal to k two. So we haven't found the element yet.

So then we probe and then we have found k two. So we're just going to remove it, like so. Alright, now let's query the table and obtain the value for K three. Let's see what happens. So when we hash k three, we get one. And k one is not equal to k three.

So let's continue the search. And then we have no element. So what does this mean? So since the value in the bucket at index two is no, we're forced to conclude that k three does not exist within the hash table. Otherwise, we would have encountered it before reaching the null position. That's how finding an element works inside a hash table.

So this method is clearly flawed. The naive removing method doesn't work because k three clearly exists within hash table. We can see it there. And in index three. So here's a solution to the removing. When we remove an element, we're going to place a unique marker called a tombstone, instead of a no element to indicate that a specific key value pair has been deleted or removed.

And when we're doing a search, we're just going to skip over the tombstones. So let's replace the deleted bucket with a tombstone like we should have done and see what happens when we now search for the key k three. Okay, so hash tag three hashes to one. So k one, cycle two, k three to keep probing, all right, we hit a tombstone, so we know that that element was deleted. So keep probing. Alright, we have found k three, and we can return its value v three as our answer for the search.

Awesome. Okay. So a quick question about tombstones. I have a lot of tombstones cluttering my hash table, how do I get rid of them? So the thing with tombstones is that we're actually going to count them as filled slots in the hash table. So they're going to increase the load factor.

And they'll all be removed when we resize the hash table. But there's also another way to get rid of them is that when we insert a new key value pair, then we can replace the buckets that have tombstones with the new key value pair. Now I want to give you guys an example of how it's done. Alright, suppose this is our hash table of size eight, and we're using the quadratic probing function, p of x equals x squared plus x divided by two. And let's see how tombstones come into play during this when we want to Do a lookup. So suppose we want to insert the key k seven inside the hash table and the hash value for K seven is five.

So we're trying to find the key k seven. So k seven, hash to five. So we check their first case seven, this cycle, the K four. So let's keep probing. So we probe quadratically. And we're just going to go the next slot over and that's position six.

Now, position six is special because it's the first position we encounter which has a tombstone in it. So we were going to want to store this position for later to perform an optimization. Okay, keep probing because five k seven yet. So when we pro at position two, we go to position one. Still no case ever Because every tombstones we have keep going. Alright, hit and yeah, another tombstone.

So let's keep probing, and Aha, we have found our key k seven. So we can return the value v seven. Now, however, we can do an optimization because we don't want to probe an additional four times to find k seven, because we just hit a bunch of tombstones along the way. So an optimization we can do is to relocate the key value pair k seven v seven to the first position where there was a tombstone. So that next time we do a look up, it'll be much faster. We call this lazy deletion or lazy relocation.

Alright, so we replace the first tombstone there with K seven v seven. Now we have two copies of that key value pair. So we're going to Want to replace the old one with an old token? Okay. And that was removing. So guys, if you liked this video and learn something, please give it a thumbs up.

And in the next video, we're going to finally be having a look at some hash table source code. The source code can be found at the link at the bottom of the page also in the description and github.com slash when she's slash data data structures, guys, thanks again for watching.