isa*_*pir 13 algorithm math statistics hash probability
"数字配方"一书提供了一种计算64位哈希码的方法,以减少冲突次数.
该算法显示在http://www.javamex.com/tutorials/collections/strong_hash_code_implementation_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个密钥)的碰撞是如此不可能是否安全,以便如果2个哈希码相同,我们可以说密钥是相同的而无需进一步检查？例如
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;
}
这不是为了安全,但执行速度是必要的,因此避免进一步检查密钥将节省时间.如果概率很低,比如说小于(100,000个键中的十分之一十亿)那么它可能是可以接受的.
TIA!
Mat*_*att 35
考虑到所谓的生日悖论,是否存在估计碰撞概率的公式？
使用生日悖论公式只是告诉你需要在什么时候开始担心发生碰撞.这是在周围Sqrt[n],其中n有可能哈希值的总数.在这种情况下n = 2^64,生日悖论公式告诉您,只要密钥数量明显少于Sqrt[n] = Sqrt[2^64] = 2^32或大约40亿,您就不必担心冲突.越高n,估计越准确.事实上,p(k)随着k键n变得越大,在步骤发生时,键发生碰撞的概率越大k=Sqrt[n].
你能估计一下碰撞的概率(即两个键散列到相同的值)吗？让我们说1000键和10,000键？
假设散列函数是均匀分布的,则可以直接推导出公式.
p(no collision for k keys) = 1 * (n-1)/n * (n-2)/n * (n-3)/n * ... * (n-(k-1))/n
该公式直接从1键开始:与1键无冲突的概率当然是1.与2键没有冲突的概率是1 * (n-1)/n.所有k键都是如此.方便的是,Mathematica有一个Pochhammer []函数用于此目的简洁地表达:
p(no collision for k keys) = Pochhammer[n-(k-1),k]/n^k
然后,要计算k密钥至少发生1次碰撞的概率,请将其从1减去:
p(k) = 1 - p(no collision for k keys) = 1 - Pochhammer[n-(k-1),k]/n^k
使用Mathematica,可以计算n=2^64:
是否可以安全地假设合理数量的键(例如,少于10,000个键)的碰撞是如此不可能,以便如果2个哈希码相同,我们可以说键是相同的而没有任何进一步的检查？
准确地回答这个问题取决于10,000个密钥中的2个是相同的概率.我们要找的是:
p(a=b|h(a)=h(b)) = The probability that a=b given h(a)=h(b)
其中a和b是键(可能相同)并且h()是散列函数.我们可以直接应用贝叶斯定理:
p(a=b|h(a)=h(b)) = p(h(a)=h(b)|a=b) * p(a=b) / p(h(a)=h(b))
我们立刻就会看到p(h(a)=h(b)|a=b) = 1(a=b当然是h(a)=h(b)这样),所以我们得到了
p(a=b|h(a)=h(b)) = p(a=b) / p(h(a)=h(b))
正如你可以看到这取决于p(a=b)它是概率a和b实际上是相同的密钥.这取决于首先如何选择10,000组密钥.前两个问题的计算假设所有键都是不同的,因此需要有关此方案的更多信息才能完全回答它.