Hash Table

A complete, dependency-free string-keyed hash table in classic chained-bucket style - public-domain code by Jerry Coffin (with improvements by HenkJan Wolthuis), which makes it ideal for dropping into your own projects. The API is small and readable: ConstructTable allocates the bucket array, TableInsert stores a key/value pair (copying the key, not the data), TableLookup retrieves it, TableDelete removes it and hands back the data so you can dispose of it, EnumerateTable calls a callback over every entry, and FreeTable tears everything down, optionally calling a per-entry cleanup function. Use it when you need a fast string-to-pointer map in plain C without pulling in a library.

#ifndef HASH__H
#define HASH__H

#include <stddef.h>           /* For size_t     */

/*
** A hash Table consists of an array of these Buckets.  Each Bucket
** holds a copy of the Key, a pointer to the Data associated with the
** Key, and a pointer to the next Bucket that collided with this one,
** if there was one.
*/

typedef struct Bucket {
    char *Key;
    void *Data;
    struct Bucket *Next;
} Bucket;

/*
** This is what you actually declare an instance of to create a Table.
** You then call 'construct_Table' with the address of this structure,
** and a guess at the Size of the Table.  Note that more nodes than this
** can be inserted in the Table, but performance degrades as this
** happens.  Performance should still be quite adequate until 2 or 3
** times as many nodes have been inserted as the Table was created with.
*/

typedef struct HashTable {
    size_t Size;
    Bucket **Table;
} HashTable;

HashTable *ConstructTable(HashTable *Table,size_t Size);

void *TableInsert(char *Key,void *Data,struct HashTable *Table);

void *TableLookup(char *Key,struct HashTable *Table);

void *TableDelete(char *Key,struct HashTable *Table);

void EnumerateTable(struct HashTable *Table,void (*func)(char *,void *));

void FreeTable(HashTable *Table, void (*func)(void *));

#endif /* HASH__H */

The heart of the implementation is the hash function and the insert path:

#include <string.h>
#include <stdlib.h>

#include "headers/hash.h"

/*
** public domain code by Jerry Coffin, with improvements by HenkJan Wolthuis.
*/

static void (*function)(void *) = (void (*)(void *))NULL;
static HashTable *the_Table = NULL;


HashTable *ConstructTable(HashTable *Table, size_t Size)
{
      size_t i;
      Bucket **temp;

      Table -> Size  = Size;
      Table -> Table = (Bucket * *)malloc(sizeof(Bucket *) * Size);
      temp = Table -> Table;

      if ( temp == NULL )
      {
            Table -> Size = 0;
            return Table;
      }

      for (i=0;i<Size;i++)
            temp[i] = NULL;
      return Table;
}


/*
** Hashes a string to produce an unsigned short, which should be
** sufficient for most purposes.
*/

static unsigned hash(char *string)
{
      unsigned ret_val = 0;
      int i;

      while (*string)
      {
            i = *( int *)string;
            ret_val ^= i;
            ret_val <<= 1;
            string ++;
      }
      return ret_val;
}


void *TableInsert(char *Key, void *Data, HashTable *Table)
{
      unsigned val = hash(Key) % Table->Size;
      Bucket *ptr;
      // ... walks the chain at Table->Table[val], replaces existing keys,
      //     or mallocs a new Bucket at the head of the chain ...
}

And a driver showing the whole lifecycle - construct, insert six entries, look them all up, delete them all, free:

#include <Windows.H>
#include <WindowsX.H>
#include <Stdio.H>
#include <Stdlib.H>

#include "Headers/Hash.C"

int main(int argc, char *argv[])
{

	HashTable Table;

	char *strings[] = {
	 "First",
	 "Second",
	 "Third",
	 "Fourth",
	 "Fith",
	 "Sixth",
	 NULL
	};

	void *Result;

	ConstructTable(&Table,200);

	TableInsert("0", strings[0], &Table);
	TableInsert("1", strings[1], &Table);
	TableInsert("2", strings[2], &Table);
	TableInsert("3", strings[3], &Table);
	TableInsert("4", strings[4], &Table);
	TableInsert("5", strings[5], &Table);

//	EnumerateTable(&Table, printer);

	printf("%s\n",TableLookup("0", &Table));
	printf("%s\n",TableLookup("1", &Table));
	printf("%s\n",TableLookup("2", &Table));
	printf("%s\n",TableLookup("3", &Table));
	printf("%s\n",TableLookup("4", &Table));
	printf("%s\n",TableLookup("5", &Table));


	TableDelete("0",&Table);
	TableDelete("1",&Table);
	TableDelete("2",&Table);
	TableDelete("3",&Table);
	TableDelete("4",&Table);
	TableDelete("5",&Table);

	FreeTable(&Table, NULL);


	return 0;
}

The header comment's sizing advice is worth keeping: the constructor takes a guess at the table size, and performance stays fine until you insert roughly two to three times that many entries. Pass free as the second argument to FreeTable when your values are heap-allocated.