我正在寻找一组短字符串(每个字符串的长度小于 50)的哈希函数表,它具有一个特殊功能,即每当我们在该表中搜索字符串时,如果该字符串在表内它返回该字符串的关联对象或特定且唯一的数字,如果该字符串不在表内,它会提供与输入非常相似的字符串的 ID。 为了定义两个字符串之间的相似性,我们可以定义不同的函数,但假设我们将其定义为将一个字符串转换为另一个字符串所需的最少操作次数。 三注意:
- 每个查询字符串和保存字符串的长度总是相似且固定的。
- 字符串的字母表仅限于 5 个不同的字符。
- 跑道内存力和速度对我来说都很重要。
我不是在寻找最终的解决方案,但欢迎任何建议或介绍一些在类似条件下采用类似方法的论文。
最佳答案
如果字符串集是有限且已知的, 考虑使用 GPERF 生成完美的哈希函数。
之后是 SOUNDEX(string) 的散列,它使用链表解决冲突。
使用第一组进行精确查找。 使用第二组进行接近的比赛。
编辑: 由于您的字母表只有 5 个字符,因此您有机会创建多个哈希表来减少 N 的大小。
预处理您的 key ,识别每个唯一字母。它可能是 AAAAA,这是一个只有 A 的键。 AABBBB 即 AB 或 ABCDEF。其中大约有 5 个阶乘。 120 根散列树,如果需要,可以使用单独的散列函数。
我有点担心,因为不清楚字符串实际存储在哪里。很可能你的散列会发生冲突。你打算如何解决这个问题?哈希到搜索地址列表,这将让您通过从磁盘读取实际字符串来验证正确的哈希?
关于c++ - 字符串的哈希函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27889085/