C语言哈希代码中哪部分确保结果处于0..m-1范围？

先把代码的计算流程拆解开，一步步分析结果为何落在0...m-1区间：

1. 计算核心中间值 #

(a*x + b) >> 32

• a是64位无符号整数，x是32位无符号整数，两者相乘会得到精确的64位结果（无符号整数运算会自动提升位数，无溢出损失），加上64位的b后仍是64位值。
• 右移32位操作是取这个64位值的高32位（你之前理解反了），最终得到一个范围在0 ~ 2^32-1之间的32位无符号整数，记为y。

2. 缩放映射到目标范围 #

(y * m) >> 32

这一步是将y缩放到0...m-1的核心，原因如下：

• y的取值范围是0 ≤ y ≤ 2^32-1，和m相乘后得到64位精确乘积y*m。
• 右移32位等价于对y*m做整数除法y*m / 2^32并向下取整：
  • 当y=0时，结果为0；
  • 当y=2^32-1时，(2^32-1)*m = m*2^32 - m，除以2^32后向下取整得到m - 1（因为m/2^32 < 1）；
  • 所有中间的y值计算后，结果都会落在0到m-1之间，不会超出这个区间。

举个直观例子：如果m=10，y=2^32-1，则(2^32-1)*10 = 10*2^32 -10，右移32位后结果为9，正好是m-1；若y=2^31，则2^31*10 /2^32 = 5，也在0~9范围内。

另外补充：这种通过乘法+右移的缩放方式，比直接取模y % m的分布更均匀，结合随机64位参数a、b，让这个哈希函数具备强通用哈希的特性，能有效减少碰撞概率。

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