Coding Interview Practice: Hashmap

hashmap.c

#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <string.h>
#include <stdio.h>

/*
 * Lessons learnt:
 * - need semicolon after struct declaration
 * - calloc accepts size_t and number of elements as separate parameters
 * - check levels of indirections in Hashmap struct
 * - strlen doesn't include the null termination character
 */

/*
 * A bin represents a unique (key, value) pair stored in a single bin of
 * a Hashmap.  Since multiple pairs can be assigned to a single bin, they are
 * connected by a linked list structure.
 */
struct Bin
{
    char *key;
    char *value;
    struct Bin *next;
};

/*
 * A Hashmap is a linked list of bins.  The capacity determines the maximum
 * value of the key.
 */
struct Hashmap
{
    size_t capacity;
    struct Bin *bins;
};

/*
 * Allocate a new bin on the heap.  Will trigger an assertion on 
 * out-of-memory.
 */
struct Bin *
bin_new(char *key, char *value);

/*
 * Allocate the bins for the specified Hashmap.  Assumes the Hashmap is
 * allocated, but currently uninitialized.
 */
void
hashmap_init(struct Hashmap *map, size_t capacity);

/*
 * Insert the specified (key, value) pair into the Hashmap.
 * If an item with the specified key already exists, it will be overwritten.
 */
void
hashmap_insert(struct Hashmap *map, char *key, char *value);

/*
 * Retrieve the value with the specified key from the Hashmap.  If it is not
 * found, returns 0.  If it is found, sets the value.
 */
int
hashmap_retrieve(struct Hashmap *map, char *key, char **value);

/*
 * Calculate the hash value for a key.
 */
size_t
hash_key(char *key);

struct Bin *
bin_new(char *key, char *value)
{
    struct Bin *p = calloc(sizeof(struct Bin), 1);
    assert(p);
    p->key = key;
    p->value = value;
    return p;
}

void
hashmap_init(struct Hashmap *map, size_t capacity) 
{
    assert(map);
    map->bins = calloc(sizeof(struct Bin), capacity);
    assert(map->bins);
    map->capacity = capacity;
}

void
hashmap_insert(struct Hashmap *map, char *key, char *value)
{
    size_t idx;
    struct Bin *current = NULL;
    char *heap_value = NULL;
    char *heap_key = NULL;

    assert(map);
    assert(key);
    assert(value);

    heap_value = calloc(sizeof(char), strlen(value) + 1);
    assert(heap_value);

    strcpy(heap_value, value);
    idx = hash_key(key) % map->capacity;
    if (!map->bins[idx].key)
    {
        //
        // This is an empty bin.  Initialize it.
        // The +1 is to account for the null termination character, which isn't
        // counted by strlen.
        //
        map->bins[idx].key = calloc(sizeof(char), strlen(key) + 1);
        assert(map->bins[idx].key);
        strcpy(map->bins[idx].key, key);
        map->bins[idx].value = heap_value;
        return;
    }
    for (current = &map->bins[idx]; current->next; current = current->next)
    {
        //
        // Overwrite existing value.
        //
        if (strcmp(current->key, key) == 0)
        {
            free(current->value);
            current->value = heap_value;
            return;
        }
    }
    heap_key = calloc(sizeof(char), strlen(key) + 1);
    strcpy(heap_key, key);
    current->next = bin_new(heap_key, heap_value);
}

int
hashmap_retrieve(struct Hashmap *map, char *key, char **value) 
{
    size_t idx = hash_key(key) % map->capacity;
    struct Bin *current = &map->bins[idx];
    if (!current->key)
    {
        //
        // This is an empty bin.
        //
        return 0;
    }
    for (; current; current = current->next)
    {
        if (strcmp(current->key, key) == 0)
        {
            *value = current->value;
            return 1;
        }
    }
    return 0;
}

size_t
hash_key(char *key)
{
    size_t hash = 0;
    int i;
    for (i = 0; i < strlen(key); ++i)
        hash = (hash << 4) + key[i];
    return hash;
}

int
main(void)
{
    /*
     * Assign a random integer to each word in the system dictionary.
     * For a single word ("hello"), print the random integer during assignment.
     * Finally, fetch the integer for that word from the hashmap.
     * Since the fetched integer is the same, the map functions correctly.
     */
    char random[256];
    char line[256];
    FILE *fin = NULL;
    char *value = NULL;
    struct Hashmap map;
    int ret;
    hashmap_init(&map, 65535);

    fin = fopen("/usr/share/dict/words", "r");
    assert(fin);
    for (;;)
    {
        fgets(line, 256, fin);
        if (feof(fin))
            break;
        sprintf(random, "%d", rand());
        if (strcmp("hello\n", line) == 0)
            printf("in:\tmap[\"hello\"] = \"%s\"\n", random);
        hashmap_insert(&map, line, random);
    }
    fclose(fin);
    
    ret = hashmap_retrieve(&map, "hello\n", &value);
    assert(ret);
    printf("out:\tmap[\"hello\"] = \"%s\"\n", value);
    return 0;
}

Makefile

CFLAGS=-ggdb -Wall

all: hashmap.out

# $< the dependencies
# $@ the target
hashmap.out: hashmap.o
	gcc -Wall -ggdb $< -o $@

clean:
	rm -rf *.out *.o