Verwenden einer Hash-Tabelle zum Implementieren der Zeichenfolgensuche in C++

Hash-Tabelle ist eine sehr verbreitete Datenstruktur, die Schlüsselwerte einer Tabelle fester Größe zuordnet und so effiziente Such-, Einfüge- und Löschvorgänge ermöglicht. In C++ können wir unordered_map in STL (Standard Template Library) verwenden, um eine Hash-Tabelle zu implementieren.

In praktischen Anwendungen ist es häufig erforderlich, Suchvorgänge für Zeichenfolgen durchzuführen. Ermitteln Sie beispielsweise die Häufigkeit des Vorkommens eines bestimmten Schlüsselworts in einem Text oder alle Zeilen, die eine bestimmte Zeichenfolge enthalten. Um diese Aufgaben effizient zu erledigen, können String-Suchen mithilfe von Hash-Tabellen implementiert werden.

In diesem Artikel stellen wir die spezifische Methode zur Verwendung einer Hash-Tabelle zur Implementierung der Zeichenfolgensuche in C++ vor. Als Beispiel verwenden wir die Ermittlung der Häufigkeit, mit der eine Zeichenfolge in einem Text vorkommt.

Zuerst müssen wir eine Funktion definieren, um Zeichenfolgen einer Hash-Tabelle zuzuordnen. Eine gängige Methode besteht darin, den Hashwert einer Zeichenfolge als Schlüsselwert zu verwenden und so sicherzustellen, dass unterschiedliche Zeichenfolgen unterschiedlichen Orten zugeordnet werden. Damit eine Hash-Funktion eine gute Leistung erbringt, muss sie schnell berechnet werden und das Auftreten von Hash-Konflikten sollte minimiert werden.

Hier ist eine einfache Hash-Funktionsimplementierung, die die ASCII-Codes der Zeichenfolgen hinzufügt und den Rest übernimmt:

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;
}

Als nächstes müssen wir jedes Wort im Text in die Hash-Tabelle einfügen. Wir können den Text in eine Hash-Tabelle einfügen, indem wir ihn durch Leerzeichen in Wörter aufteilen und eine Hash-Funktion aufrufen. Da ein Schlüsselwort mehrmals vorkommen kann, müssen wir aufzeichnen, wie oft jedes Schlüsselwort vorkommt. Wir können unordered_map verwenden, um diese Funktion zu erreichen. Wenn der Schlüsselwert beim Einfügen bereits vorhanden ist, wird der Wert erhöht:

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];
    }
}

Schließlich können wir sein Vorkommen im Text ermitteln, indem wir den Wert aufrufen, der der Zeichenfolge in der Hash-Tabelle entspricht. Die Häufigkeit:

size_t count = word_map["target_string"];

Der vollständige Code lautet wie folgt:

#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;
}

Mit dem obigen Code können wir eine Hash-Tabelle verwenden, um schnell zu zählen, wie oft eine Zeichenfolge in einem Text vorkommt. Die Verwendung von Hash-Tabellen kann die Suchleistung verbessern, was bei großen Datenmengen offensichtlicher ist. Außerdem bietet sie eine große Flexibilität und Skalierbarkeit in praktischen Anwendungen.

Das obige ist der detaillierte Inhalt vonVerwenden einer Hash-Tabelle zum Implementieren der Zeichenfolgensuche in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!