在C++中使用哈希表实现字符串查找

哈希表是一种非常常见的数据结构，它可以将键值映射到一个固定大小的表中，从而可以高效地进行查找、插入和删除操作。在C++中，我们可以使用STL（Standard Template Library）中的unordered_map实现哈希表。

在实际应用中，经常需要对字符串进行查找操作。例如，在一个文本中查找某个关键字的出现次数或者找到所有包含某个字符串的行。为了高效地完成这些任务，可以使用哈希表实现字符串查找。

在这篇文章中，我们将介绍在C++中使用哈希表实现字符串查找的具体方法。我们将以查找一个字符串在一个文本中出现的次数为例进行说明。

首先，我们需要定义一个函数来将字符串映射到哈希表中。一种常见的方法是使用字符串的哈希值作为键值，从而可以保证不同的字符串映射到不同的位置。为了使哈希函数具有良好的性能，需要保证其计算速度快，并且尽量减少哈希冲突的发生。

立即学习“C++免费学习笔记（深入）”；

下面是一个简单的哈希函数实现，它将字符串的ASCII码相加并取余：

sematic

一个开源的机器学习平台

下载

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

接下来，我们需要将文本中的每个单词插入到哈希表中。我们可以通过将文本按空格分割成若干个单词，并调用哈希函数将它们插入到哈希表中。由于一个关键字可能出现多次，我们需要记录每个关键字出现的次数。我们可以使用unordered_map来实现这一功能，插入时若该键值已存在则将值自增：

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["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(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;
}

通过以上代码，我们就可以使用哈希表快速统计一个字符串在一个文本中出现的次数。使用哈希表能够提高查找性能，对于大量数据效果更为明显，同时在实际应用中也具有很大的灵活性和可扩展性。