哈希表索引生成优化：寻求替代取模的哈希适配方法

我在C语言项目中以哈希表作为核心数据结构，采用SipHash实现作为哈希函数，使用链表法处理冲突。当前生成哈希表索引的代码如下：

size_t genindex(const char *key, const size_t ht_len, const uint8_t *k) {
    uint64_t hash = siphash((const uint8_t *)key, strlen(key), k);
    size_t index = (size_t)(hash & (uint64_t) (ht_len - 1));
    return index;
}

但该方式导致大量冲突，哈希表约60%的空间未被使用，而存储的数据仅约60个元素。我暂不想更换冲突处理方式，希望修改索引生成逻辑。已知哈希表大小初始化时固定，为数据量附近2^i与2(i+1)之间的最近素数，请问除取模外，还有哪些方法可将哈希值适配到哈希表大小ht_len？

可选的索引适配方法 #

1. 乘法散列法 #

利用黄金比例类的常数与哈希值相乘，通过取高位来映射到哈希表大小。对于64位哈希值，推荐使用64位黄金比例常数 11400714819323198485ULL，该常数能让哈希值的高位信息充分参与索引计算，避免仅用低位带来的分布不均。
代码示例：

size_t genindex(const char *key, const size_t ht_len, const uint8_t *k) {
    uint64_t hash = siphash((const uint8_t *)key, strlen(key), k);
    const uint64_t multiplier = 11400714819323198485ULL;
    uint64_t product = hash * multiplier;
    // 计算需要移位的位数，适配素数大小的哈希表
    int shift = 64 - __builtin_clzll(ht_len - 1);
    size_t index = (size_t)((product >> shift) % ht_len);
    return index;
}

2. 高低位混合散列 #

将SipHash输出的高32位与低32位进行异或混合，打破键集可能存在的低位重复相关性，再适配到哈希表大小：

size_t genindex(const char *key, const size_t ht_len, const uint8_t *k) {
    uint64_t hash = siphash((const uint8_t *)key, strlen(key), k);
    uint64_t mixed = (hash >> 32) ^ hash;
    size_t index = (size_t)(mixed % ht_len);
    return index;
}

3. 高位截取法 #

直接使用哈希值的高32位来计算索引，避开低位可能存在的分布偏差：

size_t genindex(const char *key, const size_t ht_len, const uint8_t *k) {
    uint64_t hash = siphash((const uint8_t *)key, strlen(key), k);
    size_t index = (size_t)((hash >> 32) % ht_len);
    return index;
}

关键提示 #

你当前的核心问题是：hash & (ht_len-1)仅适用于2的幂次大小的哈希表，但你的哈希表是素数，素数减1的二进制并非全1结构，位与操作会直接丢弃大量哈希值的有效位，导致索引分布极度不均。优先将位与操作替换为hash % ht_len，这应该能立刻解决大部分冲突问题。

内容的提问来源于stack exchange，提问作者Elyo