A quick hashtable implementation in c.

hash_table.c

#define _XOPEN_SOURCE 500 /* Enable certain library functions (strdup) on linux.  See feature_test_macros(7) */

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include "hash_table.h"

// TODO Write necessary function from http://apr.apache.org/docs/apr/1.4/group__apr__hash.html

int (*ht_hash)(int, char *) = NULL;

int ht_hash_default(int hash_table_size, char *key);
struct Pair *ht_new_pair(char *key, void *value);

/**
 * Creates a new hashtable.
 */
struct HashTable *ht_initialize(int initial_size) {
  struct HashTable *hash_table = NULL;
  int i;

  if (
    initial_size < 1
    // Allocate the table itself
    || NULL == (hash_table = malloc(sizeof(struct HashTable)))
    // Allocate pointers to the head nodes
    || NULL == (hash_table->pairs = malloc(sizeof(struct Pair *) * initial_size))
  ) {
    return NULL;
  }

  for (i = 0; i < initial_size; i++) {
    *(hash_table->pairs + i) = NULL;
  }

  hash_table->size = initial_size;

  // Set default hashing function
  if (NULL == ht_hash) {
    ht_set_hash_function(ht_hash_default);
  }

  return hash_table;
}

/**
 * Sets hashing function.
 */
int ht_set_hash_function(int (*new_hash_function)(int, char *)) {
  if (NULL == new_hash_function) {
    return 0;
  }

  ht_hash = new_hash_function;

  return 1;
}

/**
 * Hash a string for a particular hash table.
 */
int ht_hash_default(int hash_table_size, char *key) {
  unsigned long int key_hash;
  int i = 0,
    key_length = strlen(key);

  // Convert our string to an integer
  while (key_hash < ULONG_MAX && i < key_length) {
    key_hash = key_hash << 8;
    key_hash += *(key + i++);
    //key_hash = (key_hash << 8) + *(key + i++);
  }

  return (key_hash % hash_table_size);
}

/**
 * Create a key-value pair.
 */
struct Pair *ht_new_pair(char *key, void *value) {
  struct Pair *new_pair;

  if (
    NULL == (new_pair = malloc(sizeof(struct Pair)))
    || NULL == (new_pair->key = strdup(key))
  ) {
    return NULL;
  }

  new_pair->value = value;
  new_pair->next = NULL;

  return new_pair;
}

/**
 * Insert a key-value pair into a hash table.
 * If returns NULL that means new pair added, anything other than NULL
 * means that there was an old value by that the given key, it replaced
 * with the new value and the return value is the pointer of the old value.
 */
void *ht_set(struct HashTable *hash_table, char *key, void *value) {
  int bin = ht_hash(hash_table->size, key);
  struct Pair *new_pair = NULL,
    *next = *(hash_table->pairs + bin),
    *last = NULL;
  void *old_value = NULL;

  while (NULL != next && NULL != next->key && strcmp(key, next->key) > 0) {
    last = next;
    next = next->next;
  }

  if (NULL != next && NULL != next->key && 0 == strcmp(key, next->key)) {
    // There's already a pair. Let's replace that string.

    old_value = next->value;
    next->value = value;
  } else {
    // Nope, could't find it. Time to grow a pair.

    new_pair = ht_new_pair(key, value);

    if (next == *(hash_table->pairs + bin)) {
      // We're at the start of the linked list in this bin.

      new_pair->next = next;
      *(hash_table->pairs + bin) = new_pair;
    } else if (NULL == next) {
      // We're at the end of the linked list in this bin.

      last->next = new_pair;
    } else {
      // We're in the middle of the list.

      new_pair->next = next;
      last->next = new_pair;
    }
  }

  return old_value;
}

/**
 * Retrieve the value of pair from the hash table via pair's key.
 */
void *ht_get(struct HashTable *hash_table, char *key) {
  int bin = ht_hash(hash_table->size, key);
  struct Pair *pair;

  // Step through the bin, looking for our value
  pair = *(hash_table->pairs + bin);
  while (NULL != pair && NULL != pair->key && strcmp(key, pair->key) > 0) {
    pair = pair->next;
  }

  return (NULL == pair || NULL == pair->key || 0 != strcmp(key, pair->key))
    ? NULL
    : pair->value;
}

hash_table.h

#ifndef _HASH_TABLE_H_
#define _HASH_TABLE_H_

struct Pair {
  char *key;
  void *value;
  struct Pair *next;
};

struct HashTable {
  int size;
  struct Pair **pairs;
};

struct HashTable *ht_initialize(int initial_size);
int ht_set_hash_function(int (*new_hash_function)(int, char *));
void *ht_set(struct HashTable *hash_table, char *key, void *value);
void *ht_get(struct HashTable *hash_table, char *key);

#endif // _HASH_TABLE_H_

Revision 6 Changelog

• Code style changed as my taste (sorry if it's bothering you)
• Structure tags changed to reflect their purpose
• Type definitions on structures removed to prevent error may occur due to hidden struct keyword
• Hashing function can be set, if not falls back to default one
• Header file added
• Structure definitions moved to header file
• Function prototypes added to header file
• Code file name changed to reflect it's purpose

Revision 7 Changelog

• Table can hold any kind of value (not just string)

Revision 8 Changelog (Fix for Revision 7)

• strdup call removed while creating new pair
• ht_set returns old value's pointer after replacement (if done any)