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 {{c 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 {{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 {{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"));

}}}