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!