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

Question

许多来源称llvm::StringMap中使用的哈希冲突处理方法开放地址法不稳定。当负载因子较高时（这是可以想象的），开放地址法被认为比链接法差。

但如果负载因子很低，使用开放地址法会造成巨大的内存浪费，因为我必须在内存中分配Bucket_number * sizeof(Record)字节，即使大多数桶不包含记录。

所以我的问题是，LLVM选择开放地址法而不是分离链接的原因是什么？仅仅因为通过缓存局部性获得速度优势吗？

谢谢:)

编辑：C++11标准对std::unordered_set和std::unordered_map的要求意味着使用链式方法处理哈希冲突，而不是开放地址法。为什么LLVM选择了一种无法满足C++标准的哈希冲突处理方法？是否有任何特殊用例需要使用llvm::StringMap来保证这种偏离？（编辑：此幻灯片将LLVM的几种数据结构与STL的相应结构进行了性能比较）

另一个问题：

顺便问一下，llvm::StringMap如何保证在增长时不会重新计算键的哈希值？ 手册中说：

哈希表增长时不会重新计算已存在于表中的字符串的哈希值。

- Leedehai

---

假定字符串不是一个很大的对象（只是指针+大小），因此这种方式不会浪费太多内存。对于最后一个问题：也许他们在表中存储哈希值。如果字符串不匹配，则比较可能会更快。 - geza

“甚至不能满足C++标准”？哼，它不是一个unordered_map或set。它并不试图满足特定std容器的要求... - Yakk - Adam Nevraumont

@Yakk 但是如果它不能满足标准的要求，用户可以使用std::unordered_map<std::string, ..>代替llvm::StringMap。因此，我询问了特殊用例来证明:) - Leedehai

@geza 哦，你说得对，llvm::StringRef 只占用了 2 个字长。我的问题是这种技术通常适用于哪些情况，在这种情况下 sizeof(record) 可能会更大。 - Leedehai

是的，如果记录的大小很大，那么这可能不值得。但在这种情况下，你只是浪费内存。它可能仍然更快，因为不需要指针解引用。提示：您可以创建一个链式哈希表，其中具有此参数的模板参数。因此，您可以选择如何存储链的第一个元素，以便可以对两种方式进行基准测试，并选择哪种更快。 - geza

Answer 1

让我们来看一下实现。在这里，我们可以看到表格被存储为间接指向记录的平行数组，以及任何缓存的32位哈希码数组，即分开的结构体数组。

实际上：

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

除了容量是动态的，负载因子似乎保持在37.5%至75%之间外，这里还涉及到IT技术相关内容。

对于N个记录，负载因子为F，相比等效链式实现而言，开放地址实现需要N/F指针加N/F整数，而链式实现则需要N*(1+1/F)指针加N整数。在一个典型的64位系统上，开放地址版本大小在 ~4％ 更大和 ~30％更小之间。

然而，正如你所怀疑的那样，主要优点在于缓存效应。除了通过缩小数据平均缓存来减少竞争之外，碰撞过滤归结为对连续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的幂而不是质数表大小。这确保了扩展表时有效地引入一个额外的哈希码位，并将加倍的表分解成两个连续的目标数组，有效地使操作成为缓存友好的线性扫描。

- doynax