L'analyse des performances des différentes implémentations de tables de hachage en C++ révèle des comportements surprenants selon la distribution des clés. L'exemple suivant illustre ce phénomène en utilisant des clés combinées (paires d'entiers) compressées dans un seul long long.

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>

using ll = long long;
using namespace std;
using namespace __gnu_pbds;

const int MAX_TAILLE = 100010;
int positions[MAX_TAILLE], compteur = 0;
mt19937 generateur;

struct Arete {
    int sommet1, sommet2, poids;
};

vector<Arete> listeAretes;

inline bool comparerArete(const Arete& a, const Arete& b) {
    return a.poids < b.poids;
}

gp_hash_table<ll, int> tableHachage;

inline ll creerCle(int x, int y) {
    return (static_cast<ll>(x) << 32) | y;
}

int main() {
    int nbSommets = 100000, nbAretes = 100000, nbRequetes = 250;
    for (int i = 1; i <= nbSommets; ++i) {
        positions[i] = i;
    }

    // Insertion des arêtes dans la table de hachage
    for (int i = 0; i < nbAretes; ++i) {
        int poids = generateur() % 123456789 + 1;
        int u = generateur() % nbSommets + 1;
        int v = generateur() % nbSommets + 1;
        if (u > v) swap(u, v);
        ll cle = creerCle(u, v);
        
        if (tableHachage.find(cle) == tableHachage.end()) {
            tableHachage[cle] = poids;
        } else {
            tableHachage[cle] = min(tableHachage[cle], poids);
        }
    }

    // Parcours et extraction des arêtes
    for (const auto& entree : tableHachage) {
        ll cle = entree.first;
        int poids = entree.second;
        int u = static_cast<int>(cle >> 32);
        int v = static_cast<int>(cle & 0xFFFFFFFF);
        listeAretes.push_back({u, v, poids});
    }

    // Re-mapping des clés vers des indices
    for (size_t i = 0; i < listeAretes.size(); ++i) {
        const auto& arete = listeAretes[i];
        ll cle = creerCle(arete.sommet1, arete.sommet2);
        tableHachage[cle] = i;
    }

    // Requêtes sur des sous-ensembles de sommets
    for (int requete = 0; requete < nbRequetes; ++requete) {
        shuffle(positions + 1, positions + nbSommets + 1, generateur);
        int tailleSousEnsemble = 400;
        for (int i = 0; i < tailleSousEnsemble; ++i) {
            for (int j = i + 1; j < tailleSousEnsemble; ++j) {
                int u = positions[i];
                int v = positions[j];
                if (u > v) swap(u, v);
                ll cle = creerCle(u, v);
                if (tableHachage.find(cle) != tableHachage.end()) {
                    ++compteur;
                }
            }
        }
    }

    return 0;
}

En comparant différentes structures : gp_hash_table peut devenir très lent (environ 10 secondess) lorsque les clés sont fortement déséquilibrées. La fonction creerCle produisant des valeurs long long non uniformément distribuées cause des collisions fréquentes.

Avec cc_hash_table, les temps d'exécution sont bien meilleurs (environ 0.01 seconde), mais des vérifications avec UBSan révèlent des accès mémoire invalides indiquant potentiellmeent des bugs dans l'implémentation.

La solution recommandée consiste à utiliser une table de hachage imbriquée :

gp_hash_table<int, gp_hash_table<int, int>> tableImbriquee;

Cette approche évite le problème de distribution des clés en séparant les deux dimensions de la clé, offrant de meilleures performances et une plus grande stabilité.