Thread: developing hash tables in the C Programming language

  1. #1
    Registered User
    Join Date
    May 2008
    Posts
    1

    developing hash tables in the C Programming language

    To Whom It May Concern,

    I am now starting to develop a hash table in C. I was wondering if there are any posts available that will display a very simple hash table developed in the C programming language? I have been having issues with developing my own hash table, since I am not very used to the idea of pointers. Sorry I am more of a Matlab type of individual. I was wondering if there are any examples of source code utilizing only very simple linked-lists to develop a simple Nx2 hash table. I should state that the Nx2, means a hash table with two columns and and arbitrary number of rows.


    Thanks,


    David B W108B

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Using a linked list as the "collision solution" is only one of several options, and you don't really need to use pointers to solve collisions in a hash-table.
    You could for example:
    * Use a non-colliding hash-algorithm [although that's often difficult to achieve for arbitrary data].
    * Use the "go to next[1] position until you find a free/match" when you find a collision. Of course, eventually, if you use a fixed size hash-table, the entire table will be full, and if you have MANY collisions, the algorithm is not very efficient if you have frequent collisions.

    Having said that, if you are serious about programming C, you will soon have to learn about pointers, and linked lists have some tutorials on www.cprogramming.com page. There's also some good algorithmic stuff (general, not just hash/linked list related - make a bookmark!) on the www.eternallyconfuzzled.com page.

    If you go down the route of using buckets with linked list [which is what I did when I wrote a lisp interpreter], then you should start by implementing a basic linked list algorithm which you can add/remove items from the linked list [make sure you test for adding/deleting the first, the last and deleting all items in the list!]

    [1] Next doesn't necessarily mean "add one", it may be add 7 or 42 or whatever number you fancy using - just as long as you use a deterministic method. Using steps bigger than one is useful if it's likely that two neighboring cells are more likely to cause a collision than ones that are far apart.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bernstein hash?
    By audinue in forum C Programming
    Replies: 0
    Last Post: 01-07-2009, 07:24 AM
  2. Language of choice after C++
    By gandalf_bar in forum A Brief History of Cprogramming.com
    Replies: 47
    Last Post: 06-15-2004, 01:20 AM
  3. hash tables
    By ender in forum C++ Programming
    Replies: 0
    Last Post: 05-08-2002, 07:36 AM
  4. hash tables
    By iain in forum C++ Programming
    Replies: 3
    Last Post: 12-08-2001, 04:10 PM
  5. Visual J#
    By mfc2themax in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 10-08-2001, 02:41 PM