Utilisation d'une table de hachage pour implémenter la recherche de chaînes en C++

La table de hachage est une structure de données très courante qui mappe les valeurs clés dans une table de taille fixe, permettant des opérations efficaces de recherche, d'insertion et de suppression. En C++, nous pouvons utiliser unordered_map dans STL (Standard Template Library) pour implémenter une table de hachage.

Dans les applications pratiques, il est souvent nécessaire d'effectuer des opérations de recherche sur des chaînes. Par exemple, recherchez le nombre d'occurrences d'un certain mot-clé dans un texte ou recherchez toutes les lignes contenant une certaine chaîne. Pour accomplir ces tâches efficacement, des recherches de chaînes peuvent être implémentées à l'aide de tables de hachage.

Dans cet article, nous présenterons la méthode spécifique d'utilisation de la table de hachage pour implémenter la recherche de chaîne en C++. Nous utiliserons l'exemple de la recherche du nombre de fois qu'une chaîne apparaît dans un texte.

Tout d'abord, nous devons définir une fonction pour mapper les chaînes dans une table de hachage. Une méthode courante consiste à utiliser la valeur de hachage de la chaîne comme valeur de clé, garantissant ainsi que différentes chaînes correspondent à différents emplacements. Pour qu'une fonction de hachage ait de bonnes performances, elle doit être calculée rapidement et l'apparition de conflits de hachage doit être minimisée.

Voici une implémentation simple d'une fonction de hachage qui ajoute les codes ASCII des chaînes et prend le reste :

size_t hash_func(const std::string& str) {
    size_t hash_val = 0;
    for (char c : str) {
        hash_val += static_cast<size_t>(c);
    }
    return hash_val % MAP_SIZE;
}

Ensuite, nous devons insérer chaque mot du texte dans la table de hachage. Nous pouvons insérer le texte dans une table de hachage en le divisant en mots par des espaces et en appelant une fonction de hachage. Puisqu’un mot-clé peut apparaître plusieurs fois, nous devons enregistrer le nombre de fois où chaque mot-clé apparaît. Nous pouvons utiliser unordered_map pour réaliser cette fonction. Si la valeur de la clé existe déjà lors de l'insertion, la valeur sera incrémentée :

std::unordered_map<std::string, size_t> word_map;
for (std::string word : words) {
    if (word_map.find(word) == word_map.end()) {
        word_map[word] = 1;
    } else {
        ++word_map[word];
    }
}

Enfin, nous pouvons obtenir son occurrence dans le texte en appelant la valeur correspondant à la chaîne dans la table de hachage. Le nombre de fois :

size_t count = word_map["target_string"];

Le code complet est le suivant :

#include 
#include 
#include 
#include 

const size_t MAP_SIZE = 1024;

size_t hash_func(const std::string& str) {
    size_t hash_val = 0;
    for (char c : str) {
        hash_val += static_cast<size_t>(c);
    }
    return hash_val % MAP_SIZE;
}

int main() {
    std::vector words {"hello", "world", "hello", "c++", "hash", "world", "world"};
    std::unordered_map word_map;

    for (std::string word : words) {
        if (word_map.find(word) == word_map.end()) {
            word_map[word] = 1;
        } else {
            ++word_map[word];
        }
    }

    size_t count = word_map["world"];
    std::cout << "The word 'world' appears " << count << " times." << std::endl;

    return 0;
}

Avec le code ci-dessus, on peut utiliser une table de hachage pour compter rapidement le nombre de fois qu'une chaîne apparaît dans un texte. L'utilisation de tables de hachage peut améliorer les performances de recherche, ce qui est plus évident pour de grandes quantités de données. Elle offre également une grande flexibilité et évolutivité dans les applications pratiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!