[dekhn]

A hash table in C is about 30 lines of code, so I don't think you have to stick to linked lists for dictionaries.

[threeducks]

9 lines seem to be sufficient (assuming string keys and int values).

    // Hashtable definition
    #include <string.h>
    #define N 1024
    int* map_ptr(const char **keys, int *values, const char *key){
        size_t h = 0, c = 0, i;
        for (const char *c = key; *c; c++) h = h * 33 + *(unsigned char*)c;
        for (i = h % N; c < N && keys[i] && 0 != strcmp(keys[i], key); i = (i + 1) % N, c++);
        if (!keys[i]) keys[i] = key;
        return 0 == strcmp(keys[i], key) ? &values[i] : NULL;
    }

    // Example usage
    const char *keys[N];
    int values[N];

    #include <stdio.h>

    int main(){
        // Set some values
        *map_ptr(keys, values, "one") = 1;
        *map_ptr(keys, values, "two") = 2;
        *map_ptr(keys, values, "three") = 3;

        // Retrieve values
        printf("one: %i\n", *map_ptr(keys, values, "one"));
        printf("two: %i\n", *map_ptr(keys, values, "two"));
        printf("three: %i\n", *map_ptr(keys, values, "three"));

        return 0;
    }

[ludocode]

Indeed, a decent closed hash table is maybe 30 lines. An open hash table with linear probing is even less, especially if you don't need to remove entries. It's almost identical to a linear search through an array; you just change where you start iterating.

In my first stage Onramp linker [1], converting linear search to an open hash table adds a grand total of 24 bytecode instructions, including the FNV-1a hash function. There's no reason to ever linear search a symbol table.

[1]: https://github.com/ludocode/onramp/blob/develop/core/ld/0-gl...

[bluGill]

a linear search may be faster because it is cache and branch prediction frienly. Benchmarks on real world data is needed to make a final call.

[bluGill]

Sure but a linear search is 5. when my limit is 500 lines of C I don't dare spare those lines.