can anyone pls explain me abt hashed linked list and ways to implement it..??
can anyone pls explain me abt hashed linked list and ways to implement it..??
Do you know what a hash table is? A hashed linked list is basically an array of nodes where in indeces are referenced via a hash table.
See: Hash Table wiki and Prelude's Hash Table Tutorial
Last edited by AndrewHunter; 09-21-2011 at 01:00 PM.
Originally Posted by anduril462
Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.
The data structure you are probably thinking of does not go by that name. The emphasis would be on the hash table part of it, not on the linked-list part of it.
It's just a "chained hash table".
Hash table - Wikipedia, the free encyclopedia
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
Oh ok, so the OP is referring to a hash table where multiple entries can have the same key value, which is resolved via a node chain per key entry?
Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.
Well, the way you make it sound, it's like it's some special kind of hash table. But it's not.
All hash tables will have collisions (multiple keys having the same hash). Therefore, it needs a way to mitigate that, and one way is by putting a linked list at each bucket.
This is effectively a "chained hash table."
You may also be thinking of an implmentation that does actually store all of the nodes in one continuous list. Each list of items with an equal hash is joined to the list from the next bucket, which makes for easy iteration over the items since you don't have to worry about starting onto the list in the next bucket when you finish with the list in the previous one.
IIRC a std::unordered_map typically works this way.
I've never searched for an implementation of this. But you can either study the one that comes with your compiler or just do your own web searching. In Visual Studio 2008 the interesting bits are inside xhash.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
