hash_table_demo.cpp

#include <stdio.h>
#include <string.h>

const int MAX_HASH_COUNT = 1001;
const int MAX_FREE_NODES = 10000;
const int NOT_FOUND = -1;

struct Bucket {
  int key;
  int value;
  Bucket *next;
};

Bucket *hashTable[MAX_HASH_COUNT];
Bucket freeNodes[MAX_FREE_NODES];
int nextFreeNode = 0;

void hashInit() {
  memset(hashTable, 0, sizeof(Bucket*) * MAX_HASH_COUNT);
  memset(freeNodes, 0, sizeof(Bucket) * MAX_FREE_NODES);
}

void hashSet(int key, int value) {
  Bucket **node = &hashTable[key % MAX_HASH_COUNT];
  while (*node && (*node)->key != key) {
    node = &((*node)->next);
  }
  if (!(*node)) {
    *node = &freeNodes[nextFreeNode++];
    (*node)->key = key;
  }
  (*node)->value = value;
}

int hashGet(int key) {
  Bucket *node = hashTable[key % MAX_HASH_COUNT];
  while (node && node->key != key) {
    node = node->next;
  }
  if (node) {
    return node->value;
  } else {
    return NOT_FOUND;
  }
}

#define assert(c) { \
  if (!(c)) { \
    printf("Assertion failed: %s\n", #c); \
  } \
}

int main() {
  hashInit();
  for (int i=1; i<=10; ++i) {
    assert(hashGet(i) == NOT_FOUND);
    assert(hashGet(i + MAX_HASH_COUNT) == NOT_FOUND);
    hashSet(i, i);
    assert(hashGet(i) == i);
    assert(hashGet(i + MAX_HASH_COUNT) == NOT_FOUND);
    hashSet(i + MAX_HASH_COUNT, i + MAX_HASH_COUNT);
    assert(hashGet(i) == i);
    assert(hashGet(i + MAX_HASH_COUNT) == i + MAX_HASH_COUNT);
  }

  for (int i=1; i<=10; ++i) {
    printf("hash[%d] = %d, hash[%d] = %d\n", 
      i, hashGet(i), i + MAX_HASH_COUNT, hashGet(i + MAX_HASH_COUNT));
  }
  return 0;
}