# Hash Table implementation in C using linear probing for collisions

I've written a simple Hash Table implementation in C, in order to use it in an IRC bot, so mostly storing nicknames, channel names, etc (small strings). I'm using linear probind to resolve collision.

Here is the public API (hash.h):

#pragma once

#include <stdbool.h>

typedef struct hash {
struct hash_node* nodes;
size_t capacity;
size_t size;
} hash_t;

typedef struct hash_node {
char *key;
void *value;
} hash_node_t ;

hash_t* hash_create(size_t capacity);
void hash_destroy(hash_t *hash);

bool hash_set(hash_t *hash, const char *key, void *value);
void* hash_get(hash_t *hash, const char *key);



And here is the implementation (hash.c):

#include <stddef.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

#include "hash.h"

// Implementation of the 64 bits version of the FNV1-a hashing algorithm
static uint64_t hash_fnv1a(const char *str) {
uint64_t hash = UINT64_C(14695981039346656037);
while (*str) {
hash ^= (uint64_t) *str++;
hash *= UINT64_C(1099511628211);
}
return hash;
}

static hash_node_t *hash_node_get(hash_node_t *nodes, size_t nodes_size, const char *key) {
uint64_t index = hash_fnv1a(key) % nodes_size;
hash_node_t *node = &nodes[index];
while (node->key != NULL) {
if (strcmp(node->key, key) == 0) {
return node;
}
if (++index == nodes_size)
index = 0;
node = &nodes[index];
}
// If we did not find this key, we return the node which can be used to store this key.
return node;
}

bool hash_grow(hash_t* hash, size_t new_capacity) {
hash_node_t *new_nodes = calloc(new_capacity, sizeof(hash_node_t));
if (new_nodes == NULL)
return false;
for (size_t i = 0; i < hash->capacity; i++) {
hash_node_t *node = &hash->nodes[i];
if (node->key != NULL) {
hash_node_t *new_node = hash_node_get(new_nodes, new_capacity, node->key);
*new_node = *node;
}
}
free(hash->nodes);
hash->nodes = new_nodes;
hash->capacity = new_capacity;
return true;
}

hash_t *hash_create(size_t capacity) {
hash_t *hash = malloc(sizeof(hash_t));
if (hash == NULL)
return NULL;
hash->size = 0;
hash->capacity = capacity;
hash->nodes = calloc(capacity, sizeof(hash_node_t));
if (hash->nodes == NULL) {
free(hash);
return NULL;
}
return hash;
}

void hash_destroy(hash_t *hash) {
for (size_t i = 0; i < hash->capacity; i++) {
hash_node_t *node = hash->nodes + i;
if (node->key != NULL) {
free(node->key);
}
}
free(hash->nodes);
free(hash);
}

bool hash_set(hash_t *hash, const char *key, void *value) {
hash_node_t *node = hash_node_get(hash->nodes, hash->capacity, key);
if (node->key != NULL) {
node->value = value;
return true;
}

if (hash->size >= hash->capacity / 2) {
if (!hash_grow(hash, hash->capacity * 2)) {
return false;
}
// After growing the hash, the node reference has been freed,
// so we get it again from the new nodes array.
node = hash_node_get(hash->nodes, hash->capacity, key);
}

node->key = strdup(key);
if (node->key == NULL) {
return NULL;
}
node->value = value;
hash->size++;
return true;
}

void *hash_get(hash_t *hash, const char *key) {
return hash_node_get(hash->nodes, hash->capacity, key)->value;
}


I'm mostly satisfied with it, except the hash_grow function which I find a bit complicated to understand. So I asked myself a few questions regarding this implementation:

1. Should I use size_t for my nodes array ? In my case this hash table will never contain a lot of entries, so I could have use a uint32_t because I don't need the extra space on 64 bits architecture. In this case I can use the 32 bits implement of FNV1-a.

2. Is storing the result of the hash_fnv1a hash inside the hash_node_t is useful in order to avoid computing it again in hash_grow ? In this case I would just need to recompute the "modulo" because the key didn't change.

3. I used linear probing to resolve collisions, it's easier and I don't think that for my use case it would make a big difference.

4. My structs are public because I have unit tests (with cmocka) and I need to check internal states in my tests.

I'm a professional developer, but not in C. I do this just for fun, so please don't be too rude with me. Thanks for your comments, I'm really excited to get a review.