DaniWeb Forum Index > Software Development > C

sucinct example of hash table w/ chaining

Please support our C advertiser: Programming Forums - DaniWeb Sister Site

•

Join Date: Jan 2008

Posts: 14

Reputation: silentdragoon is an unknown quantity at this point

Solved Threads: 0

silentdragoon silentdragoon is offline

Offline

Newbie Poster

sucinct example of hash table w/ chaining

Jan 15th, 2008

Can someone point me towards a dead basic, complete example of a hash table utilising chaining? I've got a working hash function, I am just getting really frustrated with not understanding what I don't understand with the setting up of the hash table. All the examples on the web I've looked at I can't get working, or they seem so complicated; pages and pages of code seeing how well it works, and on various inputs, and I just want something dead simple and transparent, that will not crash when I give it a word.

My understanding is that for the hash table with chaining, you'll need a linked list data structure (which I have working fine) and another data structure, that holds each chain and also an index. So I have something like

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
typedef struct l {
  char* data;
  int numfound;
  struct l *next;
} listelem;
typedef struct l {
  char* data;
  int numfound;
  struct l *next;
} listelem;

for my linked list, which seems to work well, but I am stuck on what to do for the other data structure. Should it be

[code]
typedef struct hashtable {
struct listelem chain;
int index;
} hashtable;

or is that way off base?

The problem I'm having is that I'm developing in Windows at the moment, and when it doesn't work it just crashes, with no inkling of what went wrong, whereas on linux it seems to be easier to catch errors. Or it gives me thousands of errors/warnings on compile, and I can't resolve them.

I've written about three or four insert functions now, using different ideas and bases, and none of them have worked even a little bit. My current m.o. for the insert function is planned thusly:

// 1. hash word, get address
// 2. compare to word in that address, if there is one
// 3. if there is one, check it until next is null
// 4. check by strcmp-ing the data segment and the input string
// 5. if there is no match, add it to the beginning of the chain
// 6. if there is a match, increment the numfound and break

Does that sound reasonable?

Ach. My project is due on Friday and I'm so far behind.. Please help me, good people! I am talking to my tutor tomorrow, hopefully I can get some of this resolved, but I am in a sorry state -- programming six hours a night after an exhausting day just isn't going well. No sleep = no energy = sloppy programming = staying up to fix errors = no sleep, etc.

sad face.

•

Join Date: Oct 2006

Posts: 2,958

Reputation: niek_e has a reputation beyond repute

Solved Threads: 307

niek_e

Offline

Cenosillicaphobiac

Re: sucinct example of hash table w/ chaining

Jan 16th, 2008

These are questions for Narue. You could have a look at this Tutorial she wrote : link

[edit] Looking futher below in the threadlist, I saw that you allready asked this question in this thread and got the same answer... Sorry 'bout that

Niek

Last edited by niek_e; Jan 16th, 2008 at 5:04 am.

•

Join Date: Jan 2008

Posts: 14

Reputation: silentdragoon is an unknown quantity at this point

Solved Threads: 0

silentdragoon silentdragoon is offline

Offline

Newbie Poster

Re: sucinct example of hash table w/ chaining

Jan 16th, 2008

Even that tutorial has too much going on, I need something far simpler -- if such a thing exists.

•

Join Date: Sep 2004

Posts: 7,813

Reputation: Narue has a reputation beyond repute

Solved Threads: 747

Narue

Offline

Senior Bitch

Re: sucinct example of hash table w/ chaining

Jan 16th, 2008

Here's as simple as it gets with separate chaining, with some rudimentary testing. I wrote it in a few minutes, so don't blame me if there are bugs.

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct node {
  char *data;
  struct node *next;
} node;
 
unsigned djb_hash ( const void *key, int len )
{
  unsigned const char *p = key;
  unsigned h = 0;
  int i;
 
  for ( i = 0; i < len; i++ )
    h = 33 * h ^ p[i];
 
  return h;
}
 
static int find ( const node *table[], int size, const char *key )
{
  unsigned index = djb_hash ( key, strlen ( key ) ) % size;
  const node *it = table[index];
 
  /* Find a matching key in the list, if any */
  while ( it != NULL && strcmp ( it->data, key ) != 0 )
    it = it->next;
 
  return it != NULL;
}
 
static int insert ( node *table[], int size, const char *key )
{
  if ( !find ( table, size, key ) ) {
    /* Find the linked list we want to search */
    unsigned index = djb_hash ( key, strlen ( key ) ) % size;
 
    node *new_node = malloc ( sizeof *new_node );
 
    if ( new_node == NULL )
      return 0;
 
    new_node->data = malloc ( strlen ( key ) + 1 );
 
    if ( new_node->data == NULL )
      return 0;
 
    /* Fill in the data and link to the front of the list */
    strcpy ( new_node->data, key );
    new_node->next = table[index];
    table[index] = new_node;
 
    return 1;
  }
 
  return 0;
}
 
#include <assert.h>
 
int main ( void )
{
  node *table[101] = {0};
 
  assert ( insert ( table, 101, "test" ) == 1 );
  assert ( find ( table, 101, "test" ) == 1 );
  assert ( insert ( table, 101, "test" ) == 0 );
  assert ( find ( table, 101, "foo" ) == 0 );
 
  return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
  char *data;
  struct node *next;
} node;

unsigned djb_hash ( const void *key, int len )
{
  unsigned const char *p = key;
  unsigned h = 0;
  int i;

  for ( i = 0; i < len; i++ )
    h = 33 * h ^ p[i];

  return h;
}

static int find ( const node *table[], int size, const char *key )
{
  unsigned index = djb_hash ( key, strlen ( key ) ) % size;
  const node *it = table[index];

  /* Find a matching key in the list, if any */
  while ( it != NULL && strcmp ( it->data, key ) != 0 )
    it = it->next;

  return it != NULL;
}

static int insert ( node *table[], int size, const char *key )
{
  if ( !find ( table, size, key ) ) {
    /* Find the linked list we want to search */
    unsigned index = djb_hash ( key, strlen ( key ) ) % size;

    node *new_node = malloc ( sizeof *new_node );

    if ( new_node == NULL )
      return 0;

    new_node->data = malloc ( strlen ( key ) + 1 );

    if ( new_node->data == NULL )
      return 0;

    /* Fill in the data and link to the front of the list */
    strcpy ( new_node->data, key );
    new_node->next = table[index];
    table[index] = new_node;

    return 1;
  }

  return 0;
}

#include <assert.h>

int main ( void )
{
  node *table[101] = {0};

  assert ( insert ( table, 101, "test" ) == 1 );
  assert ( find ( table, 101, "test" ) == 1 );
  assert ( insert ( table, 101, "test" ) == 0 );
  assert ( find ( table, 101, "foo" ) == 0 );

  return 0;
}