C中的罗宾汉哈希

Question

我正在实现一个 Hashtable 来处理与 Robin Hood 哈希的冲突。但是，以前我使用的是链接，插入近 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;
}

将所有内容置于上下文中：

节点参数是新条目。
索引参数是新条目所在的位置，如果它没有被占用的话。

Answer 1

罗宾汉算法非常聪明，但它与任何其他开放式哈希技术一样依赖于良好的哈希函数。

作为最坏的情况，考虑最坏的哈希函数：

int hash(const char* key) { return 0; }

因为这会将每个项目映射到同一个插槽，所以很容易看出探测总数是条目数的二次方：第一个插入在第一个探测上成功；第二个插件需要两个探针；第三个三探头；依此类推，导致 n 插入的总共 n(n+1)/2 个探针。无论您使用简单的线性探测还是罗宾汉探测，都是如此。

有趣的是，这个哈希函数可能对插入到链式哈希中没有任何影响 table 如果 - 这是一个非常大的 if - 没有尝试用于验证插入的元素是否唯一。（在您提供的代码中就是这种情况，这并非完全不合理；哈希 table 很可能被构建为固定查找 table 并且已经知道条目到添加的是唯一的。稍后会详细介绍这一点。）

在链式哈希实现中，非验证插入函数可能如下所示：

void insert(hashNode *node, int index) {
  node->next = hashTable[index];
  hashTable[index] = node;
}

请注意，没有充分的理由为哈希链使用双重 linked 列表，即使您打算实施删除也是如此。额外的 link 只是浪费内存和周期。

您可以（实际上）立即构建链式哈希table这一事实并不意味着该算法已经构建了一个好的哈希table。等到在table中查找一个值时，就会发现问题：查找该元素的平均探测次数将是table中元素个数的一半。 Robin Hood（或线性）开放寻址哈希 table 具有完全相同的性能，因为所有搜索都从 table 的开头开始。与使用 table.

的成本相比，开放寻址哈希 table 的构建速度也很慢这一事实可能几乎无关紧要。

我们不需要像 "always use 0" 函数那样可怕的散列函数来产生二次性能。哈希函数具有极小范围的可能值就足够了（与哈希的大小 table 相比）。如果可能值的可能性相同，链式哈希仍将是二次的，但平均链长度将除以可能值的数量。但是，linear/R.Hood 探测的哈希不是这种情况，特别是如果所有可能的哈希值都集中在一个小范围内。假设，例如，哈希函数是

int hash(const char* key) {
  unsigned char h = 0;
  while (*key) h += *key++;
  return h;
}

这里hash的范围限制在[0, 255)。如果 table 大小远大于 256，这将迅速减少到与常量哈希函数相同的情况。很快，散列 table 中的前 256 个条目将被填充，并且该点之后的每个插入（或查找）都需要在 table 开头的线性增加的紧凑范围内进行线性搜索.因此性能将与具有常量哈希函数的 table 的性能无法区分。

None 的目的是鼓励使用链式哈希 table。相反，它指出了使用良好哈希函数的重要性。（从某种意义上说，散列密钥的结果均匀分布在整个可能的节点位置范围内是好的。）None然而，通常情况下，聪明的开放寻址方案对坏的散列函数更敏感比简单的链接。

开放寻址方案绝对有吸引力，特别是在静态查找 table 的情况下。它们在静态查找 table 的情况下更具吸引力，因为删除确实很痛苦，因此不必实施键删除可以消除巨大的复杂性。最常见的删除解决方案是用 DELETED 标记元素替换已删除的元素。查找探测仍然必须跳过 DELETED 标记，但是如果查找之后要进行插入，则可以在查找扫描期间记住第一个 DELETED 标记，如果找不到键，则由插入的节点覆盖。这可以接受，但负载因子必须根据预期的 DELETED 标记数来计算，如果使用模式有时连续删除大量元素，table 的实际负载因子将显着下降。

不过，在删除不是问题的情况下，开放寻址哈希 table 具有一些重要的优势。特别是，在负载（键和关联值，如果有的话）很小的情况下，它们的开销要低得多。在链式哈希 table 的情况下，每个节点必须包含一个 next 指针，并且哈希 table 索引必须是指向节点链的指针向量。对于key只占指针space的hashtable，开销为100%，也就是说，一个线性探测的open-addressed hashtable，load factor为50 %占用space比一个链式table少一点，其索引向量被完全占用并且其节点按需分配。

不仅线性探测 table 的存储效率更高，它还提供了更好的参考位置，这意味着 CPU 的 RAM 缓存将发挥更大的优势。使用线性探测，可以使用单个高速缓存行进行八次探测（因此只有一个慢速内存引用），这几乎是通过随机分配的 linked 列表进行探测的八倍 table条目。（在实践中，加速不会如此极端，但它可能会快两倍以上。）对于字符串键，在性能非常重要的情况下，您可能会考虑首先存储长度 and/or哈希条目本身中键的几个字符，因此指向完整字符串的指针大多只使用一次，以验证探测成功。

但是开放寻址的 space 和时间优势都取决于散列 table 是 条目数组 ，而不是指针数组在您的实施中进入条目。将条目直接放入哈希索引避免了每个条目（或至少每个链）的指针的可能显着开销，并允许有效使用内存缓存。所以这是您在最终实施中可能需要考虑的事情。

最后，开放寻址不一定会使删除变得复杂。在布谷鸟哈希（及其近年来启发的各种算法）中，删除并不比链式哈希中的删除困难，甚至可能更容易。在布谷鸟哈希中，任何给定的键只能位于 table 中的两个位置之一（或者，在某些变体中，k 位置之一用于某个小常量 k）和一个查找操作只需要检查这两个地方。（插入可能需要更长的时间，但对于小于 50% 的负载因子，它仍然需要 O(1)。）这将不会对 lookup/insertion 速度产生明显影响，并且插槽将透明地重复使用，无需任何进一步干预。（不利的一面是，一个节点的两个可能位置并不相邻，它们很可能位于不同的缓存行上。但是对于给定的查找，它们只有两个。一些变体具有更好的参考位置。）

关于您的罗宾汉实施的最后几点评论：

我不完全相信 99.5% 的负载率是合理的。也许没关系，但 99% 和 99.5% 之间的差异是如此之小，以至于没有明显的理由去诱惑命运。此外，通过使 table 的大小为 2 的幂（在本例中为 1,048,576）并使用位掩码计算余数，可以消除哈希计算期间相当缓慢的余数运算。最终结果可能会明显更快。
在散列条目中缓存探测计数确实有效（尽管我之前有疑虑）但我仍然相信建议的缓存散列值的方法更优越。您可以轻松计算出探测距离；它是搜索循环中的当前索引与根据缓存的哈希值（或缓存的起始索引位置本身，如果您选择缓存的内容）计算的索引之间的差异。该计算不需要对散列 table 条目进行任何修改，因此它对缓存更友好且速度稍快，并且不再需要 space。（但无论哪种方式，都会有存储开销，这也会降低缓存友好性。）
最后，如评论中所述，您的环绕代码中有一个差一错误；应该是
```
if(index >= NUM_WORDS) index = 0;
```
使用严格的大于测试，您的下一次迭代将尝试使用索引 NUM_WORDS 处的条目，该条目超出范围。

Answer 2

只想把它留在这里：99% 的填充率不合理。下界是95%，也不是90%。我知道他们在报纸上说了，他们错了。大错特错。像开放地址一样使用 60%-80%

Robin Hood 哈希不会在您插入时更改数量或冲突，平均（和总）冲突数保持不变。只是它们的分布发生了变化：罗宾汉改善了最坏的情况。但对于平均值，它与线性、二次或双重哈希相同。

在 75% 时，您会在命中前发生大约 1.5 次碰撞
大约 2 次碰撞的 80%
在 90% 时约有 4.5 次碰撞
在 95% 时约有 9 次碰撞
99% 大约 30 次碰撞

我测试了一个 10000 元素的随机 table。罗宾汉哈希不能改变这个平均值，但它可以将 1% 最坏情况下的碰撞次数从 150-250 次（在 95% 填充率时）未命中提高到大约 30-40 次。

C中的罗宾汉哈希

Robin Hood hashing in C

c

algorithm

hashtable

probing