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

EN

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

有效地：

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

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

对于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的幂，而不是素表大小。这确保了表的增长会有效地带来额外的哈希码位，并将加倍的表去交织成两个连续的目标数组，从而有效地使操作成为一个对缓存友好的线性扫描。