Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / General Programming / hash tables... Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
haba

April 20, 2005, 05:01 AM

Hi,

  1.  
  2. #define HASHELEMENTS    10007
  3.  
  4. struct node
  5. {
  6.         int age;
  7.         char name[512];
  8.         struct node *previous;
  9.         struct node *next;
  10. } *hashtable[HASHELEMENTS];
  11.  
  12. void Insert(int age, char name[])
  13. {
  14.         struct node *newhash;
  15.         struct node *currenthash;
  16.         unsigned int hashvalue;
  17.  
  18.         newhash = (struct node *)malloc(sizeof *newhash);
  19.         if(newhash == NULL)
  20.                 return;
  21.  
  22.         newhash->age = age;
  23.         strcpy(newhash->name, name);
  24.  
  25.         hashvalue = hash(name);
  26.  
  27.         if(hashtable[hashvalue] == NULL)
  28.         {
  29.                 hashtable[hashvalue] = newhash;
  30.                 hashtable[hashvalue]->previous = NULL;
  31.                 hashtable[hashvalue]->next = NULL;
  32.         }
  33.         else
  34.         {
  35.                 currenthash = hashtable[hashvalue];
  36.                 while(currenthash->next != NULL)
  37.                         currenthash = currenthash->next;
  38.                 currenthash->next = newhash;
  39.                 newhash->next = NULL;
  40.                 newhash->previous = currenthash;
  41.         }
  42. }
  43.  


this hash table can work with a max of HASHELEMENTS (10007), right? how can I make it work with as many as I want (dynamically) ?
Oh, and another thing: how can I extract (for display or something) all the elements of the hash table?

Huge thanks

 
Corre

April 20, 2005, 05:15 AM

Even though I'm generally in favor of using hash tables, I would suggest that you might be better off using the std::map, which gives similar functionality (key-value look up) but is simpler to get up and running (although not as efficient in every case).

 
haba

April 20, 2005, 05:19 AM

I need to use c ...

 
grelle

April 20, 2005, 05:25 AM

No, it works with as many elements as you want (only limited by available memory).
HASHELEMENTS is the number of 'buckets' in the hash table. Each 'bucket' contains a linked list of elements. And that list can be as long as needed.

To extract all elements:

  1.  
  2. for(int i = 0; i < HASHELEMENTS; i++)
  3. {
  4.    node *pList = hashtable[i];
  5.    while(pList)
  6.    {
  7.       printf("%s: %dn", pList->name, pList->age);
  8.       pList = pList->next;
  9.    }
  10. }
  11.  

 
haba

April 20, 2005, 05:25 AM

this problem is even more serious... because for some names I need to insert... my hash function returns values bigger than the size of the table... :(

 
haba

April 20, 2005, 05:29 AM

this is my hashing function:

  1.  
  2. unsigned hash(char *str)
  3. {
  4.         unsigned hash_value = 0;
  5.  
  6.         for( ; *str; ++str)
  7.                 hash_value = (hash_value << 1) ^*str;
  8.  
  9.         return hash_value;
  10. }
  11.  


how do you explain that for some names that I need to insert (for which hash returns values of the order 10^6), I get 'Object reference not set to an instance of an object' error ...

 
grelle

April 20, 2005, 05:29 AM

Mod the hashvalue with the size of the table, like this:
hashvalue = hashvalue % HASHELEMENTS;

This will give you a value between 0 and HASHELEMENTS - 1 (it's the integer division remainder of 'hashvalue / HASHELEMENTS')

 
grelle

April 20, 2005, 05:32 AM

See my answer below your first post

 
haba

April 20, 2005, 05:35 AM

giant thanks!

 
haba

April 20, 2005, 05:39 AM

just one more thing...
using this hash function, I'm always sure that lower ASCII value keys have lower indices in the table, right?

 
haba

April 20, 2005, 05:49 AM

hmmm.... guess not...
so whats the best way to print all the values, but sorted alphabetically (amybe some hash function that sorts the keys...? how?)?

thanks again

 
haba

April 20, 2005, 06:44 AM

would this hash function work for my purposes?

  1.  
  2. int hash(char *str)
  3. {
  4.    int i=0, n=0;
  5.  
  6.    while(str[i] != '')
  7.    {
  8.       n *= 10;
  9.       n += str[i] - '0';
  10.       i++;
  11.    }
  12.  
  13.    return n % HASHELEMENTS;
  14. }
  15.  


thanks again

 
haba

April 20, 2005, 06:47 AM

hmm... no... it wouldnt :(

any more help?

 
Bramz

April 20, 2005, 07:15 AM

OK, now be honest, where does your problem come from?

 
haba

April 20, 2005, 07:32 AM

i just want to print the keys and values in the table... is there any way to sort these in the table? or do I have to copy the elements to a list, and then sort the list? If so, what is the most efficient algorithm to sort a linked list?

 
grelle

April 20, 2005, 08:31 AM

Hash tables are not used that way. You should store your strings in another structure to be able to sort them. A simple list will work, more efficient structures exist though.
Google 'data structures' and 'algorithms' and you should find a lot of resources on the subject.

 
haba

April 20, 2005, 11:43 AM

thanks for all the help... just one more thing:
I'm inserting stuff in my hash table like this:

  1.  
  2. void Insert(int age, char name[])
  3. {
  4.         struct node *newhash;
  5.         struct node *currenthash;
  6.         unsigned int hashvalue;
  7.  
  8.         newhash = (struct node *)malloc(sizeof *newhash);
  9.         if(newhash == NULL)
  10.                 return;
  11.  
  12.         newhash->age = age;
  13.         strcpy(newhash->name, name);
  14.        
  15.         hashvalue = hash(name);
  16.  
  17.         if(hashtable[hashvalue] == NULL)
  18.         {
  19.                 hashtable[hashvalue] = newhash;
  20.                 hashtable[hashvalue]->previous = NULL;
  21.                 hashtable[hashvalue]->next = NULL;
  22.         }
  23.         else
  24.         {
  25.                 currenthash = hashtable[hashvalue];
  26.                 while(currenthash->next != NULL)   // the problem occurs here
  27.                         currenthash = currenthash->next;
  28.                 currenthash->next = newhash;
  29.                 newhash->next = NULL;
  30.                 newhash->previous = currenthash;
  31.         }
  32. }
  33.  


I'm inserting records from a text file, and I get to a point where I get a Segmentation Fault error, I debuged it (with some printfs) and I found the error occurs where it is marked (in the code up)...

Any help?

Thanks again

 
haba

April 20, 2005, 11:44 AM

thanks for all the help... just one more thing:
I'm inserting stuff in my hash table like this:

  1.  
  2. void Insert(int age, char name[])
  3. {
  4.         struct node *newhash;
  5.         struct node *currenthash;
  6.         unsigned int hashvalue;
  7.  
  8.         newhash = (struct node *)malloc(sizeof *newhash);
  9.         if(newhash == NULL)
  10.                 return;
  11.  
  12.         newhash->age = age;
  13.         strcpy(newhash->name, name);
  14.        
  15.         hashvalue = hash(name);
  16.  
  17.         if(hashtable[hashvalue] == NULL)
  18.         {
  19.                 hashtable[hashvalue] = newhash;
  20.                 hashtable[hashvalue]->previous = NULL;
  21.                 hashtable[hashvalue]->next = NULL;
  22.         }
  23.         else
  24.         {
  25.                 currenthash = hashtable[hashvalue];
  26.                 while(currenthash->next != NULL)   // the problem occurs here
  27.                         currenthash = currenthash->next;
  28.                 currenthash->next = newhash;
  29.                 newhash->next = NULL;
  30.                 newhash->previous = currenthash;
  31.         }
  32. }
  33.  


I'm inserting records from a text file, and I get to a point where I get a Segmentation Fault error, I debuged it (with some printfs) and I found the error occurs where it is marked (in the code up)...

Any help?

Thanks again

 
I'M BRIAN FELLOWS

April 20, 2005, 12:06 PM

ASK YOUR PROFESSOR.

 
Danny Chapman

April 20, 2005, 12:14 PM

One way to debug this kind of stuff is to write a debug version of your hash function that either:

1. always returns 0
or
2. increments and returns a static counter % n
(where n is between 1 and the size of your array).

This way it's a lot easier to step through the code with a piece of paper checking it's doing what you expect it to do.

 
Marmakoide

April 20, 2005, 01:26 PM

1)
Ho please, for your hash function write

  1.  
  2. int
  3. hash(char *str) {
  4.    int result;
  5.  
  6.    result = str++;
  7.    for(char shift = 0; *str != ''; str++, shift++) {
  8.       shift &= 31;
  9.       result += (*str << shift);
  10.    }
  11.  
  12.    return result % HASHELEMENTS;
  13. }
  14.  


It's a bit faster than your version.

2)
And as Brian says in his Brian style, the implementation of a hash table is a school exercise (It don't mean that is trivial or boring) . "The Art of computer programming" contains a full chpater on the subject, with all the details...

 
Victor Widell

April 20, 2005, 06:59 PM

If you need fast access by string indices, you can try the Trie data structure. It is also very simple to print them alphabethically.

My own implementation:
http://www.ds.hj.se/~geon/trie/main.cpp

 
This thread contains 22 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.