我需要在C中使用面向性能的哈希函数实现来实现我将要编码的哈希表 . 我已经环顾四周,只发现了一个问题,询问什么是“一般”的好散列函数 . 我考虑过CRC32(但在哪里可以找到很好的实现?)和一些加密算法 . 不过,我的 table 有非常具体的要求 .
这是表格的样子:
100,000 items max
200,000 capacity (so the load is 0.5)
hashing a 6-character string which is a part of English sentence
examples: "become" "and he" ", not "
哈希表的首要任务是快速搜索(检索) . 快速插入并不重要,但它会伴随快速搜索 . 删除并不重要,重新散列不是我可能会使用here描述的单独链接 . 我已经看了this article,但想要对那些曾经处理过这样的任务的人提出意见 .
9 回答
那么你使用正确的数据结构,因为在哈希表中搜索是O(1)! :)
CRC32应该没问题 . 实现并不复杂,它主要基于XOR . 只要确保它使用一个好的多项式 .
现在假设你想要一个哈希,并且想要一些在你的情况下可行的东西 blazing fast ,因为你的字符串只有6个字符长你可以使用这个魔法:
CRC用于缓慢发布;)
Explanation: 这可以通过将字符串指针的内容转换为"look like" size_t(int32或int64,基于硬件的最佳匹配)来实现 . 因此,字符串的内容被解释为原始数字,不再担心字符,然后您将所需的精度进行位移(您将此数字调整为最佳性能,我发现2对于散列字符串很有效)成千上万) .
另外真正整洁的部分是现代硬件上任何体面的编译器都会在1个汇编指令中散列这样的字符串,很难被击败;)
这个简单的多项式非常有效 . 我从微软研究院的Paul Larson那里得到了它,他研究了各种哈希函数和哈希乘法器 .
在创建哈希表以防止hash table attacks之前,应将
salt
初始化为某个随机选择的值 . 如果这对您来说不是问题,请使用0 .表的大小也很重要,以尽量减少碰撞 . 听起来像你的很好 .
Boost.Functional/Hash可能对您有用 . 我保证其性能 .
Boost也有一个CRC library .
我先看一下Boost.Unordered(即boost :: unordered_map <>) . 它使用哈希映射而不是二进制树作为容器 .
我相信一些STL实现在stdext命名空间中有一个hash_map <>容器 .
表的大小将决定您应该使用的大小哈希值 . 您希望尽可能减少碰撞 . 我不确定你用最大项目和容量指定了什么(它们对我来说似乎是一样的)在任何情况下,这些数字中的任何一个都表明32位散列就足够了 . 您可能会使用CRC16(约65,000种可能性),但您可能会遇到很多冲突 . 另一方面,碰撞可能比CRC32散列更快地处理 .
我会说,请使用CRC32 . 您将发现不缺少文档和示例代码 . 由于您已经计算出最大值并且速度是优先级,因此请使用指针数组 . 使用哈希生成索引 . 在碰撞时,增加索引直到你碰到一个空桶..快速而简单 .
由于您存储英文单词,因此大多数字符都是字母,并且数据的最重要的两位不会有太大的变化 . 除此之外,我会保持它非常简单,只需使用XOR . 毕竟你不是在寻找加密强度,而只是为了合理均匀分布 . 这些方面的东西:
除此之外,您是否将std :: tr1 :: hash视为哈希函数和/或std :: tr1 :: unordered_map作为哈希表的实现?使用这些可能会节省很多与实现自己的类相反的工作 .
简单的事情:
这假定为32位整数 . 它每个字符使用5位,因此哈希值只有30位 . 您可以通过为前一个或两个字符生成六位来解决此问题 . 如果字符集足够小,则可能不需要超过30位 .
如果您需要搜索短字符串并且插入不是问题,也许您可以使用B树或2-3树,在您的情况下通过散列不会获得太多收益 .
你这样做的方法是在每个节点放一个字母,这样你首先要检查节点“a”,然后检查“a”的子节点是否为“p”,它是“p”的子节点,然后是“ l“然后”e“ . 在你有“苹果”和“申请”的情况下,你需要寻找最后一个节点,(因为唯一的区别在于最后一个“e”和“y”)
但是在大多数情况下你都能得到只需几步之后的单词(“xylophone”=>“x” - >“ylophone”),所以你可以这样优化 . 这可能比散列更快
自C 11以来,C提供了std::hash< string >( string ) . 这可能是一个有效的散列函数,为大多数字符串提供good distribution of hash-codes .
此外,如果您正在考虑实现哈希表,那么您现在应该考虑使用C std::unordered_map .