Hash table with separate chaining implementation in C

Question

I'm attempting to implement a hash table with separate chaining in C. It works fine, but is there something that I should optimize, fix or maybe add some features?

hashtable.h

#ifndef HASHTABLE_H
#define HASHTABLE_H


enum data_type {
    INTEGER, FLOAT, DOUBLE,
    CHARACTER, STRING,
    SET, LIST, HASH
};

struct node_t {
    char *key;
    void *value;
    enum data_type type;
    struct node_t *next, *prev;
};

struct hashtable_t {
    int size, used;
    struct node_t **table;
};

struct hashtable_t *create_ht();
void delete_ht(struct hashtable_t *ht);

void ht_insert(struct hashtable_t *ht, char *key, void *value, enum data_type type);
struct node_t *ht_search(struct hashtable_t *ht, char *key);
void ht_delete(struct hashtable_t *ht, char *key);
void ht_update(struct hashtable_t *ht, char *key, void *value, enum data_type type);


#endif // HASHTABLE_H

hashtable.c

#include "hashtable.h"

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

#define HT_INITIAL_SIZE 11


static int hash(char *key, int size) {
    long hash = strlen(key);
    for (int i = 0; i < strlen(key); ++key, ++i) {
        hash = ((hash << 5) ^ (hash >> 27)) ^ (*key);
        hash %= size;
    }

    return (int) hash;
}

static int check_prime(int n) {
    if (n <= 1)
        return 0;

    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0)
            return 0;
    }

    return 1;
}

static int next_prime(int n) {
    while (check_prime(n) != 1)
        n++;

    return n;
}

static struct hashtable_t *create_new_sized_ht(int size) {
    struct hashtable_t *ht = malloc(sizeof(struct hashtable_t));
    ht->table = calloc((size_t) size, sizeof(struct node_t *));
    ht->size = size;
    ht->used = 0;

    return ht;
}

static void resize_ht(struct hashtable_t *ht, int size) {
    if (ht->used > size || size < HT_INITIAL_SIZE)
        return;

    struct hashtable_t *resized_ht = create_new_sized_ht(size);
    for (int i = 0; i < ht->size; i++) {
        struct node_t *nd = ht->table[i], *next;
        while (nd) {
            ht_insert(resized_ht, nd->key, nd->value, nd->type);
            nd = nd->next;
        }
    }

    ht->size = resized_ht->size;

    struct node_t **temp_table = ht->table;
    ht->table = resized_ht->table;
    resized_ht->table = temp_table;

    delete_ht(resized_ht);
}

static void resize_up_ht(struct hashtable_t *ht) {
    int size = next_prime(ht->size * 2);
    resize_ht(ht, size);
}

static void resize_down_ht(struct hashtable_t *ht) {
    int size = next_prime(ht->size / 2);
    resize_ht(ht, size);
}

struct hashtable_t *create_ht() {
    return create_new_sized_ht(HT_INITIAL_SIZE);
}

void delete_ht(struct hashtable_t *ht) {
    for (int i = 0; i < ht->size; i++) {
        struct node_t *head = ht->table[i], *next;
        while (head) {
            next = head->next;
            free(head);
            head = next;
        }
    }

    free(ht->table);
    free(ht);
}

void ht_insert(struct hashtable_t *ht, char *key, void *value, enum data_type type) {
    if (ht->used >= ht->size * 0.80)
        resize_up_ht(ht);

    int h = hash(key, ht->size);

    struct node_t *head = ht->table[h], *prev = NULL;
    while (head) {
        prev = head;
        head = head->next;
    }

    struct node_t *nd = malloc(sizeof(struct node_t));
    nd->key = key;
    nd->value = value;
    nd->type = type;
    nd->prev = prev;
    nd->next = NULL;

    if (prev)
        prev->next = nd;
    else
        ht->table[h] = nd;

    ht->used++;
}

struct node_t *ht_search(struct hashtable_t *ht, char *key) {
    int h = hash(key, ht->size);

    struct node_t *head = ht->table[h];
    while (head) {
        if (strcmp(head->key, key) == 0)
            return head;
        else
            head = head->next;
    }

    return NULL;
}

void ht_delete(struct hashtable_t *ht, char *key) {
    if (ht->used <= ht->size * 0.10)
        resize_down_ht(ht);

    struct node_t *nd = ht_search(ht, key);

    if (nd) {
        if (nd->prev && nd->next) {
            nd->prev->next = nd->next;
            nd->next->prev = nd->prev;
        } else if (!nd->prev) {
            ht->table[hash(nd->key, ht->size)] = nd->next;
        } else if (nd->prev && !nd->next) {
            nd->prev->next = NULL;
        }

        free(nd);
        ht->used--;
    }
}

void ht_update(struct hashtable_t *ht, char *key, void *value, enum data_type type) {
    struct node_t *nd = ht_search(ht, key);

    if (nd) {
        nd->value = value;
        nd->type = type;
    }
}

Answer 1

Yes, there is something you should optimize. I'm going to be brief in this answer.

• Your code is not using inline functions. They are necessary for best possible performance.
• The key and value need to be allocated as separate memory blocks in your solution.
• Your hash table is limited to whatever data types you have defined.
• Your keys must always be strings
• Your hash function is hardcoded and is vulnerable to hash collision attacks unlike e.g. SipHash.

Look at the Linux kernel container_of macro and their implementation of a separately chained hash table. It is the best-performing hash table implementable on the C language. Just don't copy their use of a fixed hash function; allow using some reasonable nearly cryptographically secure hash function like SipHash.

Your hash table is limited to whatever data types you have defined. The key and value also need to be pointers. This limits the operation of the hash table a lot.

In the Linux kernel implementation, you store arbitrary structs and define the hash function and comparison function yourself, so you can decide which parts of the data structure belong to the key and which belong to the value. The Linux kernel implementation also leaves up to the programmer whether duplicate keys are allowed.

Here is the patch that added hash table: https://lwn.net/Articles/510271/

This contains the hash list itself: https://github.com/torvalds/linux/blob/master/include/linux/list.h