lang/c/ ToyHashTable1

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

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"));
}