A hash table at its simplest is just an array. The hash function turns whatever your key is into an index for the array and that is where you store the item. The problem is that a hash function rarely gives every key a unique index, so hash tables aren't always simple arrays. They either have ways of choosing a different index that can be easily and reproducibly probed later, or multiple items are placed at the same index in a linked list or other dynamic data structure. Here is a quick and dirty implementation of the latter:
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 53
struct hl_hnode {
char data[BUFSIZ];
struct hl_hnode *next;
};
struct hl_hnode *table[N];
unsigned hash ( const char *s )
{
unsigned h;
for ( h = 0; *s != 0; s++ )
h = *s + 37 * h;
return h % N;
}
char *hl_probe ( const char *key )
{
struct hl_hnode *it;
for ( it = table[ hash ( key ) ]; it != NULL; it = it->next ) {
if ( strcmp ( it->data, key ) == 0 )
return it->data;
}
return NULL;
}
void hl_insert ( const char *key )
{
unsigned h;
struct hl_hnode *new_node;
/* Disallow duplicates */
if ( hl_probe ( key ) != NULL )
return;
/* Hash data */
h = hash ( key );
if ( ( new_node = malloc ( sizeof *new_node ) ) == NULL )
return;
strcpy ( new_node->data, key );
new_node->next = table[h];
table[h] = new_node;
}
