每次使用哈希的时候 , 多少都有些忐忑 , 尤其是在打cf的时候,房间里要是有个叉哈希狂魔是非常恐怖的 ,如果写多模数哈希的话,又怕太慢被卡。昨天vp了一场cf 比赛看评论区的时候 看到了一个非常优秀的做法 , 在这里mark一下 , 也分享给大家。
u64 mix (u64 o) {
o += 0x9e3779b97f4a7c15;
o = (o^(o>>30))*0xbf58476d1ce4e5b9;
o = (o^(o>>27))*0x94d049bb133111eb;
return o ^ (o>>31);
}
这个操作不是很罕见吧,这是一种非常常见的哈希函数,通常称为 “MurmurHash3”。该函数的目标是将一个64位整数o转换为另一个64位整数哈希值。它基于一些魔数和位运算。
首先,将0x9e3779b97f4a7c15添加到o中,这是MurmurHash3算法中常用的一个常数。
然后,对o执行两次异或和乘法运算,每次对o右移30位,27位,分别使用0xbf58476d1ce4e5b9和0x94d049bb133111eb两个常数。这一步是为了将o与一些随机化的值进行混合,以增加哈希值的分布性。
最后,o右移31位并与o异或,这是为了进一步混淆o的比特位,并使哈希值在均匀分布方面更加均衡。
完整代码:https://www.acwing.com/solution/content/179335/
大佬牛逼,这是什么操作我看蒙了
大佬是我无知,能稍微解释一下么Hhhh
大佬是我无知,能稍微解释一下么Hhhh