Probabilité de collisions de code de hachage 64 bits

Le livre Numérique Recettes propose une méthode pour calculer 64 bits des codes de hachage afin de réduire le nombre de collisions.

L'algorithme est illustré à http://www.javamex.com/tutorials/collections/strong_hash_code_implementation_2.shtml et est copié ici pour référence:

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

Mes questions:

1) Est-il une formule pour estimer la probabilité de collisions en tenant compte de la soi-disant Paradoxe d'Anniversaire?

2) Pouvez-vous estimer la probabilité de collision (j'.e deux clés de hachage à la même valeur)? Disons qu'avec les touches de 1 000 et 10 000 clés?

MODIFIER: reformulé/corrigé de la question 3

3) Est-il sûr de supposer que, d'une collision avec un nombre raisonnable de touches (disons, moins de 10 000 clés) est donc improbable de sorte que si 2 des codes de hachage sont les mêmes, nous pouvons dire que les touches sont les mêmes sans aucune autre vérification? par exemple,

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

Ce n'est pas pour la sécurité, mais la vitesse d'exécution est impératif afin d'éviter de nouvelles vérifications des touches de gagner du temps. Si la probabilité est tellement faible, disons moins de (1 à 1 milliard de dollars pour 100,000 clés), il sera probablement acceptable.

TIA!

source d'informationauteur isapir | 2014-02-26