Hash Table Open Addressing Removals

[@WilliamFiset-videos]

For more context, a tombstone in the video really represents the key-value pair: (tombstone, null) where tombstone is some unique value/pointer.

[@WilliamFiset-videos]

As pointed out by @theSomething in the last example I should have replaced the key-value pair (k7, v7) with a tombstone instead of a null token.

[@sahilsingh1]

Can you please add this to the video description or in the pinned comment? Will be easier for people to find.

[@DrunkJackal]

I just ran into this problem last night when I noticed my hash table was incorrect after removal. Thank you for this!

[@MrMadplaya]

Really underrated for such well made videos. Pretty everything I needed on hashing, thanks.

[@Wolfwuf]

For a second i thought i was listening to charlie (moistcritical) lol Thanks for the video, very concise and clear.

[@thesomething8467]

You can't just replace the old position with null. It might cause premature termination when looking up values

[@WilliamFiset-videos]

theSomething Can you elaborate? FYI I'm not allowing keys to be null.

[@thesomething8467]

In the last example. There could be a key with the same hash as k7 after k7

[@WilliamFiset-videos]

So something is definitely wrong. I believe I should have placed a tombstone instead of a null value, oops! Thanks for pointing this out.

[@jonathanharoun5247]

@@WilliamFiset-videos What is a tombstone?

[@bleachedrainbow]

@@jonathanharoun5247 (for anyone new to this thread) A tombstone tells the retrieval function for the hash table that the index has been "previously used" so that it can continue looking for the key. Otherwise it will just assume that the key does not exist in the hash table.

[@johanliebert5179]

awesome videos. i have never got bored watching your videos , excellent presentation.

[@VidushJindal]

❤❤ such a lovely video, understood the concept clearly.

[@alexanderyinyang1436]

I am confused with last part, where you replace first tombstone with k7,v7. With which logic do you find existing k7,v7 cell to replace with tombstone (to remove duplicate)?

[@sofiamorais1366]

Thank you so much 🙏🙏

[@ThanhNguyen-sl2kd]

What if you insert (k3, v3) after remove k2 in the first example, it should be added after k1, but that would be a duplicate of k3

[@Mydad-et1el]

for the last problem, why do we need to keep track of all the tombstone? Don't we just need to know the first tombstone position only? As we will sub k7 into that first tombstone position. So wouldn't keeping track of the other position redundant?

[@mohammadanvary9912]

Very clear and usefull. Thanks :)

[@GauravKumar-sr6bt]

When we relocated k7,v7 from index 7 to index 6, shouldn't we put tombstone at index 7, instead of null? My reasoning for this is that, suppose after inserting k7,v7, and before lookup of k7,v7, we inserted one more element (k8,v8) and it had to skip index 7 while probing because k7,v7 was present there. So after removing k7,v7, we again try to insert k8,v8, it will get inserted at index 7, even though it already exists.

[@bob_jones]

Yep. theSomething mentioned this in a comment way earlier to which WilliamFiset responded and agreed.

[@albertosposito1042]

@@bob_jones But now i'm even more confused, if we replaced a tombstone with another tombstone, just in another position, isn't all of this work useless since it doesn't clear any space in our hash table?

[@saniancreations]

@@albertosposito1042 The point of this optimization is not to remove tombstones, it is to make the lookup of elements with the same hash value faster. Before, it took 5 probes to look up the value. After the swap, it will only take 1. Swapping does not reduce the load factor but it does lower the average lookup time. It's like this: When that element was inserted, the table was a bit more cluttered and we had to place the value far away from its hash index, which makes the lookup take a bit longer. But now that a spot has opened up that is closer to the hash index, the next time we look up this value, we move it there which makes future lookups faster again.

[@rohitsijwali8091]

How the tombstone contribute in load factor? When we remove an element and put a tombstone we can simply decrease number of elements. Is this because in this way we hit threshold earlier so resizetable will get rid of tombstone.

[@mikhailpalagashvili169]

Excellent

[@MrNukenin16]

5:33 voice crack