TL;DR

inline int32_t hash_index(const uint64_t* keys, uint32_t keys_size, uint64_t key) {
    if (!keys_size || key >= HASH_TOMBSTONE)
        return -1;

    const uint32_t max_distance = keys_size;

    uint32_t i = hash_first_index(key, keys_size);
    uint32_t distance = 0;
    while (keys[i] != key) {
        if (distance > max_distance)
            return -1;
        if (keys[i] == HASH_UNUSED)
            return -1;
        i = (i + 1) & (keys_size - 1); // instead of (i+1) % keys_size
        ++distance;
    }
    return i;
}

背景

这是一个 开放寻址哈希表中 hash 值的查找函数。
参数中：keys 是存储哈希值的数组，keys_size 是表的大小，key 是要查找的 hash 值。返回 hash 值所在的数组下标（如果不存在则返回 -1）。

开放寻址哈希表 hash key 往往很大，要把它塞进数组中，常见的方法就是把 key 做被除数，哈希表数组大小做除数，把余数作为下标结果，可以有效保证它在数组范围 (0~keys_size-1) 内 ，即 key % keys_size。这种计算是频繁的，每次添加、查找都会执行一次或多次。

现在让我们关注求余运算的性能问题，
首先我们写一个求余函数：

int func(int a, int b)
{
    return a % b;
}

用 Visual Studio 开 /O2 编译选项（最大编译优化）来编译此函数，求余运算部分的汇编指令及其占用的CPU时钟周期如下：

mov eax, ebx          ; 1 cycle (零延迟移动，通常被重命名处理)
cdq                   ; 1 cycle  
idiv ecx              ; ≈20-40 cycles (有符号除法，周期数可变)
mov eax, edx          ; 1 cycle

看上去这并不是 1 个 cycle 就可以完成的运算，优化求余运算可以优化哈希表的性能。

解决

这有一个简单实用的 trick：

计算 m % n 时候，当除数 n 是 2 的 k 次幂（k为正整数），m % n 等于 m & (n-1)。
其中 % 为求余（模除），& 为按位与。

而 m & (n-1) 的性能优于 m % n。因为执行同样的逻辑，它只需要 1 个 cycle：

and eax, ebx        ; ebx 等于 keys_size - 1

做到这一切，只需要保持哈希表的总大小为 2 的 幂。

证明

设 n = 2k，
则 m = q⋅2k+r，q 是商，r 是余数。
m & (q⋅2k−1)
= (q⋅2k+r) & (q⋅2k-1)
= (q⋅2k+r) & (2k-1)
这步可以进一步分为高 k 位和低 k 位的计算：
= q⋅2k & (2k-1) + r & (2k-1)

在二进制中：
2k 是 1 后面跟 k 个 0。比如 8 的二进制为 1000。
2k−1 是 k 个 1。比如 8-1 的二进制为 0111。
q⋅2k
= q 的二进制 << k
= q 的二进制后面补 k 个 0
也就是说，q⋅2k 的低 k 位全是 0，而 (2k-1) 的只有 k 位，所以它们位与的结果是 0。
因此，m & (q⋅2k−1)
= q⋅2k & (2k-1) + r & (2k-1)
= r & (2k-1)。

2k 二进制形式为高一位是 1，后面的 k-1 位都是 0；因为余数一定小于除数，所以 r 不会大于 2k， r 的高 1 位一定是 0，后面的 k-1 位都代表自己。所以 r & (2k-1) 的值为 r 本身。
因此，m & (q⋅2k−1) = r。

Q.E.D.

其他

这种优化方法确实需要更多的空间，是用空间换时间的一种办法。

哈希表的使用中，一般时间复杂度更重要些。至于空间分配上的要求比常规方式更高，这其实也符合线性探测法的需求。
线性探测法是用来处理不同 hash 值计算后下标恰好一致的方法，如果下标已经有值了，要不断重新计算可存入的下一个位置，这种开销在哈希表空间使用率高的情况下尤为明显：