I've written a C implementation of a hashmap of strings including the basic operations and a strategy for handling hash collisons.
Additionally, I've included some tests, specifically for cases involving hash collisions which, I confess, gave me a bit of trouble initially.
Thank you in advance for your time :)
ps, if you prefer to view on github: https://github.com/JosephSBoyle/HashMap
hashmap.h
#include <stddef.h>
#include "hashmap.c"
/* Create a hashmap.*/
Node** hm_create(void);
/* Add an item to the hashmap */
void hm_add(Node** hmap, char key[], char value[]);
/* Remove an item from the hashmap */
void hm_del(Node** hmap, char key[]);
/** Get an item from the hashmap
* @returns the value corresponding to 'key' or the terminating character '\0'
* if no such item exists. */
char* hm_get(Node** hmap, char key[]);
hashmap.c
#define BUCKETS 1000000
#define PRIME_SEED_1 17
#define PRIME_SEED_2 97
#define KEY_CHARS 128
#define VALUE_CHARS 128
#define NODE_SIZE sizeof(Node)
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>
/* A key-value node in a single-linked list. */
typedef struct Node Node;
struct Node {
Node* next;
char key[KEY_CHARS];
char value[VALUE_CHARS];
};
Node* create_sentinel_node(){
void* ptr = malloc(NODE_SIZE);
if (ptr == NULL){
exit(EXIT_FAILURE);
} else {
Node* node = (Node*)ptr; // safely typecast the pointer
node->next = NULL;
strcpy(node->key, "\0");
strcpy(node->value, "\0");
return node;
}
}
size_t modular_hash(char* string) {
size_t hash = 0;
for (char* character=string; *character != '\0'; character++) {
hash += ((int)*character + PRIME_SEED_1) * PRIME_SEED_2;
}
return hash;
}
Node** hm_create(void){
static Node* keys[BUCKETS] = {};
for (size_t i=0; i<BUCKETS; i++){
keys[i] = create_sentinel_node();
}
return keys;
}
void hm_add(Node** hmap, char key[], char value[]){
Node* node = hmap[modular_hash(key)];
if (strcmp(node->value, "\0") == 0){
// there's no item in this bucket.
strcpy(node->key, key);
strcpy(node->value, value);
return;
}
while(true){
if (strcmp(node->key, key) == 0){
// the key already exists as a node in the linked list
// so we can simply replace the value.
strcpy(node->value, value);
return;
}
if (node->next == NULL){
// no more nodes, append a new node to the linked list.
void* ptr = malloc(NODE_SIZE);
if (ptr == NULL){
exit(EXIT_FAILURE);
}
Node* new_node = (Node*)ptr; // safely typecast the pointer
new_node->next = NULL;
strcpy(node->value, value);
strcpy(new_node->key, key);
node->next = new_node;
return;
}
node = node->next;
}
}
void hm_del(Node** hmap, char key[]){
size_t khash = modular_hash(key);
Node* node = hmap[khash];
void* prev_node = NULL;
Node* head = node;
// find the node
while (strcmp(head->key, key) != 0){
if (head->next == NULL){
// the key doesn't exist in this hashmap.
return;
}
head = head->next;
prev_node = head;
}
// are we deleting the first node?
if (prev_node == NULL){
// are we deleting the only node?
if (head->next == NULL){
// reset the node to the sentinel node.
strcpy(node->value, "\0");
strcpy(node->key, "\0");
} else {
// we are deleting the first of n>1 nodes.
hmap[khash] = head->next;
}
} else {
// there must be a previous node.
Node* prev_node = (Node*)prev_node;
// is this the last node?
if (head->next == NULL){
prev_node->next = NULL;
} else {
// we are deleting neither the first nor the last node.
prev_node->next = head->next;
}
free(head);
}
}
char* hm_get(Node** hmap, char key[]){
Node* node = hmap[modular_hash(key)];
// skip list elements in the bucket (linked list) that don't match our key.
while (strcmp(node->key, key) != 0){
if (node->next==NULL){
return "\0";
}
node = node->next;
}
return node->value;
}
tests.c
#include "hashmap.h"
/** TESTS
* These tests test the collision handling of the hashmap.
* NOTE: To cause collisions, replace the return value of the hash function with a constant int, e.g `return 0;`
*/
void main(){
// test adding and getting an item
Node** hm0 = hm_create();
hm_add(hm0, "bob", "x");
char* a = hm_get(hm0, "bob");
assert(strcmp(a, "x") == 0);
// test deleting an item that doesn't exist
Node** hm1 = hm_create();
hm_del(hm1, "bob");
char* b = hm_get(hm1, "bob");
assert(strcmp(b, "\0") == 0);
// test getting a deleted item
Node** hm2 = hm_create();
hm_add(hm0, "bob", "the dog");
hm_del(hm2, "bob");
char* c = hm_get(hm2, "bob");
assert(strcmp(c, "\0") == 0);
// test overwriting a value
Node** hm3 = hm_create();
hm_add(hm3, "bob", "foo");
hm_add(hm3, "bob", "bar");
char* d = hm_get(hm3, "bob");
assert(strcmp(d, "bar") == 0);
// test deleting the last item
Node** hm4 = hm_create();
hm_add(hm4, "bob", "foo");
hm_add(hm4, "alice", "bar");
hm_add(hm4, "jane", "baz");
hm_del(hm4, "jane");
char* e = hm_get(hm4, "jane");
assert(strcmp(e, "\0") == 0);
// test deleting an item in the middle of the linked list.
Node** hm5 = hm_create();
hm_add(hm5, "bob", "abc");
hm_add(hm5, "alice", "123");
hm_add(hm5, "jane", "xyz");
hm_del(hm5, "alice");
char* f = hm_get(hm5, "alice");
assert(strcmp(f, "\0") == 0);
printf(
"############################\n"
"----- ALL TESTS PASSED -----\n"
"############################\n"
);
}
```
