Probabilidade de colisões de código hash de 64 bits
O livro Numerical Recipes oferece um método para calcular códigos de hash de 64 bits, a fim de reduzir o número de colisões.
O algoritmo é mostrado emhttp://www.javamex.com/tutorials/collections/strong_hash_code_implementation_2.shtml e é copiado aqui para referência:
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;
}
Minhas perguntas:
1) Existe uma fórmula para estimar a probabilidade de colisões levando em consideração o chamado Paradoxo do Aniversário?
2) Você pode estimar a probabilidade de uma colisão (ou seja, duas chaves com o mesmo valor)? Digamos que com 1.000 chaves e com 10.000 chaves?
EDITAR: pergunta reformulada / corrigida 3
3) É seguro assumir que uma colisão de um número razoável de chaves (digamos, menos de 10.000 chaves) é tão improvável que, se 2 códigos de hash forem iguais, podemos dizer que as chaves são iguais sem nenhuma verificação adicional? por exemplo.
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;
}
Isso não é por segurança, mas a velocidade de execução é imperativa, portanto, evitar verificações adicionais das chaves economizará tempo. Se a probabilidade for tão baixa, diga menos que (1 em 1 bilhão para 100.000 chaves), provavelmente será aceitável.
TIA!