map.c

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

#define CAPACITY 100000

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

Entry* entries[CAPACITY];

unsigned _hash(char* key) {
    unsigned hash;
    for (hash = 0; *key; key++)
        hash = *key + 31 * hash;
    return hash % CAPACITY;
}

void* get(char* key) {
    Entry* entry;
    for (entry = entries[_hash(key)]; entry; entry = entry->next)
        if (!strcmp(key, entry->key))
            return entry->value;
    return 0;
}

void put(char* key, void* value) {
    Entry* entry;
    unsigned hash = _hash(key);
    for (entry = entries[hash]; entry; entry = entry->next)
        if (!strcmp(key, entry->key)) {
            entry->value = value;
            return;
        }
    entry = (Entry*) malloc(sizeof(Entry));
    entry->key = key;
    entry->value = value;
    entry->next = entries[hash];
    entries[hash] = entry;
}

#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 CAPACITY

void main() {
    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(keys[i], (void*) (i * 10));
    putd = now() - start;

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

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

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

map2.c

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

#define CAPACITY 100000

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

int   entries[CAPACITY];
Entry pool[CAPACITY];
int   count;

unsigned _hash(char* key) {
    unsigned hash;
    for (hash = 0; *key; key++)
        hash = *key + 31 * hash;
    return hash % CAPACITY;
}

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

void put(char* key, void* value) {
    int entry;
    unsigned hash;
    if (count == CAPACITY)
        return;
    hash = _hash(key);
    for (entry = entries[hash]; entry; entry = pool[entry - 1].next)
        if (!strcmp(key, pool[entry - 1].key)) {
            pool[entry - 1].value = value;
            return;
        }
    entry = count++;
    pool[entry].key = key;
    pool[entry].value = value;
    pool[entry].next = entries[hash];
    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 CAPACITY

void main() {
    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(keys[i], (void*) (i * 10));
    putd = now() - start;

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

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

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

map.c
test 999990
put 0.029268
get 0.019293
ovr 0.019203

map2.c is a pooled fixed version of map.c.

map2.c
test 999990
put 0.016348
get 0.017738
ovr 0.017845