Darf man sich darauf verlassen, dass zufällige Ints einzigartig sind?

Ich habe ein Netzwerkprotokoll implementiert und benötige Pakete mit eindeutigen Bezeichnern. Bisher habe ich nur zufällige 32-Bit-Ganzzahlen generiert und angenommen, dass es astronomisch unwahrscheinlich ist, dass es während der Lebensdauer eines Programms / einer Verbindung zu einer Kollision kommt. Wird dies im Produktionscode allgemein als akzeptable Praxis angesehen, oder sollte man ein komplexeres System entwickeln, um Kollisionen zu verhindern?

Vorsicht vor dem Geburtstagsparadoxon .

Angenommen, Sie generieren eine Folge von Zufallswerten (einheitlich, unabhängig) aus einer Menge der Größe N (in Ihrem Fall N = 2 ^ 32).

Die Faustregel für das Geburtstagsparadoxon besagt dann, dass, sobald Sie ungefähr sqrt (N) -Werte generiert haben, eine Kollision mit einer Wahrscheinlichkeit von mindestens 50% aufgetreten ist, d. H., Dass mindestens zwei identische Werte im vorliegen erzeugte Sequenz.

Für N = 2 ^ 32 ist sqrt (N) = 2 ^ 16 = 65536. Nachdem Sie also ungefähr 65.000 Bezeichner generiert haben, ist es wahrscheinlicher, dass zwei von ihnen kollidieren als nicht! Wenn Sie eine Kennung pro Sekunde generieren, dauert dies weniger als einen Tag. Es ist unnötig zu erwähnen, dass viele Netzwerkprotokolle viel schneller arbeiten.

Es wird allgemein als akzeptabel angesehen, sich darauf zu verlassen, dass Zufallszahlen eindeutig sind, wenn diese Zahlen genügend Bits haben. Es gibt kryptografische Protokolle, bei denen das Wiederholen einer Zufallszahl die gesamte Sicherheit gefährdet. Und solange der verwendete Zufallszahlengenerator keine ernsthaften Sicherheitslücken aufweist, war dies kein Problem.

Einer der Algorithmen zum Generieren von UUIDs generiert effektiv eine ID, die aus 122 zufälligen Bits besteht, und geht davon aus, dass sie eindeutig ist. Zwei der anderen Algorithmen setzen voraus, dass ein auf 122 Bit gekürzter Hash-Wert eindeutig ist, was ungefähr das gleiche Kollisionsrisiko birgt.

Es gibt also Standards, bei denen 122 Bit ausreichen, um eine zufällige ID eindeutig zu machen, aber 32 Bit sind definitiv nicht genug. Bei 32-Bit-IDs dauert es nur etwa 2¹⁶ IDs, bis das Kollisionsrisiko 50% erreicht, da bei 2¹⁶ IDs nahezu 2³¹ Paare vorhanden sind, von denen jedes eine Kollision sein könnte.

Sogar 122 Bits sind weniger, als ich in jedem neuen Design empfehlen würde. Wenn Ihnen die Einhaltung von Standards wichtig ist, verwenden Sie UUIDs. Verwenden Sie andernfalls etwas, das größer als 122 Bit ist.

Die SHA1-Hash-Funktion mit einer Ausgabe von 160 Bit gilt nicht mehr als sicher, was zum Teil daran liegt, dass 160 Bit nicht ausreichen, um die Eindeutigkeit der Ausgaben zu gewährleisten. Moderne Hash-Funktionen haben Ausgänge von 224 bis 512 Bit. Nach dem Zufallsprinzip generierte IDs sollten auf die gleichen Größen abzielen, um die Eindeutigkeit mit einem guten Sicherheitsspielraum zu gewährleisten.

Ich würde diese schlechte Praxis nennen. Zufallszahlen erzeugen einfach keine eindeutigen Zahlen, sie erzeugen einfach Zufallszahlen. Eine zufällige Verteilung enthält wahrscheinlich einige Duplikate. Sie können diesen Umstand annehmbar unwahrscheinlich machen, indem Sie ein Zeitelement hinzufügen. Wenn Sie die aktuelle Zeit in Millisekunden von der Systemuhr erhalten. Etwas wie das:

parseToInt(toString(System.currentTimeMillis()) + toString(Random.makeInt()))

Wird einen langen Weg gehen. Um die Eindeutigkeit zu gewährleisten, müssen Sie UUID / GUID verwenden. Die Generierung kann jedoch teuer sein. Das oben Genannte ist wahrscheinlich ausreichend, da die einzige Möglichkeit einer Überlappung darin besteht, dass die zufällige Generierung ein Duplikat in derselben Millisekunde aufwies.

Dies hängt sowohl von der Ausfallwahrscheinlichkeit als auch von den Folgen des Ausfalls ab.

Ich erinnere mich an eine Debatte zwischen Software- und Hardwareleuten, bei der die Hardwareleute einen Algorithmus mit einer geringen Wahrscheinlichkeit falscher Ergebnisse (etwa 1 Fehler in 100 Jahren) für akzeptabel hielten und die Softwareleute dies für ein Gräuel hielten. Es stellte sich heraus, dass die Hardware-Leute routinemäßig die erwarteten Ausfallraten berechneten und sehr an die Vorstellung gewöhnt waren, dass alles gelegentlich falsche Antworten geben würde, z. B. aufgrund von Störungen, die durch kosmische Strahlung verursacht wurden. Sie fanden es seltsam, dass Software-Leute eine hundertprozentige Zuverlässigkeit erwarteten.

Sicher, Sie haben ziemlich niedrige Wahrscheinlichkeiten dafür, dass zwei zufällige 32-Bit-Ganzzahlen sequenziell sind, aber das ist nicht ganz unmöglich. Die geeignete technische Entscheidung basiert auf den Konsequenzen von Kollisionen, einer Schätzung des von Ihnen generierten Zahlenvolumens, der Lebensdauer, für die Eindeutigkeit erforderlich ist, und der Frage, was passiert, wenn ein böswilliger Benutzer versucht, Kollisionen auszulösen.

Es ist akzeptabel anzunehmen, dass Zufallszahlen eindeutig sind, aber Sie müssen vorsichtig sein.

Angenommen, Ihre Zufallszahlen sind gleichmäßig verteilt, ist die Wahrscheinlichkeit einer Kollision ungefähr (n ^2/2 ) / k, wobei n die Anzahl der von Ihnen generierten Zufallszahlen und k die Anzahl der möglichen Werte ist, die eine "Zufallszahl" annehmen kann.

Sie geben keine astronomisch unwahrscheinliche Zahl an, nehmen wir also 1 zu 2 ³⁰ (ungefähr eine Milliarde). Nehmen wir weiter an, Sie generieren 2 bis ³⁰ Pakete (wenn jedes Paket ungefähr ein Kilobyte an Daten darstellt, bedeutet dies ungefähr ein Terabyte an Gesamtdaten, groß, aber nicht unvorstellbar). Wir brauchen eine Zufallszahl mit mindestens 2 ⁸⁹ möglichen Werten.

Erstens müssen Ihre Zufallszahlen groß genug sein. Eine 32-Bit-Zufallszahl kann maximal 2 ³² mögliche Werte haben. Für einen ausgelasteten Server, der bei weitem nicht hoch genug ist.

Zweitens muss Ihr Zufallsgenerator einen ausreichend großen internen Zustand haben. Wenn Ihr Zufallszahlengenerator nur einen internen 32-Bit-Zustand hat, erhalten Sie, egal wie groß der Wert ist, den Sie daraus generieren, immer noch höchstens 2 ³² mögliche Werte.

Drittens, wenn Sie möchten, dass die Zufallszahlen nicht nur innerhalb einer Verbindung, sondern verbindungsübergreifend eindeutig sind, muss Ihr Zufallszahlengenerator eine gute Ausgangsbasis haben. Dies gilt insbesondere dann, wenn Ihr Programm häufig neu gestartet wird.

Im Allgemeinen sind die "regulären" Zufallszahlengeneratoren in Programmiersprachen für eine solche Verwendung nicht geeignet. Die Zufallszahlengeneratoren, die von Kryptografiebibliotheken bereitgestellt werden, sind im Allgemeinen.

In einige der obigen Antworten ist die Annahme eingebaut, dass der Zufallszahlengenerator tatsächlich "flach" ist - dass die Wahrscheinlichkeit, dass zwei beliebige Zahlen die nächste sind, die gleiche ist.

Das gilt wahrscheinlich nicht für die meisten Zufallsgeneratoren. Die meisten verwenden ein Polynom höherer Ordnung, das wiederholt auf einen Samen angewendet wird.

Das heißt, es gibt viele Systeme, die von diesem Schema abhängen, normalerweise mit UUIDs. Beispielsweise hat jedes Objekt und Asset in Second Life eine zufällig generierte 128-Bit-UUID, und sie kollidieren selten.

Viele Leute haben bereits qualitativ hochwertige Antworten gegeben, aber ich möchte ein paar kleinere Punkte hinzufügen: Erstens ist @nomadictypes Punkt über das Geburtstagsparadoxon ausgezeichnet .

Ein weiterer Punkt: Zufälligkeit ist nicht so einfach zu generieren und zu definieren, wie es die Leute normalerweise annehmen. (Tatsächlich gibt es statistische Tests für die Zufälligkeit ).

Mit dieser sagte, ist es wichtig , der sich bewusst sein , Fallacy der Gambler , der ein statistischer Irrtum ist , wo die Menschen davon ausgehen , dass unabhängige Ereignisse irgendwie gegenseitig beeinflussen. Zufällige Ereignisse sind in der Regel statistisch unabhängig voneinander. Wenn Sie also zufällig eine "10" generieren, ändert dies nichts an Ihrer zukünftigen Wahrscheinlichkeit, im geringsten mehr "10" zu generieren. (Vielleicht könnte jemand eine Ausnahme von dieser Regel finden, aber ich würde erwarten, dass dies für so ziemlich alle Zufallszahlengeneratoren der Fall ist.)

Wenn Sie also davon ausgehen könnten , dass eine ausreichend lange Folge von Zufallszahlen eindeutig ist, wären dies keine Zufallszahlen, da dies ein klares statistisches Muster wäre. Außerdem würde dies bedeuten, dass jede neue Zahl kein eigenständiges Ereignis ist. Wenn Sie beispielsweise eine 10 generieren, würde dies bedeuten, dass die Wahrscheinlichkeit, zukünftige 10 zu generieren, 0% beträgt (dies könnte möglicherweise nicht passieren) Das würde bedeuten, dass Sie die Wahrscheinlichkeit erhöhen würden, eine andere Zahl als 10 zu erhalten (dh je mehr Zahlen Sie generieren, desto höher ist die Wahrscheinlichkeit für jede der verbleibenden Zahlen).

Noch etwas zu beachten: Die Chance, den Powerball für ein einziges Spiel zu gewinnen, liegt meines Wissens bei etwa 1 zu 175 Millionen. Allerdings sind die Chancen von jemandem gewinnen deutlich höher als das. Sie interessieren sich mehr für die Wahrscheinlichkeit, dass jemand "gewinnt" (dh ein Duplikat ist) als für die Wahrscheinlichkeit, dass eine bestimmte Zahl "gewinnt" / ein Duplikat ist.

Es spielt keine Rolle, wie viele Bits Sie verwenden - Sie können NICHT garantieren, dass zwei "Zufallszahlen" unterschiedlich sind. Stattdessen schlage ich vor, dass Sie so etwas wie die IP-Adresse oder eine andere Netzwerkadresse des Computers und eine fortlaufende Nummer verwenden, vorzugsweise eine HONKIN 'BIG-fortlaufende Nummer - 128 Bit (offensichtlich ohne Vorzeichen) klingen nach einem guten Start, aber 256 wären besser.

Nein natürlich nicht. Sofern Sie keine ersatzlosen Samples verwenden, besteht die Möglichkeit einer - wenn auch geringen - Duplizierung.