map3.c

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

typedef struct Entry {
    char* key;
    void* value;
    int   next;
} Entry;

typedef struct Map {
    int    capacity;
    int    growth;
    int    count;
    int*   entries;
    Entry* pool;
} Map;

Map* newMap(int capacity, int growth) {
    Map* map = (Map*) malloc(sizeof(Map));
    map->capacity = capacity;
    map->growth = growth;
    map->count = 0;
    map->entries = (int*) calloc(capacity, sizeof(int));
    map->pool = (Entry*) calloc(capacity, sizeof(Entry));
    return map;
}

unsigned _hash(Map* map, char* key) {
    unsigned hash;
    for (hash = 0; *key; key++)
        hash = *key + 31 * hash;
    return hash % map->capacity;
}

void* get(Map* map, char* key) {
    int entry;
    for (entry = map->entries[_hash(map, key)]; entry; entry = map->pool[entry - 1].next)
        if (!strcmp(key, map->pool[entry - 1].key))
            return map->pool[entry - 1].value;
    return 0;
}

void put(Map* map, char* key, void* value) {
    int entry;
    unsigned hash;
    if (map->count == map->capacity) {
        map->capacity *= map->growth;
        free(map->entries);
        map->entries = (int*) calloc(map->capacity, sizeof(int));
        map->pool = (Entry*) realloc(map->pool, map->capacity * sizeof(Entry));
        for (entry = 0; entry < map->count; entry++) {
            hash = _hash(map, map->pool[entry].key);
            map->pool[entry].next = map->entries[hash];
            map->entries[hash] = entry + 1;
        }
    }
    hash = _hash(map, key);
    for (entry = map->entries[hash]; entry; entry = map->pool[entry - 1].next)
        if (!strcmp(key, map->pool[entry - 1].key)) {
            map->pool[entry - 1].value = value;
            return;
        }
    entry = map->count++;
    map->pool[entry].key = key;
    map->pool[entry].value = value;
    map->pool[entry].next = map->entries[hash];
    map->entries[hash] = entry + 1;
}

#include <stdio.h>
#include <windows.h>

double now() {
    double frequency;
    double counter;
    QueryPerformanceFrequency((LARGE_INTEGER*) &frequency);
    QueryPerformanceCounter((LARGE_INTEGER*) &counter);
    return counter / frequency;
}

#define MAX 100000

void main() {
    Map* map = newMap(MAX, 1);
    int i;
    double start;
    double putd;
    double getd;
    double ovrd;

    char* keys[MAX];
    for (i = 0; i < MAX; ++i)
    {
        char* key = (char*) malloc(32);
        sprintf(key, "%d", i);
        keys[i] = key;
    }

    start = now();
    for (i = 0; i < MAX; ++i)
        put(map, keys[i], (void*) (i * 10));
    putd = now() - start;

    start = now();
    for (i = 0; i < MAX; ++i)
        get(map, keys[i]);
    getd = now() - start;

    start = now();
    for (i = MAX - 1; i > -1; --i)
        get(map, keys[i]);
    ovrd = now() - start;

    printf("%s\n", __FILE__);
    printf("test %d\n", get(map, keys[MAX - 1]));
    printf("put %f\n", putd);
    printf("get %f\n", getd);
    printf("ovr %f\n", ovrd);
}

Growing hash map. What costy is rehashing. Caching the hash doesn't improve the speed.