This post shows how to implement a simple hash table of arbitrary length,
allowing to store all values c knows and doing so while being as minimal as
possible. It does however not include collision handling, to implement this,
simply swap the Map.buckets array with an array of linked list and insert
into the linked lists instead of only into the bucket array and you should be
good to go.
1#include <assert.h>
2
3typedef struct Map { size_t size; size_t cap; void **buckets; } Map;
4const size_t BASE = 0x811c9dc5;
5const size_t PRIME = 0x01000193;
6size_t hash(Map *m, char *str) {
7 size_t initial = BASE;
8 while(*str) {
9 initial ^= *str++;
10 initial *= PRIME;
11 }
12 return initial & (m->cap - 1);
13}
14
15Map init(size_t cap) {
16 Map m = {0,cap};
17 m.buckets = malloc(sizeof(void*)*m.cap);
18 assert(m.buckets != NULL);
19 return m;
20}
21
22void put(Map *m, char *str, void *value) {
23 m->size++;
24 m->buckets[hash(m, str)] = value;
25}
26
27void* get(Map *m, char *str) {
28 return m->buckets[hash(m, str)];
29}