为什么LLVM选择开放寻址哈希表来实现llvm::StringMap？

Question

许多消息来源说开放寻址中使用的散列冲突处理方法llvm::StringMap不稳定。当负载因子很高（这是可以想象的）时，据说开放寻址不如链接。

但是如果负载因子很低，那么open-addressing就会有巨大的内存浪费，因为我必须在内存中分配Bucket_number * sizeof(Record)字节，即使大多数bucket没有记录。

所以我的问题是，LLVM 选择开放寻址而不是单独链接的原因是什么？是否仅仅是因为缓存局部性（记录本身存储在存储桶中）获得的速度优势？

谢谢：）

编辑：C++11 标准对链接方法的要求，std::unordered_set而std::unordered_map不是开放寻址。为什么LLVM会选择一种连C++标准都达不到的hash碰撞处理方式？llvm::StringMap 是否有任何特殊用例可以保证这种偏差？（编辑：这张幻灯片比较了几种 LLVM 数据结构与 STL 对应数据结构的性能）

另一个问题，顺便说一句：

如何llvm::StringMap保证键的哈希值在增长时不会重新计算？该手册说：

哈希表增长不会重新计算表中已有字符串的哈希值。

Answer 1

让我们看看实现。在这里，我们看到该表存储为指向记录的间接指针的并行数组以及任何缓存的 32 位哈希码数组，即单独的结构数组。

有效地：

struct StringMap {
 uint32_t hashcode[CAPACITY];
 StringMapEntry *hashptr[CAPACITY];
};

除了容量是动态的并且负载系数似乎保持在容量的 37.5% 和 75% 之间。

对于N记录负载因子，与等效链式实现的指针加整数相比，F这为开放寻址实现产生N/F指针加N/F整数。在一个典型的64位系统中的开地址版本较大之间〜4％和〜30％更小。N*(1+1/F)N

但是，正如您正确怀疑的那样，这里的主要优势在于缓存效果。除了通过缩小数据平均缓存减少争用之外，冲突过滤归结为对连续 32 位散列键的线性重新探测，无需检查任何进一步的信息。因此，在链接必须跟随到可能未缓存的存储的链接情况下，拒绝冲突要快得多，因此可以使用显着更高的负载因子。另一方面，必须在指针查找表上考虑一个额外的可能缓存未命中，但是这是一个常数，它不会随着相当于一个链式冲突的负载而降级。

有效地：

StringMapEntry *StringMap::lookup(const char *text) {
    for(uint32_t *scan = &hashcode[hashvalue % CAPACITY]; *scan != SENTINEL; ++scan) {
        uint32_t hash_value = hash_function(text);
        if(hash_value == *scan) {
            StringMapEntry *entry = p->hashptr[scan - hashcode];
            if(!std::strcmp(entry->text, text))
                return entry;
            }
        }
    }
}

加上诸如包装之类的微妙之处。

至于你的第二个问题，优化是预先计算和存储散列键。这会浪费一些存储空间，但可以防止检查潜在的长可变长度字符串的昂贵操作，除非几乎可以肯定匹配。在退化的情况下，复杂的模板名称重整可能有数百个字符。

RehashTable 中的进一步优化是使用 2 的幂而不是主要表大小。这确保了表格的增长有效地带来了一个额外的哈希码位，并将双倍表解交织成两个连续的目标阵列，有效地使操作成为缓存友好的线性扫描。