[C] Funzione di hashing da 16bit

[MItaly]

Sì, la lista di trabocco è un approccio classico alle collisioni nelle hashtable, ma se hai una funzione di hashing decente le collisioni comunque dovrebbero essere poca roba fino ad un fattore di carico sensato. Inoltre uno svantaggio della lista linkata è che ha località di cache peggiore, per cui spesso si preferisce usare approcci alle collisioni che rimangono all'interno della hashtable.

Anche un trie potrebbe essere una soluzione plausibile a seconda anche della lunghezza delle stringhe

Anche, vale anche lì il discorso della località di cache se le si allocano indipendentemente (anche se volendo uno può comunque tenere tutto in un "piattone" - i nodi vengono allocati in un vettorone con un sistema ad allocatore lineare e al posto dei puntatori - inutilmente grossi - si usano degli indici).

[MItaly]

Ok, ho fatto qualche prova io in C++ con un programma di test di questo tipo:

#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <iostream>
#include <unordered_map>
#include <map>

const int comb_n = 233;
const int tot_count = 172400;

int main() {
    std::string sz = "abcdefghijklm";
    std::vector<std::string> combs;
    for(int i=0; i<comb_n; ++i) {
        std::random_shuffle(sz.begin(), sz.end());
        combs.push_back(sz);
    }

    {
        std::cout<<"Lineare\n";
        std::vector<std::pair<std::string, unsigned>> count_v;
        for(auto &sz: combs) {
            count_v.push_back(std::make_pair(sz, 0U));
        }
        for(int i=0; i<tot_count*comb_n; ++i) {
            const std::string &key = combs[rand()%comb_n];
            for(auto &it: count_v) {
                if(it.first == key) {
                    it.second++;
                    break;
                }
            }
        }
        std::cout<<"Fine lineare!\n";

        std::cout<<"Dicotomica\n";
        std::sort(count_v.begin(), count_v.end());
        for(int i=0; i<tot_count*comb_n; ++i) {
            const std::string &key = combs[rand()%comb_n];
            auto it = std::lower_bound(count_v.begin(), count_v.end(), key,
                    [](const std::pair<std::string, int> &a, const std::string &b) {
                        return a.first < b;
                    });
            it->second++;
        }
        std::cout<<"Fine dicotomica\n";
    }

    {
        std::cout<<"Hashtable\n";
        std::unordered_map<std::string, unsigned> count_h;
        for(int i=0; i<tot_count*comb_n; ++i) {
            const std::string &key = combs[rand()%comb_n];
            count_h[key]++;
        }
        std::cout<<"Fine hashtable\n";
    }

    {
        std::cout<<"Map\n";
        std::map<std::string, unsigned> count_h;
        for(int i=0; i<tot_count*comb_n; ++i) {
            const std::string &key = combs[rand()%comb_n];
            count_h[key]++;
        }
        std::cout<<"Fine map\n";
    }
    return 0;
}

I risultati:

[mitalia@mitalia ~/scratch/lookup]$ stdbuf -o0 ./lookup.x | ts -i '%.s'
0.000017 Lineare
34.237293 Fine lineare!
0.000084 Dicotomica
6.239760 Fine dicotomica
0.000086 Hashtable
1.640778 Fine hashtable
0.000086 Map
3.793371 Fine map

(i valori che contano sono quelli delle righe "Fine xxx", e si riferiscono a 233*172400 lookup fatti in ordine casuale)

Vince la hashtable di default fornita con libstdc++, che sembra usare murmurhash2 come funzione di hashing.