Help With Hashtables

This is a discussion on Help With Hashtables within the C Programming forums, part of the General Programming Boards category; Hi all i am a C newbie and need to implement a hash table to store some stuff... its like ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    4

    Unhappy Help With Hashtables

    Hi all i am a C newbie and need to implement a hash table to store some stuff...
    its like this i need to store "strings" that point to some values...

    ie name is the string and the values could be stuff like
    idNum, Age etc

    so i tot i will strut some thing called person...
    with the attributes Name, idNum and Age

    then i want to store all these Persons structs in a Hash Table with the key defined by the Name...i saw several codes online but i cant seem to figure them out can any one help me

    Thanks a million

  2. #2
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    I know you posted this question in the C forum, but if you are able to use C++, that would make things much easier for you by using <string> and <map>.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    First I would suggest you implement the program with something simple, like a linked list. Make your program work so you can look up an entry in the list by its name or value.

    Once you understand how that works, then try reading up on hash tables again. There's no reason to start overly complex. (Hash tables are actually quite simple if you can grasp the hashing concept. But I'd suggest an "easier" implementation first.)

    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    Apr 2005
    Posts
    4
    Quote Originally Posted by quzah
    First I would suggest you implement the program with something simple, like a linked list. Make your program work so you can look up an entry in the list by its name or value.

    Once you understand how that works, then try reading up on hash tables again. There's no reason to start overly complex. (Hash tables are actually quite simple if you can grasp the hashing concept. But I'd suggest an "easier" implementation first.)

    Quzah.
    wow thats a very fast reply indeed...yeah tot of that too but the think is that my code gets rather complex (messy) if i were to use linked lists and stuff...

    so i was thinking maybe i should instead just use an array of structs...hummm that mean my searches will be much slower but will be easier to implement.

  5. #5
    Registered User
    Join Date
    Apr 2005
    Posts
    4
    Quote Originally Posted by joshdick
    I know you posted this question in the C forum, but if you are able to use C++, that would make things much easier for you by using <string> and <map>.

    sorry man c was not my choice either...i used to program in java and other o-o langs b4 now tasked to do something in c so basically i am lost without my APIs and Objects

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Well if you understand a linked list, a hash table can be easily done with an array of linked lists. You do something like this:
    Code:
    struct foo
    {
        struct foo *...pointers to next (optionally to prev) node...
        int key;
        ...data...
    };
    
    struct foo *hastable[ NUMBER_OF_BUCKETS ];
    Now all you do, is "hash" the key to find out what bucket it goes into. Then, just like when you "sort at time of insertion" a normal linked list entry, you do the same here.

    You find the bucket it goes into:
    Code:
    bucket = &hashtable[ toinsert->key % NUMBER_OF_BUCKETS ];
    Now you pass that bucket over to a function along with whatever you're inserting.
    Code:
    insertme( struct foo **bucket, struct foo *toinsert )
    {
        ...insert it in numerical order based on the key (not the hash of the key)...
    }
    The reason you need to pass the address of the bucket is so that you can actually upate the bucket itself. That is to say, if this is NULL, meaning nothing is here right now, or if the value of what there should come after the value that's there already, we need to make this new value the top of this list:
    Code:
    if( hashtable[ HASHED_KEY ] == NULL || hashtable[ HASHED_KEY ]->key > toinsert->key )
    {
        toinsert->next = hashtabhe[ HASHED_KEY ];
        hashtable[ HASHED_KEY ] = toinsert;
    }
    The above was just an illustration of the point. You wouldn't actually do that check implicitly. Rather, since this would be inside a function as listed above, it would be more along the lines of:
    Code:
    if( *bucket == NULL || (*bucket)->value > toinsert->value )
    {
        ...fix it up here...
    }
    At any rate, it's a pretty easy concept if you understand linked lists. Now your search time becomes 1/NUMBER_OF_BUCKETS of the time it would take you to simply run through a standard linked list, because you have it split into NUMBER_OF_BUCKETS lists, and you just run through one of those smaller lists instead of one huge one.

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    High Flyer stumpster123's Avatar
    Join Date
    Mar 2005
    Posts
    26
    You would need a hash function too, that will generate the key.
    Here is a good hash function
    Code:
    int hash_example (char *s, int T)
    {
      int h = 0;
      for (; *s != 0; s++)
        h = (h << 5) ^ (*s) ^ h;
    
      if (h < 0) h = -h;
      return h % T;
    }
    s is the string you want to generate a key for and T is the maximum number you want to go to for the keys.

  8. #8
    Registered User
    Join Date
    Apr 2005
    Posts
    4

    Unhappy

    Hey guys thanks all for you inputs...will go play ard with the codes and get a hashtable out soon (hopefully)

    But a new prob has surfaced...
    I need to write the entire hashtable or for that matter a single struct to a file using a write method that i have in my program:

    the struct itself has a few variables like a Name and 2-3 more attributes. The structs are of fixed size.

    Code:
    void writeDisk(int blkNum, char * string)
    {
        int i;
    
             //writing to the disk
             //clear the contents of the block to be written on
             for(i=0;i<blkSize;i++)
             {
              diskNameMap[blkNum * blkSize + i] = '\0';
             }
       
             //write to the block one byte at a time
             for(i=0;i<blkSize;i++)
             {              
              diskNameMap[blkNum * blkSize + i] = string[i];
             }
             //sync the diskNameMap with diskName
             msync(diskNameMap, length, MS_SYNC);
    
    }// end of writeDisk Method
    basically it writes 1 byte at a time by taking in a char* of max size regulated by the block size

    so basically i have to convert my struct into a char* so i can write it to a file. Is this possible? If so how?

    in pseudo code it is something like:

    1.cast the struct to char*;
    2.then chop it up into the blocksize;
    //(since my method can only write 1 block at a time)
    3.for(i=0;i<sizeof(arrayOfChoppedStruct);i++)
    {
    writeDisk(blkNum+1,arrayOfChoppedStruct[i]);
    }

    so how can i do line 1 in c...thanks all

    Cheers

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Why? Why don't you just use fwrite and write a structure at a time that way?
    Code:
    for( foo = 0; foo < MAX_BUCKETS; foo++ )
        for( bar = firstinthisbucket; bar; bar = bar->next in bucket )
            if( fwrite( bar, sizeof( yourstructure ), 1, fp ) != 1 )
            {
                printf("Write failed.\n");
                return -1;
            }
    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    High Flyer stumpster123's Avatar
    Join Date
    Mar 2005
    Posts
    26
    Don't you need to cast the first parameter to (const void *) in fwrite.

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    No.

    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hashtables & Unicode
    By Cactus_Hugger in forum C++ Programming
    Replies: 4
    Last Post: 07-26-2008, 12:50 PM

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