我正在实现一个处理罗宾汉哈希冲突的哈希表。但是，以前我使用链接代替，插入近 100 万个密钥的过程几乎是即时的。罗宾汉散列不会发生同样的情况，我觉得这很奇怪，因为我的印象是它要快得多。所以我想问的是我的插入功能是否正确实现。代码如下：
typedef struct hashNode{
char *word;
int freq; //not utilized in the insertion
int probe;// distance from the calculated index to the actual index it was inserted.
struct hashNode* next; //not utilized in the insertion
struct hashNode* base; //not utilized in the insertion
}hashNode;
typedef hashNode* hash_ptr;
hash_ptr hashTable[NUM_WORDS] = {NULL}; // NUM_WORDS = 1000000
// Number of actual entries = 994707
hash_ptr swap(hash_ptr node, int index){
hash_ptr temp = hashTable[index];
hashTable[index] = node;
return temp;
}
static void insertion(hash_ptr node,int index){
while(hashTable[index]){
if(node->probe > hashTable[index]->probe){
node = swap(node,index);
}
node->probe++;
index++;
if(index > NUM_WORDS) index = 0;
}
hashTable[index] = node;
}
将所有内容置于上下文中：
- 节点参数是新条目。
- 索引参数是新条目所在的位置(如果未被占用)。
罗宾汉算法非常聪明，但它与任何其他开放哈希技术一样依赖于良好的哈希函数。
作为最坏的情况，请考虑最糟糕的哈希函数：
int hash(const char* key) { return 0; }
由于这会将每个项目映射到同一插槽，因此很容易看出探针总数在条目数上是二次的：第一个插入在第一个探针上成功;第二个插入需要两个探针;第三个插入需要三个探针;依此类推，导致总共n(n+1)/2个探针用于n个插入。无论您使用简单的线性探测还是罗宾汉探测，都是如此。
有趣的是，这个哈希函数可能对插入到链式哈希表中没有任何影响，如果 - 这是一个非常大的如果- 没有尝试验证插入的元素是唯一的。(您提供的代码就是这种情况，这并非完全不合理;哈希表很可能是作为固定查找表构建的，并且已经知道要添加的条目是唯一的。稍后会详细介绍这一点。
在链式哈希实现中，非验证插入函数可能如下所示：
void insert(hashNode *node, int index) {
node->next = hashTable[index];
hashTable[index] = node;
}
请注意，即使您计划实现删除，也没有充分的理由将双向链表用于哈希链。额外的链接只是浪费内存和周期。
事实上，你可以(实际上)毫不犹豫地构建链式哈希表，这并不意味着该算法已经构建了一个好的哈希表。当需要在表中查找值时，将发现问题：查找元素的平均探测器数将是表中元素数的一半。罗宾汉(或线性)开放寻址哈希表具有完全相同的性能，因为所有搜索都从表的开头开始。与使用该表的成本相比，开放地址哈希表的构建速度也很慢这一事实可能几乎无关紧要。
我们不需要像"始终使用 0"函数那样糟糕的哈希函数来产生二次性能。哈希函数具有极小的可能值范围(与哈希表的大小相比)就足够了。如果可能的值可能性相等，则链式哈希仍将是二次的，但平均链长度将除以可能值的数量。但是，线性/R.Hood探测哈希的情况并非如此，特别是如果所有可能的哈希值都集中在一个小范围内。例如，假设哈希函数是
int hash(const char* key) {
unsigned char h = 0;
while (*key) h += *key++;
return h;
}
在这里，哈希的范围限制为 [0， 255)。如果表大小远大于 256，这将迅速减少到与常量哈希函数相同的情况。很快，哈希表中的前 256 个条目将被填充，此后的每个插入(或查找)都需要在表开头的线性递增紧凑范围内进行线性搜索。因此，性能与具有常量哈希函数的表的性能无法区分。
所有这些都不是为了激励使用链式哈希表。相反，它指出了使用良好哈希函数的重要性。(从某种意义上说，散列密钥的结果均匀分布在整个可能的节点位置范围内。尽管如此，通常情况下，聪明的开放寻址方案比简单的链接对糟糕的哈希函数更敏感。
开放寻址方案绝对很有吸引力，特别是在静态查找表的情况下。在静态查找表的情况下，它们更具吸引力，因为删除确实可能很痛苦，因此不必实现密钥删除消除了巨大的复杂性。最常见的删除解决方案是将已删除的元素替换为已删除的标记元素。查找探测器仍必须跳过已删除标记，但如果查找后要插入，则可以在查找扫描期间记住第一个已删除标记，如果未找到键，则入的节点覆盖。这是可以接受的，但负载系数必须使用预期的 DELETE 标记数量来计算，如果使用模式有时会连续删除大量元素，则表的实际负载系数将显着下降。
但是，在删除不是问题的情况下，开放寻址哈希表具有一些重要优势。特别是，在有效负载(键和相关值，如果有)较小的情况下，它们的开销要低得多。对于链式哈希表，每个节点都必须包含一个next指针，并且哈希表索引必须是指向节点链的指针向量。对于键仅占用指针空间的哈希表，开销为 100%，这意味着负载因子为 50% 的线性探测开放寻址哈希表占用的空间略少于索引向量已完全占用且节点按需分配的链式表。
线性探测表不仅存储效率更高，而且还提供了更好的参考位置，这意味着 CPU 的 RAM 缓存将用于更大的优势。使用线性探测，可以使用单个缓存行(因此只有一个慢速内存引用)执行八个探测，这几乎是探测随机分配的表条目的链接列表的八倍。(实际上，速度不会如此极端，但很可能是其两倍以上。对于性能确实很重要的字符串键，可以考虑将键的长度和/或前几个字符存储在哈希条目本身中，以便指向完整字符串的指针通常只使用一次，以验证探测是否成功。
但是，开放寻址的空间和时间优势都取决于哈希表是一个条目数组，而不是像实现中那样指向条目的指针数组。将条目直接放入哈希索引可以避免每个条目(或至少每个链)的指针可能产生的大量开销，并允许有效使用内存缓存。因此，这是您在最终实现中可能需要考虑的事情。
最后，开放寻址不一定会使删除变得复杂。在布谷鸟哈希(以及近年来它启发的各种算法)中，删除并不比链哈希中的删除更困难，甚至可能更容易。在 cuckoo 哈希中，任何给定的键只能在表中的两个位置之一(或者，在某些变体中，一些小常量kk位置之一)，查找操作只需要检查这两个位置。(插入可能需要更长的时间，但对于负载系数小于 50% 时，仍应为 O(1)。因此，您只需将其从其所在位置删除即可删除条目;这对查找/插入速度没有明显影响，并且插槽将被透明地重复使用，无需任何进一步的干预。(不利的一面是，节点的两个可能位置不相邻，它们可能位于单独的缓存行上。但是对于给定的查找，只有两个。某些变体具有更好的参考位置。
关于你的罗宾汉实现的最后几点评论：
我不完全相信 99.5% 的负载系数是合理的。也许没关系，但99%和99.5%之间的差距是如此之小，以至于没有明显的理由来诱惑命运。此外，哈希计算期间相当慢的余数操作可以通过使表的大小为 2 的幂(在本例中为 1,048,576)并使用位掩码计算余数来消除。最终结果可能会明显更快。
在哈希条目中缓存探测计数确实有效(尽管我之前有疑问)，但我仍然认为缓存哈希值的建议方法是优越的。您可以轻松计算探头距离;它是搜索循环中的当前索引与根据缓存的哈希值(或缓存的起始索引位置本身，如果选择缓存)计算的索引之间的差异。该计算不需要对哈希表条目进行任何修改，因此缓存更友好，速度稍快，并且不需要更多空间。(但无论哪种方式，都会有存储开销，这也降低了缓存友好性。
最后，如注释中所述，您的环绕代码中有一个逐个错误;它应该是
if(index >= NUM_WORDS) index = 0;使用编写的严格大于测试，下一次迭代将尝试使用索引 NUM_WORDS 处的条目，这是越界的。
只是把它留在这里：99% 的填充率是不合理的。下界是95%，也不是90%。我知道他们在报纸上说过，他们错了。大错特错。使用60%-80%，就像你应该使用开放式地址一样
罗宾汉哈希不会在您插入时更改数量或碰撞，平均(和总)碰撞次数保持不变。只有他们的分布发生了变化：罗宾汉改善了最坏的情况。但对于平均值，它与线性、二次或双哈希相同。
- 在 75% 时，您在击中之前会发生大约 1.5 次碰撞
- 在 80% 时大约 2 次碰撞
- 在 90% 时大约 4.5 次碰撞
- 在 95% 时大约 9 次碰撞
- 在 99% 大约 30 次碰撞
我在 10000 个元素的随机表上进行了测试。罗宾汉哈希无法改变这个平均值，但它将 1% 的最坏情况的碰撞次数从 150-250 次未命中(在 95% 的填充率下)提高到大约 30-40 次。