9 ms·

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.

• ludocode 1y ago
  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-global/ld.oe.ohx https://github.com/ludocode/onramp/blob/develop/core/ld/0-gl...
  • bluGill 1y ago
    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 1y ago
  Sure but a linear search is 5. when my limit is 500 lines of C I don't dare spare those lines.
• threeducks 1y ago
  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; }