Hash 浅谈：计算与碰撞
- 培训职业
- 2025-05-05 01:45:07
在使用 Doris 的 Bitmap 类型做用户统计时，我遇到了一个问题，Doris 字符串转数字的 Hash 函数无法满足需求。我寻找了一个可以生成 32 位数字且将碰撞率控制在千万分之一以下的 Hash 函数，同事打趣我找到这样的函数后，也请他帮我找找又大又便宜的房子。经过一番研究，我发现这样的函数确实存在，但并非易事。
Hash 函数将任意长度的数据映射为固定长度的数据，其具体计算过程以 MurmurHash 为例。该算法快速高效，同时能提供良好的分布和低碰撞率，通过乘法和旋转运算处理输入数据。算法初始化散列值为随机值，逐个处理输入数据的4字节块，并对哈希值进行更新。处理完所有数据后，返回最终的散列值。
MurmurHash 通过参数 m 和 r 进行乘法和旋转运算，这些值是开发者调试出来的、认为效果较好的值。&0xff 操作确保字节值被视为无符号值，以在 Java 中实现转为无符号值。长度&~3 等同于将长度向下舍入到4的倍数，通过将长度的二进制表示的最后两位清零实现。
了解 Hash 计算过程后，我们来探讨碰撞率。碰撞率是指两个不同的输入数据经过 Hash 函数计算后得到相同哈希值的概率。由于哈希值长度固定而输入数据长度不确定，碰撞是不可避免的。计算碰撞率可以将其转换为一个概率问题，即在包含 N 个可能哈希值的空间内，随机生成 k 个值至少有两个值相等的概率。
对于计算公式，当 N 趋于无穷大时，可以用简化表达式来计算碰撞概率。通过代入公式计算，可以发现如果仅生成29个数字，32位数字的 Hash 值碰撞率可以在千万分之一以下。这个答案虽然可能看似不那么令人满意，但它回答了问题，同时也学到了不少关于 Hash 函数的知识。
参考资料：公众号：大数据小屋
多重随机标签