Motivation

I started watching https://www.youtube.com/watch?v=2Ti5yvumFTU and decided to have a go at writing the simplest toy hash table I could before watching the rest of the video. As such, this uses a poor choice of hash function (basically just Xor all the characters), and cannot delete items.

Code Version 2

I've added code to print the table, and to delete entries.

hasht.h

typedef struct _hasht hasht;

hasht* hasht_new(void);
void hasht_print(hasht *h);
void hasht_store(hasht *h, const char* key, char* data);
char* hasht_get(hasht *h, const char *key);
char* hasht_get_default(hasht *h, const char *key, char *def);
char* hasht_delete(hasht *h, const char *key);
int hasht_has(hasht *h, const char *key);

hasht.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "hasht.h"

typedef struct _llnode {
  char* key;
  char* data;
  struct _llnode *next;
} llnode;
typedef struct _ll {
  struct _llnode *head;
} ll;
#define TABLE_SIZE 16
struct _hasht {
  ll bins[TABLE_SIZE];
};
hasht* hasht_new(void) {
  hasht* h = (hasht*)malloc(sizeof(hasht));
  memset(h,0,sizeof(hasht));
  return h;
}
char hasht_hash(const char* key) {
  char x = 0;
  const char *p = key;
  while(*p != 0) {
    x ^= *p;
    p++;
  }
  return x % TABLE_SIZE;
}
llnode* create_llnode(const char* key, char* data) {
  llnode *n = (llnode*)malloc(sizeof(llnode));
  char *key_cpy = (char*)malloc(strlen(key)+1);
  strcpy(key_cpy,key);
  n->key = key_cpy;
  n->data = data;
  n->next = NULL;
  return n;
}
void hasht_print(hasht *h) {
  for(int i=0; i<TABLE_SIZE; i++) {
    llnode *p = h->bins[i].head;
    if( p != NULL ) {
      printf("Bin %d:\n",i);
      while( p != NULL ) {
        printf("  %s => %s\n",p->key,p->data);
        p = p->next;
      }
    }
  }
}
void hasht_store(hasht *h, const char* key, char* data) {
  char hk = hasht_hash(key);
  llnode *p = h->bins[hk].head;
  if( p == NULL ) {
    p = create_llnode(key,data);
    h->bins[hk].head = p;
    return;
  }
  // if we are here, then the list is nonempty
  while( p->next != NULL ) {
    if( strcmp(p->key,key) == 0 ) {
      p->data = data;
      return;
    }
    p = p->next;
  }
  // if we are here, then p points to the last element in the list
  if( strcmp(p->key,key) == 0 ) {
    p->data = data;
    return;
  }
  // if we are here, then then key is not in the table
  p->next = create_llnode(key,data);
  // so now our new element is last in the bin
}
char* hasht_get(hasht *h, const char *key) {
  char hk = hasht_hash(key);
  llnode *p = h->bins[hk].head;
  while(p != NULL) {
    if( strcmp(p->key,key) == 0) {
      return p->data;
    }
    p = p->next;
  }
  return NULL;
}
char* hasht_get_default(hasht *h, const char *key, char *def) {
  char hk = hasht_hash(key);
  llnode *p = h->bins[hk].head;
  while(p != NULL) {
    if( strcmp(p->key,key) == 0) {
      return p->data;
    }
    p = p->next;
  }
  return def;
}
// returns the data from the deleted node so that the caller can free it if necessary
char* hasht_delete(hasht *h, const char *key) {
  char hk = hasht_hash(key);
  llnode *p = h->bins[hk].head;
  llnode *prev = NULL;
  while(p != NULL) {
    if( strcmp(p->key,key) == 0) {
      llnode *q = p->next;
      if( prev == NULL ) {
        h->bins[hk].head = NULL;
        char* data = p->data;
        free(p->key);
        free(p);
        return data;
      } else {
        char* data = p->data;
        prev->next = p->next;
        free(p->key);
        free(p);
        return data;
      }
    }
    prev = p;
    p = p->next;
  }
  return NULL;
}
int hasht_has(hasht *h, const char *key) {
  char hk = hasht_hash(key);
  llnode *p = h->bins[hk].head;
  while(p != NULL) {
    if( strcmp(p->key,key) == 0) {
      return 1;
    }
    p = p->next;
  }
  return 0;
}

test.c

#include <stdio.h>
#include "hasht.h"

int main() {
  char* got;
  hasht* h = hasht_new();

  printf("Insert 3 items\n");
  hasht_store(h, "hello","hello world");
  hasht_store(h, "hex","mr flibble");
  hasht_store(h, "random","turnip");
  hasht_print(h);

  printf("===========\n");
  printf("Get 'hex' default to 'boing'\n");
  got = hasht_get_default(h, "hex", "boing");
  printf("Got %s\n",got);
  printf("Get 'hex' default to NULL\n");
  got = hasht_get(h, "hex");
  printf("Result is null? %s\n",got == NULL ? "yes" : "no");
  printf("===========\n");

  printf("Delete 'hex'\n");
  got = hasht_delete(h,"hex");
  hasht_print(h);
  printf("deleted: %s\n",got);
  printf("===========\n");

  printf("Get 'hex' default to 'boing'\n");
  got = hasht_get_default(h, "hex", "boing");
  printf("Got %s\n",got);
  printf("Get 'hex' default to NULL\n");
  got = hasht_get(h, "hex");
  printf("Result is null? %s\n",got == NULL ? "yes" : "no");
  printf("===========\n");

  printf("Table has 'hex'? %s\n",hasht_has(h,"hex") ? "yes" : "no");
  printf("Table has 'hello'? %s\n",hasht_has(h,"hello") ? "yes" : "no");
}

Compile with

gcc -o test hasht.c test.c

Code Version 1

hasht.h

typedef struct _hasht hasht;
hasht* hasht_new(void);
const char* hasht_get(hasht* h, const char* key);
void hasht_store(hasht* h, const char* key, const char* value);

hasht.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "hasht.h"

typedef struct _llnode {
  const char* key;
  const char* data;
  struct _llnode *next;
} llnode;
typedef struct _ll {
  struct _llnode *head;
} ll;
struct _hasht {
  ll bins[256];
};
hasht* hasht_new(void) {
  hasht* h = (hasht*)malloc(sizeof(hasht));
  memset(h,0,sizeof(hasht));
  return h;
}
char hasht_hash(const char* key) {
  char x = 0;
  const char *p = key;
  while(*p != 0) {
    x ^= *p;
    p++;
  }
  return x;
}
llnode* create_llnode(const char* key, const char* data) {
  llnode *n = (llnode*)malloc(sizeof(llnode));
  char *key_cpy = (char*)malloc(strlen(key)+1);
  strcpy(key_cpy,key);
  n->key = key_cpy;
  n->data = data;
  n->next = NULL;
  return n;
}
void hasht_store(hasht *h, const char* key, const char* data) {
  char hk = hasht_hash(key);
  llnode *p = h->bins[hk].head;
  if( p == NULL ) {
    p = create_llnode(key,data);
    h->bins[hk].head = p;
    return;
  }
  // if we are here, then the list is nonempty
  while( p->next != NULL ) {
    if( strcmp(p->key,key) == 0 ) {
      p->data = data;
      return;
    }
    p = p->next;
  }
  // if we are here, then p points to the last element in the list
  if( strcmp(p->key,key) == 0 ) {
    p->data = data;
    return;
  }
  // if we are here, then then key is not in the table
  p->next = create_llnode(key,data);
  // so now our new element is last in the bin
}
const char* hasht_get(hasht *h, const char *key) {
  char hk = hasht_hash(key);
  llnode *p = h->bins[hk].head;
  while(p != NULL) {
    if( strcmp(p->key,key) == 0) {
      return p->data;
    }
    p = p->next;
  }
  return "";
}

Test program

test.c

#include <stdio.h>
#include "hasht.h"

int main() {
  hasht* h = hasht_new();
  char* item1 = "hello world";
  char* item2 = "mr flibble";
  hasht_store(h, "hello",item1);
  hasht_store(h, "hex",item2);
  printf("1:\n");
  printf("%s %s\n",hasht_get(h, "hello"),hasht_get(h, "hex"));
  hasht_store(h, "hello", "boing");
  printf("2:\n");
  printf("%s %s\n",hasht_get(h, "hello"),hasht_get(h, "hex"));
}