快速计算Hash值的一种变体算法
2024-01-09 20:53:06
快速Hash算法的实现
当使用%求一个随机数,在区间【0,N-1】的索引位置时,性能并不会高效,因为mod指令通常需要多个CPU周期才能完成,因此Blog( A fast alternative to the modulo reduction)中提出一个变体算法,来消除取模运算,取而代之的是乘法与位移的联合操作。
例如,对于32位整型的随机数rand_x
,计算在[0, N-1]区间上的HASH值算法如下:
int index = (int) ((long) rand_x * N) >>> 32
性能测试
Table 1. CPU cycles per Call on 32-bit
modulo reduction | fast range |
---|---|
8.1 | 2.2 |
从上表可以看到,在32位的数上计算HASH值,Blog中的算法要比取模运算快4倍。
文章来源:https://blog.csdn.net/u014445499/article/details/135487946
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!