6
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Mast Mar 31 '18 at 9:37
1
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$ – Dannnno Mar 30 '18 at 18:27
  • \$\begingroup\$ Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. \$\endgroup\$ – Dannnno Mar 30 '18 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.