罗宾汉算法非常聪明，但它与任何其他开放散列技术一样依赖于具有良好的散列函数。
作为最坏的情况，考虑最坏的哈希函数：
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;
}
请注意，没有充分的理由为哈希链使用双向链表，即使您计划实现删除。额外的链接只是浪费内存和周期。
您可以（几乎）没有时间构建链式哈希表这一事实并不意味着该算法已经构建了一个好的哈希表。当需要在表中查找一个值时，就会发现问题：查找元素的平均探针数将是表中元素数的一半。Robin Hood（或线性）开放寻址哈希表具有完全相同的性能，因为所有搜索都从表的开头开始。与使用该表的成本相比，开放地址哈希表的构建速度也很慢这一事实可能几乎无关紧要。
我们不需要像“始终使用 0”函数那样糟糕的哈希函数来产生二次性能。散列函数具有极小范围的可能值就足够了（与散列表的大小相比）。如果可能值的可能性相同，则链式哈希仍然是二次的，但平均链长将除以可能值的数量。但是，对于线性/R.Hood 探测散列，情况并非如此，特别是如果所有可能的散列值都集中在一个小范围内。例如，假设哈希函数是
int hash(const char* key) {
unsigned char h = 0;
while (*key) h += *key++;
return h;
}
这里，哈希的范围被限制为 [0, 255)。如果表大小远大于 256，这将迅速减少到与常量散列函数相同的情况。很快，哈希表中的前 256 个条目将被填充，并且在该点之后的每次插入（或查找）都需要在表开头的线性增加的紧凑范围内进行线性搜索。因此性能将与具有恒定哈希函数的表的性能没有区别。
这些都不是为了鼓励使用链式哈希表。相反，它指出了使用良好哈希函数的重要性。（从某种意义上说，散列密钥的结果均匀分布在可能的节点位置的整个范围内是好的。）尽管如此，通常情况下，聪明的开放寻址方案比简单的链接对坏的散列函数更敏感。
开放寻址方案绝对有吸引力，特别是在静态查找表的情况下。它们在静态查找表的情况下更有吸引力，因为删除确实很痛苦，因此不必实现键删除消除了巨大的复杂性。最常见的删除解决方案是将已删除的元素替换为 DELETED 标记元素。查找探针仍必须跳过 DELETED 标记，但如果查找之后将插入插入，则可以在查找扫描期间记住第一个 DELETED 标记，如果找不到键，则由插入的节点覆盖。这可以接受，但是负载因子必须使用预期的 DELETED 标记数来计算，如果使用模式有时会连续删除很多元素，
但是，在删除不是问题的情况下，开放地址哈希表具有一些重要的优势。特别是，在有效负载（键和相关值，如果有的话）很小的情况下，它们的开销要低得多。在链式哈希表的情况下，每个节点都必须包含一个next指针，并且哈希表索引必须是指向节点链的指针向量。对于key只占用一个指针空间的hash表，开销是100%，也就是说负载因子为50%的linear-probed开放地址hash表比索引的链表占用的空间要少一点向量被完全占用，其节点按需分配。
线性探测表不仅存储效率更高，它还提供了更好的参考局部性，这意味着 CPU 的 RAM 缓存将得到更大的利用。使用线性探测，可以使用单个高速缓存行（因此只有一个慢速内存引用）进行八次探测，这几乎是通过随机分配的表条目的链接列表进行探测的八倍。（实际上，速度不会这么快，但它可能会快两倍以上。）对于性能真正重要的字符串键，您可能会考虑存储长度和/或前几个字符哈希条目本身中的键，因此指向完整字符串的指针大多只使用一次，以验证成功探测。
但是开放寻址的空间和时间优势都取决于哈希表是一个条目数组，而不是您的实现中指向条目的指针数组。将条目直接放入哈希索引可避免每个条目（或至少每个链）的指针可能显着的开销，并允许有效使用内存缓存。所以这是你在最终实现中可能要考虑的事情。
最后，开放寻址不一定会使删除变得复杂。在杜鹃哈希（以及它近年来启发的各种算法）中，删除并不比链式哈希中的删除更困难，甚至可能更容易。在杜鹃散列中，任何给定的键只能位于表中的两个位置之一（或者，在某些变体中，k某个小常数的位置之一k) 并且查找操作只需要检查这两个地方。（插入可能需要更长的时间，但对于小于 50% 的负载因子，仍需要 O(1)。）因此，您只需将条目从其所在位置移除即可删除它；这对查找/插入速度没有明显影响，并且插槽将被透明地重用，而无需任何进一步的干预。（不利的一面是，一个节点的两个可能位置并不相邻，它们很可能位于不同的缓存行上。但对于给定的查找，只有两个位置。一些变体具有更好的参考位置。）
关于您的 Robin Hood 实现的最后几点评论：
我并不完全相信 99.5% 的负载率是合理的。也许没关系，但99%和99.5%的差距太小了，没有明显的理由去诱惑命运。此外，通过将表的大小设为 2 的幂（在本例中为 1,048,576）并使用位掩码计算余数，可以消除散列计算期间相当慢的余数运算。最终结果可能会明显更快。
在哈希条目中缓存探测计数确实有效（尽管我之前有疑问），但我仍然相信缓存哈希值的建议方法是更好的。您可以轻松计算探测距离；它是搜索循环中的当前索引与从缓存的哈希值（或缓存的起始索引位置本身，如果您选择缓存的话）计算的索引之间的差异。该计算不需要对哈希表条目进行任何修改，因此它对缓存更友好且速度稍快，并且不需要更多空间。（但无论哪种方式，都会产生存储开销，这也会降低缓存的友好性。）
最后，正如评论中所指出的，您的环绕代码中有一个错误；它应该是
if(index >= NUM_WORDS) index = 0;
通过编写的严格大于测试，您的下一次迭代将尝试使用索引 NUM_WORDS 处的条目，该条目超出范围。