Ok, ho fatto qualche prova io in C++ con un programma di test di questo tipo:
codice:
#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:
codice:
[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.