An HashTable implementation written in C.

hashtable.c

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

typedef char* Key;
typedef char* Value;

typedef struct BucketValue {
    /** The key that matches this entry. */
    Key key;

    /** The value that matches this entry. */
    Value value;

    /** The next bucket value with the same hash. */
    struct BucketValue *next;

    /** If this bucket is initialized. */
    bool initialized;
} BucketValue;

typedef struct HashTable {
    /** How many buckets there are. */
    size_t bucket_amount;

    /** An array of buckets. Keep in mind that bucket valuess point to the next
     * value, while this is an array of buckets themselves. */
    struct BucketValue **buckets;
} HashTable;

static size_t hash_key(Key key) {
    size_t hash = 5381;
    int c;

    while ((c = *key++) != 0)
        /*       hash * 33          + c */
        hash = ((hash << 5) + hash) + c;

    return hash;
}

void bucketvalue_free(BucketValue *bucket_value) {
    if (bucket_value) {
        if (bucket_value->next != NULL) {
            bucketvalue_free(bucket_value->next);
        }

        free(bucket_value);
    }
}

HashTable *hashtable_new(size_t bucket_amount) {
    HashTable *hashtable = malloc(sizeof(HashTable));
    hashtable->bucket_amount = bucket_amount;
    hashtable->buckets = calloc(sizeof(BucketValue*), bucket_amount);

    for (size_t i = 0; i < hashtable->bucket_amount; ++i) {
        hashtable->buckets[i] = calloc(sizeof(BucketValue), 1);
    }

    return hashtable;
}

void hashtable_free(HashTable *hashtable) {
    for (size_t i = 0; i < hashtable->bucket_amount; ++i) {
        bucketvalue_free(hashtable->buckets[i]);
    }

    free(hashtable);
}

void hashtable_insert(HashTable *hashtable, Key key, Value value) {
    size_t key_hash = hash_key(key);
    size_t index = key_hash % hashtable->bucket_amount;
    struct BucketValue *bucket = hashtable->buckets[index];

    while (true) {
        if (!bucket->initialized || strcmp(bucket->key, key) == 0) {
            bucket->key = key;
            bucket->value = value;
            bucket->initialized = true;
            return;
        }

        if (bucket->next) bucket = bucket->next;
        else break;
    }

    BucketValue *new_bucket = malloc(sizeof(BucketValue));
    new_bucket->key = key;
    new_bucket->value = value;
    new_bucket->initialized = true;
    bucket->next = new_bucket;
}

Value hashtable_get(HashTable *hashtable, Key key) {
    size_t key_hash = hash_key(key);
    size_t index = key_hash % hashtable->bucket_amount;
    BucketValue *bucket = hashtable->buckets[index];

    while (bucket) {
        if (bucket->initialized && strcmp(bucket->key, key) == 0) {
            return bucket->value;
        }

        bucket = bucket->next;
    }

    fprintf(stderr, "Could not find key '%s' in hashtable.", key);
    exit(EXIT_FAILURE);
}

void hashtable_print(HashTable *hashtable) {
    printf("{");
    for (size_t i = 0; i < hashtable->bucket_amount; ++i) {
        for (BucketValue *bucket = hashtable->buckets[i]; bucket; bucket = bucket->next) {
            printf("\"%s\": \"%s\"", bucket->key, bucket->value);
            if (bucket->next) printf(", ");
        }
    }
    printf("}");
}

int main(void) {
    HashTable *hashtable = hashtable_new(1);
    hashtable_insert(hashtable, "foo", "bar");
    hashtable_insert(hashtable, "spam", "ham");
    hashtable_print(hashtable);
    hashtable_free(hashtable);
}

/* hashtable ala k&r
 *   NULL indicates an error.
 */


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


#define HASHSIZE 100


typedef struct hashtable
{
    struct hashtable *next;
    char *key;
    char *value;
} hashtable;


uint64_t
hash (char *s)
{
    uint64_t value;
    for(value = 0; *s != '\0'; s++)
        value *= *s + 31;
    return value % HASHSIZE;
}


hashtable *
get (hashtable *table[], char *key)
{
    hashtable *ht;
    for (ht = table[hash(key)]; ht->key != NULL; ht = ht->next)
        if (strcmp(key, ht->key) == 0)
            return ht;
    return NULL;
}


hashtable *
insert (hashtable *table[], char *key, char *value)
{
    hashtable *ht;
    if ((ht = get(table, key)) == NULL) {
        ht = (hashtable *) malloc(sizeof(*ht));
        if (ht == NULL || (ht->key = strdup(key)) == NULL)
            return NULL;
        uint64_t hashvalue = hash(key);
        ht->next = table[hashvalue];
        table[hashvalue] = ht;
    } else {
        free(ht->value);
    }
    ht->value = strdup(value);
    if ((ht->value = strdup(value)) == NULL)
        return NULL;
    return ht;
}


void
table_print(hashtable *table[])
{
    putchar('{');
    putchar('\n');

    for (int i = 0; i < HASHSIZE; i++) {
        if (table[i])
            printf("    %s: %s,\n", table[i]->key, table[i]->value);
    }

    putchar('}');
    putchar('\n');
}


int
main ()
{
    hashtable *mytable[HASHSIZE];

    insert(mytable, "hello", "world");
    insert(mytable, "a whole new", "world");

    char *did_i_do_it = get(mytable, "hello")->value;
    char *aladdin = get(mytable, "hello")->value;

    table_print(mytable);
    printf("%s\n", did_i_do_it);
    printf("%s\n", aladdin);
    return 0;
}

/* hashtable ala k&r
 *   NULL indicates an error.
 */


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


#define HASHSIZE 100


typedef struct hashtable
{
    struct hashtable *next;
    char *key;
    char *value;
} hashtable;


uint64_t
hash (char *s)
{
    uint64_t value;
    for(value = 0; *s != '\0'; s++)
        value *= *s + 31;
    return value % HASHSIZE;
}


hashtable *
get (hashtable *table[], char *key)
{
    hashtable *ht;
    for (ht = table[hash(key)]; ht->key != NULL; ht = ht->next)
        if (strcmp(key, ht->key) == 0)
            return ht;
    return NULL;
}


hashtable *
insert (hashtable *table[], char *key, char *value)
{
    hashtable *ht;
    if ((ht = get(table, key)) == NULL) {
        ht = (hashtable *) malloc(sizeof(*ht));
        if (ht == NULL || (ht->key = strdup(key)) == NULL)
            return NULL;
        uint64_t hashvalue = hash(key);
        ht->next = table[hashvalue];
        table[hashvalue] = ht;
    } else {
        free(ht->value);
    }
    ht->value = strdup(value);
    if ((ht->value = strdup(value)) == NULL)
        return NULL;
    return ht;
}


void
table_print(hashtable *table[])
{
    putchar('{');
    putchar('\n');

    hashtable *ht;
    for (int i = 0; i < HASHSIZE; i++) {
        if (table[i]->key)
            printf("    %s: %s,\n", table[i]->key, table[i]->value);
        for(ht = table[i]->next; ht != NULL; ht = ht->next)
            printf("    %s: %s,\n", ht->key, ht->value);
    }

    putchar('}');
    putchar('\n');
}


int
main ()
{
    hashtable *mytable[HASHSIZE];
    for (int i = 0; i < HASHSIZE; i++)
        mytable[i] = malloc(sizeof(hashtable));

    insert(mytable, "hello", "world");
    insert(mytable, "a whole new", "world");
    insert(mytable, "1 + 2", "3");
    insert(mytable, "hello", "overwrite");
    table_print(mytable);

    return 0;
}