can anyone pls explain me abt hashed linked list and ways to implement it..??
Printable View
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
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
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?Quote:
Originally Posted by iMalc
Well, the way you make it sound, it's like it's some special kind of hash table. But it's not.Quote:
Originally Posted by AndrewHunter
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.