在C++中使用哈希表實現字串查找

哈希表是一種非常常見的資料結構，它可以將鍵值映射到固定大小的表中，從而可以有效地進行查找、插入和刪除操作。在C 中，我們可以使用STL（Standard Template Library）中的unordered_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;
}

接下來，我們需要將文字中的每個單字插入到哈希表中。我們可以透過將文字以空格分割成若干個單詞，並呼叫雜湊函數將它們插入到哈希表中。由於一個關鍵字可能出現多次，我們需要記錄每個關鍵字出現的次數。我們可以使用unordered_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中文網其他相關文章！