Wahrscheinlichkeit von 64-bit-Hash-Code-Kollisionen

Dem Buch Numerical Recipes bietet eine Methode zur Berechnung der 64-bit-hash-codes, um die Zahl der Kollisionen reduzieren.

Ist der Algorithmus gezeigt, bei der http://www.javamex.com/tutorials/collections/strong_hash_code_implementation_2.shtml und kopiert wird hier zur Referenz:

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

Meine Fragen:

1) gibt es eine Formel zur Abschätzung der Wahrscheinlichkeit von Kollisionen unter Berücksichtigung der sogenannte Geburtstags-Paradoxon?

2) wie hoch schätzen Sie die Wahrscheinlichkeit einer Kollision (ich.e zwei Schlüssel, hash auf den gleichen Wert)? Sagen wir mal mit 1.000-Tasten und mit 10.000 keys?

BEARBEITEN: umformuliert/korrigierte Frage 3

3) Ist es sicher davon ausgehen, dass eine Kollision von einer angemessenen Anzahl von Tasten (sagen wir, weniger als 10.000 keys) ist so unwahrscheinlich, so dass, wenn 2 hash-codes sind die gleichen, können wir sagen, dass die Tasten sind die gleichen ohne weitere überprüfung? z.B.

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

Dies ist nicht für die Sicherheit, aber die Ausführungsgeschwindigkeit ist zwingend erforderlich, damit die Vermeidung von weiteren Prüfungen der Tasten Zeit sparen. Wenn die Wahrscheinlichkeit so gering ist, sagen wir weniger als (1 in 1 Milliarde für 100.000 Schlüssel) wird es wahrscheinlich akzeptabel sein.

TIA!

Nur ein kurzes: preshing.com/20110504/hash-collision-probabilities

InformationsquelleAutor isapir | 2014-02-26

29

Gibt es eine Formel zur Abschätzung der Wahrscheinlichkeit von Kollisionen unter Berücksichtigung der sogenannte Geburtstags-Paradoxon?

Mit dem Birthday Paradox Formel ist einfach sagt Ihnen, an welchem Punkt Sie anfangen müssen, sich Gedanken über eine Kollision passiert. Dies ist bei rund Sqrt[n] wo n ist die gesamte Anzahl der möglichen hash-Werte. In diesem Fall n = 2^64 so den Geburtstag Paradox Formel sagt Ihnen, dass, solange die Anzahl der Tasten ist deutlich weniger als Sqrt[n] = Sqrt[2^64] = 2^32 oder etwa 4 Milliarden, die Sie nicht brauchen, um über Kollisionen. Je höher die n, desto genauer wird diese Schätzung. In der Tat ist die Wahrscheinlichkeit p(k), dass eine Kollision auftreten wird, mit k Tasten Ansätze eine Schritt-Funktion, wie n größer wird, wo der Schritt erfolgt auf k=Sqrt[n].

Können Sie schätzen die Wahrscheinlichkeit einer Kollision (ich.e zwei Schlüssel, hash auf den gleichen Wert)? Sagen wir mal mit 1.000-Tasten und mit 10.000 keys?

Vorausgesetzt, die hash-Funktion ist gleichmäßig verteilt, es ist einfach die Ableitung der Formel.
```
p(no collision for k keys) = 1 * (n-1)/n * (n-2)/n * (n-3)/n * ... * (n-(k-1))/n
```
Diese Formel folgt direkt aus beginnend mit 1 key: Die Wahrscheinlichkeit, dass keine Kollision mit Taste 1 ist natürlich 1. Die Wahrscheinlichkeit, dass keine Kollision mit 2 Schlüsseln ist 1 * (n-1)/n. Und so weiter für alle k Tasten. Bequem, Mathematica hat eine Pochhammer[] Funktion für diesen Zweck zum Ausdruck dieser lapidar:
```
p(no collision for k keys) = Pochhammer[n-(k-1),k]/n^k
```
Dann, die Wahrscheinlichkeit zu berechnen, dass es mindestens 1 Kollision für k Tasten, subtrahieren von 1:
```
p(k) = 1 - p(no collision for k keys) = 1 - Pochhammer[n-(k-1),k]/n^k
```
Mithilfe von Mathematica, kann man berechnen für n=2^64:
- p(1,000) = 1-3,7*10¹³
- p(10,000) = 1-3,7*10¹¹
- p(1,000,000) = 1-3,7*10⁷
Ist es sicher davon ausgehen, dass eine Kollision von einer angemessenen Anzahl von Tasten (sagen wir, weniger als 10.000 keys) ist so unwahrscheinlich, so dass, wenn 2 hash-codes sind die gleichen, können wir sagen, dass die Tasten sind die gleichen, ohne jegliche weitere Prüfung?

Zur Beantwortung dieser genau, hängt von der Wahrscheinlichkeit, dass 2 von den 10.000 keys identisch waren. Was wir suchen ist:
```
p(a=b|h(a)=h(b)) = The probability that a=b given h(a)=h(b)
```
wo a und b Schlüssel sind, die (möglicherweise identisch) und h() ist die hashing-Funktion beinhalten. Wir können Bayes' Theorem direkt:
```
p(a=b|h(a)=h(b)) = p(h(a)=h(b)|a=b) * p(a=b) /p(h(a)=h(b))
```
Sehen wir sofort, dass p(h(a)=h(b)|a=b) = 1 (wenn a=b dann natürlich h(a)=h(b)), so erhalten wir
```
p(a=b|h(a)=h(b)) = p(a=b) /p(h(a)=h(b))
```
Wie Sie sehen können, hängt von p(a=b) was ist die Wahrscheinlichkeit, dass a und b sind eigentlich die gleichen Schlüssel. Dies hängt davon ab, wie die Gruppe von 10.000 keys ausgewählt wurden in den ersten Platz. Die Berechnungen für die letzten zwei Fragen übernehmen alle Tasten sind ausgeprägt, so dass mehr Informationen auf dieses Szenario wird benötigt, um vollständig zu beantworten.

Gute Antwort auf Nummer 2. Nummer 1, es gibt keinen "Schritt" auf einen beliebigen Wert; eher, was passiert bei etwa sqrt(n) ist, dass eine Kollision wahrscheinlicher als nicht. Auf Nummer 3, die Sie beantwortet die Frage, die er wohl gemeint, zu Fragen, aber die Antwort auf die Frage, die er eigentlich gefragt - "wenn 2 hash-codes anders sind, können wir sagen, dass die Tasten anders sind, ohne weitere überprüfung" ist ja immer da, wenn die Schlüssel die gleichen waren, Sie würden hash an den gleichen hash.
vielen Dank für eine ausgezeichnete Antwort. dies ist nicht eine Frage der Bequemlichkeit, sondern viel mehr eine Frage der Geschwindigkeit. es scheint, wie Kollision ist unwahrscheinlich, auch für 100.000 oder 1 Millionen keys (ich habe versucht die zu geben Sie Ihre Gleichung in WolframAlpha, aber konnte es nicht zu funktionieren).
Tut mir Leid, aber nur nach dem Lesen @WarrenDew 's Kommentar habe ich gemerkt, dass ich Durcheinander Frage 3 also bearbeitete ich es jetzt.
Über die step-Funktion: das Schlüsselwort ist Konzepte. Für jede endliche n, ist die Wahrscheinlichkeit Funktion einer Kollision p(k) ist monoton Steigend, so dass p(1)=0 und p(k)=1 für k>n. Als n unendlich sind, p(k) Ansätze der Einheit step-Funktion, und der Schritt erfolgt auf k=Sqrt[n]. Das ist einfach das mathematische Ergebnis der Anwendung precalculus Grenzen p(k) (wenn auch etwas langwierig). Für Nummer 3, du hast Recht; ich antwortete auf die Frage der OP bedeutete zu Fragen. 🙂
nochmals vielen Dank für eine hervorragende Antwort!

InformationsquelleAutor Matt
1

Gibt es eine Formel zur Abschätzung der Wahrscheinlichkeit von Kollisionen unter Berücksichtigung der sogenannte Geburtstags-Paradoxon?

Finden Sie unter: Geburtstag Angriff.

Vorausgesetzt, die Verteilung der hashes ist einheitlich, die Wahrscheinlichkeit für eine Kollision für n Schlüssel ist ca. n²/2⁶⁵.

Ist es sicher davon ausgehen, dass eine Kollision von einer angemessenen Anzahl von Tasten (sagen wir, weniger als 10.000 keys) ist so unwahrscheinlich, so dass, wenn 2 hash-codes anders sind, können wir sagen, dass die Tasten anders sind, ohne weitere überprüfung?

Es ist nur sicher, wenn Sie Verwendung einer kryptographischen hash-Funktion. Auch wenn Sie tolerieren können, einen Fehler alle 3*10¹¹ mal, können Sie haben die Möglichkeit zu erwägen, dass der Eingang ist speziell gebaut, um erstellen Sie eine hash-Kollision, als ein Angriff auf Ihr Programm.

danke für deine Antwort. Ich von Ihnen positiv bewertet werden. p.s. - das ist nicht für die Sicherheit, die ich geklärt, die Frage zu Bearbeiten.

InformationsquelleAutor Anton
1

Werde ich eine grobe Annäherung an die exakten Formeln in den anderen Antworten; die Annäherung kann in der Lage sein, um Ihnen zu helfen Antwort #3. Die grobe Näherung ist, dass die Wahrscheinlichkeit für eine Kollision Auftritt mit k-Tasten und n möglich, hash-Werte mit einem guten Hash-Algorithmus ist in etwa (k^2)/2n, für k << n ist. Für 100.000 keys mit 64 bit-hash, das ist 10^10 /32x10^18 oder etwa 1, 3 Milliarden.

Ich vermute aber, dass wenn Sie die Prüfung nicht die eigentlichen Schlüssel-Werte auf Kollision, es gibt eine größere chance, Sie ' ll finden Sie heraus, den Hash-Algorithmus ist nicht "gut" genug, nachdem alle.

InformationsquelleAutor Warren Dew
1

1) gibt es eine Formel zur Abschätzung der Wahrscheinlichkeit von Kollisionen unter
berücksichtigt das sogenannte Geburtstags-Paradoxon?

Die Wahrscheinlichkeit, eine einzige Kollision Auftritt, hängt von der set-Taste generiert die hash-Funktion ist einheitlich, die wir tun können folgenden die Wahrscheinlichkeit zu berechnen, dass die Kollision nicht Auftritt, die sich an die generation der k-Tasten wie folgt :-
```
x = hash size
p(k=2) = (x-1)/x
p(k=3) = p(k=2)*(x-2)/x
..
p(k=n) = (x-1)*(x-2)..(x-n+1)/x^n

p(k=n) ~ e^-(n*n)/2x

p(collision|k=n) = 1-p(k=n) = 1 - e^(-n^2)/2x
p(collision) > 0.5 if n ~ sqrt(x)
```
Daher, wenn sqrt(2^64) Schlüssel, ist 2^32 Schlüssel erzeugt es eine höhere chance, dass es einer einzelnen Kollision.

2) wie hoch schätzen Sie die Wahrscheinlichkeit einer Kollision (ich.e zwei Schlüsseln,
hash auf den gleichen Wert)? Sagen wir mal mit 1.000-Tasten und mit 10.000
Schlüssel?
```
x = 2^64 
Use the formula pc(k=n) = 1 - e^-(n^2)/2x
```
3) Ist es sicher davon ausgehen, dass eine Kollision von einer angemessenen Anzahl von
Schlüssel (sagen wir, weniger als 10.000 keys) ist so unwahrscheinlich, so dass, wenn 2 hash
die codes sind die gleichen, können wir sagen, dass die Tasten sind die gleichen ohne
weiter überprüfen?

Dies ist eine sehr interessante Frage, denn es hängt von der Größe des key space. Nehmen wir an, Ihr Schlüssel generiert zufällig aus dem Raum von size = s - und hash-Raum ist x=2^64 wie Sie bereits erwähnt. Wahrscheinlichkeit einer Kollision ist Pc(k=n|x) = 1-e^(-n^2)/2x. Wenn die Wahrscheinlichkeit der Wahl der gleiche Schlüssel im Schlüssel-Raum ist P(k=n|s) = 1-e^(-n^2)/2s . Für Sie, um sicher zu sein, dass, wenn hash gleich, dann Tasten sind die gleichen:-
```
P(k=n|s) > Pc(k=n|x)
1-e^-(n^2/2s) > 1-e^-(n^2/2x) 
n^2/2s > n^2/2x 
s < x
s < 2^64
```
Daher zeigt es sich, dass für die Tasten zu gleich, wenn hash gleich, die Taste set-Größe muss kleiner als 2^64 ca sonst gibt es eine chance der Kollision in der hash-mehr als in key-set. Das Ergebnis ist unabhängig von der Anzahl der generierten Schlüssel.

InformationsquelleAutor Vikram Bhat

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.