El libro Numerical Recipes ofrece un método para calcular códigos hash de 64 bits para reducir el número de colisiones.

El algoritmo se muestra enhttp://www.javamex.com/tutorials/collections/strong_hash_code_implementation_2.shtml y se copia aquí para referencia:

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;
}

Mis preguntas:

1) ¿Existe una fórmula para estimar la probabilidad de colisiones teniendo en cuenta la llamada paradoja del cumpleaños?

2) ¿Puede estimar la probabilidad de una colisión (es decir, dos claves que tienen el mismo valor hash)? ¿Digamos con 1,000 llaves y con 10,000 llaves?

EDITAR: pregunta reformulada / corregida 3

3) ¿Es seguro asumir que una colisión de un número razonable de claves (digamos, menos de 10,000 claves) es tan improbable que si 2 códigos hash son iguales, podemos decir que las claves son las mismas sin más controles? p.ej.

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;
}

Esto no es por seguridad, pero la velocidad de ejecución es imprescindible, por lo que evitar verificaciones adicionales de las teclas ahorrará tiempo. Si la probabilidad es tan baja, digamos menos de (1 en 1 billón por 100,000 llaves), probablemente será aceptable.

TIA!