64位哈希码碰撞概率
64位哈希码碰撞概率
提问于 2014-02-26 00:09:39
“数值累进”一书提供了一种计算64位哈希码的方法，以减少碰撞次数。
该算法在2.shtml上显示，并在此复制以供参考：
private static final createLookupTable() {
byteTable = new long[256];
long h = 0x544B2FBACAAF1684L;
for (int i = 0; i < 256; i++) {
for (int j = 0; j < 31; j++) {
h = (h >>> 7) ^ h;
h = (h << 11) ^ h;
h = (h >>> 10) ^ h;
}
byteTable[i] = h;
}
return byteTable;
}
public static long hash(CharSequence cs) {
long h = HSTART;
final long hmult = HMULT;
final long[] ht = byteTable;
final int len = cs.length();
for (int i = 0; i < len; i++) {
char ch = cs.charAt(i);
h = (h * hmult) ^ ht[ch & 0xff];
h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];
}
return h;
}我的问题：
1)考虑到所谓的生日悖论，是否有一个计算碰撞概率的公式？
( 2)您能估计碰撞的概率(即两个键散列到相同的值)吗？比如说1000把钥匙和10,000把钥匙？
编辑：重新措辞/更正的问题3
( 3)假设合理数目的键(例如少于10,000个键)的碰撞是不可能的，这样，如果两个哈希码是相同的，我们就可以说密钥是相同的，而无须进一步检查？例如：
static boolean equals(key1, key2) {
if (key1.hash64() == key2.hash64())
return true; // probability of collision so low we don't need further check
return false;
}这不是为了安全性，但是执行速度是必需的，因此避免对密钥进行进一步检查将节省时间。如果概率如此之低，比方说小于(十亿分之一/10万密钥)，它可能是可以接受的。
蒂娅！
Stack Overflow用户
发布于 2014-02-26 04:22:46
我将对其他答案中提供的精确公式提供一个粗略的近似；这个近似可能会帮助您回答#3。粗略的近似是，用一个好的散列算法，k键和n个可能的散列值发生碰撞的概率大约是(k^2)/2n，对于k << n，对于一个64位散列的100000个密钥，是10^10 / 32x10^18，或者大约是30亿的1。
但是，我怀疑如果您不检查碰撞上的实际键值，那么您将更有可能发现哈希算法“不够好”，毕竟。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22029012
复制相关文章
相似问题
腾讯云开发者
