ハッシュ テーブルを使用して C++ で文字列検索を実装する

ハッシュ テーブルは、キー値を固定サイズのテーブルにマップする非常に一般的なデータ構造で、効率的な検索、挿入、削除操作を可能にします。 C では、STL (Standard Template Library) の unowned_map を使用してハッシュ テーブルを実装できます。

実際のアプリケーションでは、多くの場合、文字列に対して検索操作を実行する必要があります。たとえば、テキスト内の特定のキーワードの出現数を検索したり、特定の文字列を含むすべての行を検索したりできます。これらのタスクを効率的に実行するために、ハッシュ テーブルを使用して文字列検索を実装できます。

今回はハッシュテーブルを使ってC言語で文字列検索を実現する具体的な方法を紹介します。テキスト内に文字列が出現する回数を求める例を使用します。

まず、文字列をハッシュ テーブルにマッピングする関数を定義する必要があります。一般的な方法は、文字列のハッシュ値をキー値として使用し、異なる文字列が異なる場所にマッピングされるようにすることです。ハッシュ関数のパフォーマンスを向上させるには、ハッシュ関数を迅速に計算し、ハッシュ競合の発生を最小限に抑える必要があります。

以下は、文字列の ASCII コードを加算し、その余りを取得する単純なハッシュ関数の実装です:

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

次に、テキスト内の各単語をハッシュ テーブルに挿入する必要があります。 。テキストをスペースで単語に分割し、ハッシュ関数を呼び出すことで、テキストをハッシュ テーブルに挿入できます。キーワードは複数回出現する可能性があるため、各キーワードの出現回数を記録する必要があります。この関数を実現するには、unowned_map を使用できます。挿入中にキー値がすでに存在する場合、値は増分されます:

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

最後に、ハッシュ テーブル内の文字列に対応する値を呼び出すことで、値を取得できます。テキスト内の出現数:

size_t count = word_map["target_string"];

完全なコードは次のとおりです:

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

上記のコードでは、ハッシュ テーブルを使用して、テキスト内に文字列が出現する回数をすばやくカウントできます。文章。ハッシュ テーブルを使用すると、検索パフォーマンスが向上しますが、これは大量のデータの場合に顕著であり、実際のアプリケーションでは優れた柔軟性と拡張性も備えています。

以上がハッシュ テーブルを使用して C++ で文字列検索を実装するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。