64位哈希码碰撞概率
“数值累进”一书提供了一种计算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万密钥)，它可能是可以接受的。
蒂娅！
回答 2
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用户
发布于 2014-02-26 05:16:46
1)考虑到所谓的生日悖论，是否有一个计算碰撞概率的公式？
单个碰撞发生的概率取决于生成的密钥集，因为哈希函数是一致的，我们可以这样做来计算在生成k键时不发生碰撞的概率如下：
x = hash size
p(k=2) = (x-1)/x
p(k=3) = p(k=2)*(x-2)/x
..
p(k=n) = (x-1)*(x-2)..(x-n+1)/x^n
p(k=n) ~ e^-(n*n)/2x
p(collision|k=n) = 1-p(k=n) = 1 - e^(-n^2)/2x
p(collision) > 0.5 if n ~ sqrt(x)因此，如果生成sqrt(2^64)密钥，即2^32密钥，则存在单个冲突的可能性更高。
( 2)您能估计碰撞的概率(即两个键散列到相同的值)吗？比如说1000把钥匙和10,000把钥匙？
x = 2^64
Use the formula pc(k=n) = 1 - e^-(n^2)/2x( 3)假设合理数目的键(例如少于10,000个键)的碰撞是不可能的，这样，如果两个哈希码是相同的，我们就可以说密钥是相同的，而无须进一步检查？
这是一个非常有趣的问题，因为它取决于键空间的大小。假设您的密钥是从size = s空间随机生成的，而哈希空间是x=2^64 (如前所述)。碰撞概率为Pc(k=n|x) = 1-e^(-n^2)/2x。如果在密钥空间中选择相同密钥的概率为P(k=n|s) = 1-e^(-n^2)/2s。若要确保散列相同，则键是相同的：-
P(k=n|s) > Pc(k=n|x)
1-e^-(n^2/2s) > 1-e^-(n^2/2x)
n^2/2s > n^2/2x
s < x
s < 2^64因此，若要使键相同，如果哈希相同，则键集大小必须小于2^64的大小，否则哈希中的冲突可能大于键集中的冲突。结果与生成的键数无关。
https://stackoverflow.com/questions/22029012
复制相似问题
腾讯云开发者
