Cet article explore l'utilisation des structures de données basées sur le hachage dans la Standard Template Library (STL) de C++, spécifiquement unordered_set, unordered_multiset et unordered_map. Ces conteneurs, contrairement à leurs homologues basés sur les arbres rouges-noirs (set, multiset, map), offrent des performances moyennes en O(1) pour les opérations d'insertion, de suppression et de recherche, au prix d'une absence d'ordre des éléments.

1. Structures de hachage : unordered_set et unordered_multiset

Les conteneurs unordered_set et unordered_multiset sont des alternatives aux set et multiset basés sur les arbres rouges-noirs. Leur principal avantage réside dans l'utilisation de tables de hachage en interne, pemrettant des opérations en temps moyen constant (O(1)). La différence principale entre set et unordered_set est l'ordre des éléments : les éléments dans un set sont toujours triés, tandis que dans un unordered_set, ils sont désordonnés.

L'utilisation de unordered_set est similaire à celle de set, à l'exception de l'absence des méthodes lower_bound() et upper_bound(). Il est nécessaire d'inclure le fichier d'en-tête <unordered_set>.

2. Dictionnaires de hachage : unordered_map

À l'instar de unordered_set par rapport à set, unordered_map est l'équivalent basé sur une table de hachage de map. Il stocke des paires clé-valeur et offre des opérations en temps moyen constant. Comme pour unordered_set, il faut inclure le fichier d'en-tête <unordered_map>. Il est important de noter que l'itération sur les éléments d'un unordered_map ne garantit aucun ordre, contrairement à map.

3. Exemple d'application : Gestion d'inscriptions (Problème P5266)

Ce problème classique de gestion de données implique des opérations d'ajout, de modification, de recherche et de suppression. Une unordered_map<string, int> est une solution appropriée pour stocker les noms des étudiants (clés) et leurs scores (valeurs).

Voici une implémentation C++ utilisant unordered_map :

#include <iostream>
#include <unordered_map>
#include <string>
#define endl "\\n"
using namespace std;

int operation, score, num_operations;
string name;
unordered_map<string, int> student_scores;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> num_operations;
    while (num_operations--) {
        cin >> operation;
        if (operation == 1) { // Add/Update score
            cin >> name >> score;
            if (student_scores.count(name)) {
                student_scores[name] = score;
            } else {
                student_scores.insert({name, score});
            }
            cout << "OK" << endl;
        } else if (operation == 2) { // Query score
            cin >> name;
            if (student_scores.count(name)) {
                cout << student_scores[name] << endl;
            } else {
                cout << "Not found" << endl;
            }
        } else if (operation == 3) { // Delete record
            cin >> name;
            if (student_scores.count(name)) {
                student_scores.erase(name);
                cout << "Deleted successfully" << endl;
            } else {
                cout << "Not found" << endl;
            }
        } else { // operation == 4: Count records
            cout << student_scores.size() << endl;
        }
    }
    return 0;
}

On peut également utiliser une map<string, int> pour ce problème, mais unordered_map est préférable pour des perforamnces optimales en moyenne.

4. Exercice : Paires A-B (Problème P1102)

L'objectif est de trouver le nombre de paires (A, B) telles que A - B = C, où C est une constante donnée. Les nombres A, B et C peuvent être très grands.

Analyse

Approche par force brute :

Une double boucle pour vérifier toutes les paires (arr[i], arr[j]) et tester si arr[i] - arr[j] == C aurait une complexité temporelle de O(N^2), ce qui est trop lent pour N allant jusqu'à 2*10^5.

Approche par table de hachage ou arbre rouge-noir :

L'équation A - B = C peut être réécrite comme A = B + C. On peut alors parcourir le tableau une fois pour stocker la fréquence de chaque nombre dans une table de hachage ou un arbre rouge-noir. Ensuite, pour chaque nombre arr[j] (représentant B), on cherche le nombre d'occurrences de arr[j] + C (représentant A) dans la structure de données.

Notez que puisque C peut être très grand, il faut utiliser unsigned long long pour les variables impliquées.

Solution avec table de hachage :

#include <iostream>
#include <unordered_map>
using namespace std;
typedef unsigned long long ull;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    unordered_map<ull, ull> counts;
    const int MAX_N = 2e5 + 10;
    ull n, c, pair_count = 0;
    ull arr[MAX_N];

    cin >> n >> c;
    for (ull i = 0; i < n; ++i) {
        cin >> arr[i];
        counts[arr[i]]++; // Store frequency of each number
    }

    for (ull j = 0; j < n; ++j) {
        // For each element arr[j] (potential B), count occurrences of arr[j] + c (potential A)
        pair_count += counts[c + arr[j]];
    }

    cout << pair_count;
    return 0;
}

Solution avec arbre rouge-noir :

Il suffit de remplacer unordered_map par map dans le code précédent.

#include <iostream>
#include <map>
using namespace std;
typedef unsigned long long ull;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    map<ull, ull> counts;
    const int MAX_N = 2e5 + 10;
    ull n, c, pair_count = 0;
    ull arr[MAX_N];

    cin >> n >> c;
    for (ull i = 0; i < n; ++i) {
        cin >> arr[i];
        counts[arr[i]]++; // Store frequency of each number
    }

    for (ull j = 0; j < n; ++j) {
        // For each element arr[j] (potential B), count occurrences of arr[j] + c (potential A)
        pair_count += counts[c + arr[j]];
    }

    cout << pair_count;
    return 0;
}

5. Exercice : Villes et États (Problème P3405)

Le problème consiste à trouver des paires de villes où les deux premiers caractères du nom d'une ville sont identiques aux deux premiers caractères du nom de l'état de l'autre ville, et vice-versa. Les villes et états doivent appartenir à des états différents.

Analyse

Compréhension de la condition "spéciale" :

Pour chaque ville, on ne conserve que les deux premiers caractères de son nom. La condition est que si une ville A a pour préfixe "XY" et appartient à l'état "XY", et une ville B a pour préfixe "AB" et appartient à l'état "AB", alors elles forment une paire si "XY" est le préfixe de B et "AB" est le préfixe de A, et que A et B sont dans des états différents.

Gestion des cas particuliers :

Il faut exclure les paires où une ville et son état ont les mêmes deux premiers caractères, si la ville et l'état proviennent du même état. Par exemple, si une ville abc avec préfixe ab apparteint à l'état ab, et une autre ville abd avec préfixe ab appartient aussi à l'état ab, ces paires ne doivent pas être comptées.

Code

Solution avec arbre rouge-noir (map) :

Une map<pair<string, string>, int> est utilisée pour stocker les paires (préfixe ville, état) et leur fréquence. La clé est une paire, car map supporte les paires comme clés.

// Version 1: Inclut toutes les paires, puis filtre lors du comptage
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    vector<pair<string, string>> city_state_pairs;
    string city_name, state_name;
    map<pair<string, string>, int> counts;
    int n, total_pairs = 0;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> city_name >> state_name;
        string city_prefix = city_name.substr(0, 2);
        city_state_pairs.push_back({city_prefix, state_name});
        counts[{city_prefix, state_name}]++;
    }

    for (const auto& pair : city_state_pairs) {
        // Check for the reverse pair and ensure cities are from different states
        if (counts.count({pair.second, pair.first}) && pair.first != pair.second) {
            total_pairs += counts[{pair.second, pair.first}];
        }
    }
    // Each valid pair is counted twice (once for each city), so divide by 2
    cout << total_pairs / 2 << endl;
    return 0;
}

// Version 2: Filtre les paires invalides lors de l'insertion
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    vector<pair<string, string>> valid_city_state_pairs;
    string city_name, state_name;
    map<pair<string, string>, int> counts;
    int n, total_pairs = 0;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> city_name >> state_name;
        string city_prefix = city_name.substr(0, 2);
        if (city_prefix != state_name) { // Only consider pairs where prefix != state name
            valid_city_state_pairs.push_back({city_prefix, state_name});
            counts[{city_prefix, state_name}]++;
        }
    }

    for (const auto& pair : valid_city_state_pairs) {
        // Check for the reverse pair
        if (counts.count({pair.second, pair.first})) {
            total_pairs += counts[{pair.second, pair.first}];
        }
    }
    // Each valid pair is counted twice
    cout << total_pairs / 2 << endl;
    return 0;
}

La Version 2 est généralement préférable car elle évite de stocker et de traiter des paires potentiellement invalides.

Version optimisée sans stockage intermédiaire des paires :

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string city_name, state_name;
    map<pair<string, string>, int> counts;
    int n, total_pairs = 0;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> city_name >> state_name;
        string city_prefix = city_name.substr(0, 2);

        if (city_prefix == state_name) {
            continue; // Skip if prefix is same as state name
        }

        // Increment count for the current pair
        counts[{city_prefix, state_name}]++;
        // Add the count of the reverse pair (state, city_prefix) encountered so far
        total_pairs += counts[{state_name, city_prefix}];
    }

    cout << total_pairs << endl;
    return 0;
}

Solution avec table de hachage (unordered_map) :

Pour utiliser une table de hachage, nous devons combiner le préfixe de la ville et le nom de l'état en une seule clé de chaîne. Par exemple, pour une ville avec le préfixe "MI" et un état "FL", la clé pourrait être "MIFL".

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string city_name, state_name;
    unordered_map<string, int> counts;
    int n, total_pairs = 0;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> city_name >> state_name;
        string city_prefix = city_name.substr(0, 2);

        if (city_prefix == state_name) {
            continue; // Skip if prefix is same as state name
        }

        // Create a combined key for the hash table
        string current_key = city_prefix + state_name;
        string reverse_key = state_name + city_prefix;

        // Increment count for the current key
        counts[current_key]++;
        // Add the count of the reverse key encountered so far
        total_pairs += counts[reverse_key];
    }

    cout << total_pairs << endl;
    return 0;
}