I like that your demonstration starts from an empty hash table. But what happens if the first 4 elements in the first bucket are all odds and you're trying to add a 5th odd element to the hash table? Thanks.
We will split the bucket. All five will end in the odd bucket and we will split again. We keep doing this until we split the elements into two buckets or we reach the maximum size of the table.
There are two answers to this: First, hash tables tend to grow more than shrink, so often we do nothing special when we delete. We just delete. However, if we want to shrink the table as well as grow it, we can do every operation, just in reverse. Splits, become merges (find the split image and merge it), and directory grows become directory shrinks if the global depth exceeds all local depths.
great video ! but at around 12:00 , you made a split. I didn't get how can we select how to split the pointers between the old bucket and the new one. can you help please
This is the best video on Extendible Hashing on RUclips. Covers everything correctly and efficiently.
Thank you for your patient explanation! It saved much of my time.
Very well explained. Thanks a lot! This might save me some trouble in the exam today.
I like that your demonstration starts from an empty hash table. But what happens if the first 4 elements in the first bucket are all odds and you're trying to add a 5th odd element to the hash table? Thanks.
We will split the bucket. All five will end in the odd bucket and we will split again. We keep doing this until we split the elements into two buckets or we reach the maximum size of the table.
@@chrismarriott-CS Okay, so it could take multiple splits for the new pair to be inserted. Thanks again!
What happened to 26? Should that not be placed in the first bucket after you split it?
It belongs in the bottom bucket with 14, 2 and 30 after the split (since this bucket ends 10).
@@chrismarriott-CS ahh ye I see, thx for the answer.
Thank you so much.
what if we have to delete the values from the hash table?how will that effect the local depth?
There are two answers to this: First, hash tables tend to grow more than shrink, so often we do nothing special when we delete. We just delete. However, if we want to shrink the table as well as grow it, we can do every operation, just in reverse. Splits, become merges (find the split image and merge it), and directory grows become directory shrinks if the global depth exceeds all local depths.
if after deletion there is nothing in the bucket, you need to combine them back
@@JaspreetSingh-bd4zo okk Jessica!
great video ! but at around 12:00 , you made a split. I didn't get how can we select how to split the pointers between the old bucket and the new one. can you help please
We are using mod 4 to move the entries into the 0 or 2 bucket.
thank you :D
thank you :)