不使用modulo运算符的高效公平多对一映射算法有哪些？

针对你提到的模运算开销高的问题，目前工业界已经有非常多成熟的优化方案，按照适用场景可以分为以下几类：

适用M可调整为2的幂的场景：按位与映射 #

如果业务允许将槽位数量M调整为2的整数次幂（如2、4、8、16等），可以直接用按位与运算替代模运算，二者计算结果完全一致，运算为CPU单周期指令，性能远高于模运算：

• 映射逻辑：对于1~N的元素x，0编号槽位的映射结果为 x & (M - 1)，1编号槽位直接在结果上加1即可
• 示例：M=4（2^2），x=5时，5 & 3 = 1，和5 % 4 = 1结果完全一致

适用M固定不可调整的场景：乘法右移快速范围缩减 #

当M不能设置为2的幂时，可以用「乘法+右移」的组合运算替代模运算，这也是现代编译器优化常量模运算的默认实现方案，性能接近按位与运算，分布均匀度偏差小于0.01%，完全满足公平性要求：

• 针对32位无符号整数x的映射逻辑（0编号槽位）：r = ((uint32_t)x * M) >> 32，得到的r范围就是0~M-1，1编号槽位直接加1即可
• 原理：通过乘法将x的范围拉伸到2^{32量级，右移32位相当于除以2}32取整，最终得到的结果分布和模运算几乎一致

适用顺序遍历1~N的场景：增量计数器 #

如果你是按顺序处理1到N的所有元素，不需要随机查询单个元素的槽位，直接用计数器实现即可，运算开销几乎为0：

• 逻辑：初始化计数器为0，每处理一个元素就将计数器加1，等于M时清零，当前计数器值就是对应的槽位编号

额外说明 #

如果你使用的是C/C++/Rust等编译型语言，当M是编译期常量时，编译器会自动将x % M的模运算优化为上述乘法右移逻辑，不需要手动改写代码，性能和手动优化的版本没有差异。如果需要支持槽位M动态调整、尽量减少槽位变更时的元素迁移，可选用一致性哈希方案，但固定槽位场景下性能低于上述方案。

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