Open Hashing (Separate Chaining) Collision Resolution in Hash Table/Hashing
HTML-код
- Опубликовано: 24 июл 2024
- This video lecture is produced by S. Saurabh. He is B.Tech from IIT and MS from USA.
What is Open Hashing or separate chaining method in hash table
What is it used for
To study interview questions on Linked List watch • Programming Interviews...
To prepare for programming Interview Questions on Binary Trees
• Programming Interviews...
To study programming Interview questions on Stack, Queues, Arrays visit
• Programming Interviews...
To watch all Programming Interview Questions visit
• Programming Interviews...
To learn about Pointers in C visit
• Pointers in C (All you...
To learn C programming from IITian S.Saurabh visit
• C Programming Tutorial
Very informative - and the length of the video is just right :)
Thanks a lot. I got a better understanding of what Separate Chaining is all about :)
If he is too slow for you speed it up using youtubes speed thingy. I have him set at 1.5x speed and it is much more manageable.
AlteranKing how to use that
dollz T on a computer you can click the gear icon in the bottom right and select change speed. Can't do it on mobile unfortunately
I realize it is pretty off topic but does anyone know a good place to stream newly released movies online?
@Westin Rohan I watch on flixzone. You can find it on google =)
@Roy Victor yea, have been watching on FlixZone for years myself =)
clear explanation.!! Helped me a lot. thank you!!
I could understand the Separate chaining, thank to you
Great video. Thanks
im lucky to have this site for studying
Was very helpful thanks man!
thanks a lot!
excellent!
I didn't think he spoke slowly at all, sometimes when trying to explain a semi-difficult concept, it's important to speak a bit slower than usual. I like his teaching style.
Thanks for the Lecture , As a reciprocation i will click ads and see full length Advertisements on your channel :-)
in open hashing you explained how we allot same index value by linked list,but i want to know that at searching time,how will itgive us exact key @t ,we will simply pass our key to get the value during searching,and that hash function will convert it into a index which having lots of value in form of linked list because of collision,then how will it know the particular value of our key? how will it know there that which value of same index is value of the our key? please do answer
A great video... One question. If we try to insert same value twice wouldn't it be better to first search whether the value is present already?
It depends. If we don't care about duplicates, then we wouldn't want to do that. If we do care about duplicates (like in a "Set") then yes we would want to do that, in which case, hashing is already O(1) and if we find the duplicate value then we just stop.
This is one way only.
Shouldnt O(lamda) be the average case and not the worst case? Worst case should be O(n) right?
In advantages,fourth point should be INsertion is quick and easy and not the deletion. Deletion requires o(lambda) .
hi, what is happening if i want to delete something?
You said o(lambda) as a worst case, i think it is average case and worst case would be o(n) wherein all the keys which we wanna store lands in one bucket. Is it right ?
Yes, you are right.
Hi, why is insertion O(1) let say i wamt to insert at a position that has 15 elements already. Wouldnt i have to run through each element to get to the end and then insert?
@@santi_alvarez Because we are inserting in the head of the linked list and not after the tail
You don't explain the most important part: how do you find data? Using the example at 5.28: if I try to retrieve the value associate with key 81, I get a linked list. How do I know my item is the first one ? And if I try to retrieve the value associated with key 1, I get the same list, how do I know my item is the second one ?
+SimonsMusicChannel It's usually assumed that the data has some sort of unique id which can be used to identify the data - and this is the id that is used to in the hashing algorithm.
In Mr. Saurabh's example, the data he's storing (a value from 1 to 9) ALSO happens to be the data's unique id. The data to be stored could have been anything - customer info, game character inventory, library book information - but each chunk of stored data will need to identifiable with a unique key ... and this key will also be stored in that chunk of data.
When you need to retrieve the info, you provide the unique key. just like storing, the hashing algorithm will generate a hash-table index from this unique key and return a linked list with a number of items in it (could be zero items, could be 5,could be 10, could be n). The retrieval method will search the contents of the returned linked list looking for a data entry with that key. If it finds one, it returns the chunk of stored data.
A hash table is designed to speed up data retrieval and is usually much much more efficient that simply storing it all in a linked list. In the video's example, the WORST CASE search is reduced from a linked list of 9 items to a worst case search of a linked list of 2 items plus the hash lookup.
At this point, people usually ask why not just stick it all in array and use an incremental index? Well, a hash table has the advantage of creating an index out of pretty much any data type or structure (float, char, string, bitmap, etc), squishing the storage space down to not-quite-minimal-but-(potentially)-pretty-close-to-it AND offering relatively rapid retrieval compared to other solutions.
Hash tables are not always the most efficient or the most compact of storage design patterns, but they are flexible and usually a pretty good compromise on speed, space and convenience.
Hope this helps.
+tt rage, thanks for the useful comment, you are a unicorn!
I think I am starting to understand, but bare with me for a second. In the example we have
Keys: 0, 1, 4, 9, 16, 25, 36, 49, 64, 81
1) So key 1 goes to bucket 1 (First node in linked list)
2) More keys are inserted...
3) Key 81 goes to bucket 1 as well (This is the second node. By adding this at the head of the list we now push the old node (1) in second position)
My question is: since the order of the items is completely arbitrary how do I know that:
Key 1 should return what is now the second item ?
Key 81 should return what is now the first item ?
If I understand you correctly you are saying that in each bucket we have another hash function that coverts 1 and 81 to second and first position. But that is not how linked lists work, though. Linked lists are not accessed by index, the are traversed one by one.
So somewhere we have to have a function that converts:
1 --> second item
81 --> first item
Where and how is this info stored?
Thank you, this was helpful nonetheless!
Simon
+SimonsMusicChannel
Not quite - this is where the example given in the video is great in its simplicity but also confusing in its application.
Usually the data you store in the hashtable will be a collection of stuff PLUS some sort of unique identifier. ie.:
int id
int data
The id could be anything that identifies this chunk of info as a wholly unique collection of data ... but for simplicity's sake let's go with an integer (whole number). The data could also be anything - and more often than not is usually a COLLECTION of info, not just one piece of info.
in the video above, both the id AND the data happen to have the same value: id = 9 AND data = 9.
So, when adding our data to the hash table, we give the hashing algorithm our id (9) - which converts it to a hash index ((9x9) % 10 = 81 %10 = 1) - and the data we want to store ... which is also 9. Remember, these are 2 separate bits of information that, in this example HAPPEN to have the same value.
at hash table index (1), we add our chunk of data to the linked list stored there. A previously processed chunk of data had already been added - it had an id of 1 AND a data value of 1. This is what the table looked like before:
hashtable[1]:
first item:
id: 1
data: 1
nextItemInList: NULL
now we add our new chunk of data, the table looks like this:
hashtable[1]:
1st Item:
id: 9
data: 9
nextItemInList: 2nd Item
2nd Item:
id: 1
data: 1
nextItemInList: NULL
You are on the money with the linked list - we do walk them in a linear fashion and query each in turn. When we want to retrieve our data, we give it our id and ask for the data the hash table stored that's associated with that id. So:
we give it an id value of 9
the hashing algorithm turns that into a hash index:
(9x9) % 10
= 81 %10
= 1
we retrieve the linked list at that hash index:
hashtable[1]:
1st Item:
id: 9
data: 9
nextItemInList: 2nd Item
2nd Item:
id: 1
data: 1
nextItemInList: NULL
and we walk the linked list, comparing the id value stored in each linked list item with the one we're looking for until we EITHER run out of nodes (in which case we return NULL) or we find a match, at which point we return the chunk of data.
In this case, the data contains one piece of info, which is an integer and HAPPENS (in this example) to have the EXACT same value as the id we used to retrieve it in the first place.
Hopefully that clears up what's going on, and why the example in the video can be a touch confusing.
Give me a shout if it's still not clear, and I'll try again :D
+SimonsMusicChannel
Heh - you're not ruining my Sunday. It's a pleasant distraction from what I should be doing (writing interview questions) and what I want to be doing (playing Destiny).
So, the hash algorithm can be anything that will take the id (whatever form that could be), converts it to an integer value somehow and then applies a modulus calculation using the number of available slots in the hash-table.
The example hash algorithm that S. Saurabh uses in the video he stipulates at the 0.30 mark, and is:
H(x) = x² (or x-squared if that character doesn't make it up to youtube) % 10
where x is the key (or id) of the data you want to store in the hash table.
+tt rage
Ah, ok, so the MAIN hash function is:
Hash(x) = (x*x) % 10
But then when he talks about lists in buckets around 5:28, he writes:
Hash(x) = (x) % 10
So at that point he is just dealing with the square values and he is worrying about where and how to store then, right ?
OK, so assuming the above is correct, back to the original discussion now.
If I now have to retrieve data 1, which has ID of 1 and it's stored in bucket 1, I need to somehow get to the second linked list item.
To the best of my understanding the process is:
1) Look at root node (ID: 81). Is ID == 1 ? No
2) Ok, try next node. Is ID == 1? Yes, so retrieve value in node which has id 1.
That's what you are saying, right ?
I guess it makes sense and because items in buckets are assumed to be a small number, the additional O(k) is considered negligible.
OK, hopefully, we got it... :-)
Thanks,
Simon
why x^2? I've learned with x mod 10??
Table size is 10
+Tarik Mesanovic its the hash function he chose.
Set the speed to 2.0x. Thank me later :P
4 % 10 = 4 mod 10 = 0
isn't it ? oO
It's the remainder you check, so the answer is 4.
Sarthak Swain THanks
+Alan Naidon 4%10:(remainder of 4/10)
0x4=0.
4-0=4(remainder)
unable to understand....just be quick instead of dragging!!
Hi there,
Just a piece of advice if you'd want,
1. You stretch things a lot, make it quick and to the point, else its boring.
2. Dude, you seriously gotta drop that fake Indian(trying to be American) accent :D let me tell you this, changing just a word in a sentence doesn't make your accent sound any better, either fake the entire sentence or nothing.
Sorry if I sound mean, but umm..I'm just trying to help ya, so that people don't make fun of you behind your back.
Good work though, keep it up !!
My reply is only regarding the accent, as long as it's understandable, it's enough. It's an international language after all. And Sourav has been in USA for studies. So some influence must be there. Also, the Americans by birth and not from Indian origin, will never laugh at pronunciation. It's us, the Indians, who create issues with it.