Help With Hashtables

**Darkness82** · 04-06-2005

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

**joshdick** · 04-06-2005

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>.

**quzah** · 04-06-2005

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.

**Darkness82** · 04-06-2005

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.

**Darkness82** · 04-06-2005

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

**quzah** · 04-06-2005

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.

**stumpster123** · 04-06-2005

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.

**Darkness82** · 04-07-2005

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

**quzah** · 04-07-2005

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.

**stumpster123** · 04-07-2005

Don't you need to cast the first parameter to (const void *) in fwrite.

**quzah** · 04-07-2005

No.

Quzah.

Thread: Help With Hashtables

Thread Tools

Search Thread

Display

Help With Hashtables

Similar Threads

Hashtables & Unicode