Hashed linked list

This is a discussion on Hashed linked list within the C++ Programming forums, part of the General Programming Boards category; can anyone pls explain me abt hashed linked list and ways to implement it..??...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    1

    Hashed linked list

    can anyone pls explain me abt hashed linked list and ways to implement it..??

  2. #2
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    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.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    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.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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"

  4. #4
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    Quote Originally Posted by iMalc View Post
    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 anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    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.

  5. #5
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,820
    Quote Originally Posted by AndrewHunter View Post
    Oh ok, so the OP is referring to a hash table where multiple entries can have the same key value...
    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."
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. linked list and damn on linked list
    By St0rM-MaN in forum C Programming
    Replies: 13
    Last Post: 07-03-2007, 04:08 PM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 05:37 PM
  5. Replies: 6
    Last Post: 03-02-2005, 01:45 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21