c++ - 字符串数据的哈希函数

Question

我正在使用 C++ 语言处理哈希表，我需要一个用于字符串数据的哈希函数。我尝试过的一种哈希函数是添加 ascii 代码并使用模数 (%100)。

我的实际要求是找到与给定模式完全匹配或以给定模式开头的单词。

例如:给定的模式是“comp”。然后我想得到所有以 comp 开头的单词。 (例如:公司、计算机、comp 等)我可以使用散列来执行此操作吗，因为尝试过的散列函数只能找到完全匹配。那么谁能建议我一个适合这个要求的哈希函数。

Answer 1

前缀匹配最好用 trie 处理.

基本上这是一个树结构，在每个节点上保存键中的一个字符。连接从根到给定节点的路径中不同节点的字符将生成该节点的 key 。

搜索是将搜索关键字的每个字符与子节点进行比较的 trie 降序的问题。一旦你消耗了所有的字符，剩下的子树就是所有以搜索到的键为前缀的键。