Wie generieren eindeutige Ganzzahlen basierend auf GUIDs

Question

Ist es möglich, (sehr wahrscheinlich) eindeutige Integer aus GUIDs zu generieren?

int i = Guid.NewGuid().GetHashCode(); 

int j = BitConverter.ToInt32(Guid.NewGuid().ToByteArray(), 0); 

Welcher ist besser?

Answer 1

Eric Lippert hat eine sehr interessante (wie immer) Post über die probability of hash collisions.

Sie sollen alles lesen, aber er mit dieser sehr anschaulichen Grafik geschlossen:

mit Bezug zu Ihrer Frage, ich mit GetHashCode auch gehen würde, da Kollisionen unvermeidbar oder so sein wird.

Answer 2

Die GetHashCode Funktion wurde speziell entwickelt, um eine gut verteilte Reihe von Ganzzahlen mit einer geringen Kollisionswahrscheinlichkeit zu erstellen, so dass für diesen Anwendungsfall wahrscheinlich das Beste ist, was Sie tun können.

Aber ich bin mir sicher, dass Sie Hashes 128-Bit-Informationen in 32 Bits von Informationen eine Menge von Daten wegwerfen, so wird es ziemlich sicher zu Kollisionen kommen, wenn Sie eine ausreichend große Anzahl von GUIDs haben.

Answer 3

Da der GUID-Speicherplatz größer als die Anzahl der 32-Bit-Ganzzahlen ist, haben Sie garantiert Kollisionen, wenn Sie über genügend GUIDs verfügen. Angesichts dessen, dass Sie dies verstehen und bereit sind, mit Kollisionen umzugehen, wie selten diese auch sein mögen, ist GetHashCode() genau für diesen Zweck konzipiert und sollte bevorzugt werden.

Answer 4

Hier ist die einfachste Art und Weise:

Guid guid = Guid.NewGuid(); 
Random random = new Random(); 
int i = random.Next(); 

Sie werden bemerken, dass guid tatsächlich wird hier nicht verwendet, vor allem, weil es sich mit der es keinen Sinn wäre. Der GUID-Algorithmus von Microsoft verwendet die MAC-Adresse des Computers nicht mehr - GUIDs werden tatsächlich mithilfe eines Pseudozufallsgenerators (basierend auf Zeitwerten) generiert. Wenn Sie also eine zufällige Ganzzahl wünschen, ist es sinnvoller, hierfür die Klasse Random zu verwenden.

Update: tatsächlich, eine GUID mit einem int wahrscheinlich noch schlimmer wäre, erzeugen als nur Random mit („schlechter“ in dem Sinne, dass diese wäre eher Kollisionen erzeugen). Dies liegt daran, dass nicht alle 128 Bits in einer GUID zufällig sind. Im Idealfall möchten Sie die nicht variierenden Bits von einer Hash-Funktion ausschließen, obwohl es viel einfacher wäre, eine Zufallszahl zu generieren, wie ich bereits erwähnt habe. :)

Answer 5

Ein GUID ist ein 128-Bit-Integer (es ist nur in hex anstelle von Basis 10). Mit .NET 4 Verwendung http://msdn.microsoft.com/en-us/library/dd268285%28v=VS.100%29.aspx wie so:

// Turn a GUID into a string and strip out the '-' characters. 
BigInteger huge = BigInteger.Parse(modifiedGuidString, NumberStyles.AllowHexSpecifier) 

Wenn Sie 4 nicht über .NET können Sie auf IntX oder Solver Foundation suchen.

Answer 6

In einer statischen Klasse, behalten Sie eine statische Const-Ganzzahl, dann fügen Sie 1 vor jedem einzelnen Zugriff hinzu (mit einer öffentlichen Get-Eigenschaft). Dadurch wird sichergestellt, dass Sie den gesamten int-Bereich durchlaufen, bevor Sie einen nicht eindeutigen Wert erhalten.

Dies wird einen eindeutigen Integer-Wert innerhalb eines laufenden Prozesses erzeugen.Da Sie nicht explizit definieren, wie einzigartig Ihre Ganzzahl sein soll, wird dies wahrscheinlich passen.

Answer 7

Vielleicht nicht ganze Zahlen, aber kleiner eindeutiger Schlüssel sowieso kürzer dann guids:

http://www.codeproject.com/Articles/14403/Generating-Unique-Keys-in-Net

Answer 8

Wenn Sie durch die 2^32 zu durchbrechen suchen, dann versuchen, diese Methode:

/// <summary> 
/// Generate a BigInteger given a Guid. Returns a number from 0 to 2^128 
/// 0 to 340,282,366,920,938,463,463,374,607,431,768,211,456 
/// </summary> 
    public BigInteger GuidToBigInteger(Guid guid) 
    { 
     BigInteger l_retval = 0; 
     byte[] ba = guid.ToByteArray(); 
     int i = ba.Count(); 
     foreach (byte b in ba) 
     { 
      l_retval += b * BigInteger.Pow(256, --i); 
     } 
     return l_retval; 
    } 

Das Universum wird in eine kalte und dunkle Weite zerfallen, bevor Sie eine Kollision erleben.

Answer 9

Ich hatte eine Anforderung, wo mehrere Instanzen einer Konsolenanwendung benötigt, um eine eindeutige Ganzzahl-ID zu erhalten. Es wird verwendet, um die Instanz zu identifizieren und beim Start zugewiesen. Da die .exe von Hand gestartet wird, habe ich eine Lösung mit den Ticks der Startzeit festgelegt.

Meine Argumentation war, dass es für den Benutzer fast unmöglich wäre, zwei .exe in derselben Millisekunde zu starten. Dieses Verhalten ist deterministisch: Wenn Sie eine Kollision haben, wissen Sie, dass das Problem darin bestand, dass zwei Instanzen gleichzeitig gestartet wurden. Je nach Hashcode, GUID oder Zufallszahlen können Methoden auf unvorhersehbare Weise fehlschlagen.

Ich setze das Datum auf 0001-01-01, addiere die aktuelle Zeit und teile die Ticks durch 10000 (weil ich die Mikrosekunden nicht einstelle), um eine Zahl zu erhalten, die klein genug ist, um in eine ganze Zahl zu passen.

var now = DateTime.Now; 
var zeroDate = DateTime.MinValue.AddHours(now.Hour).AddMinutes(now.Minute).AddSeconds(now.Second).AddMilliseconds(now.Millisecond); 
int uniqueId = (int)(zeroDate.Ticks/10000); 

EDIT: Es gibt einige Vorbehalte. Um Kollisionen unwahrscheinlich, stellen Sie sicher, dass:

• Die Instanzen werden manuell gestartet (mehr als eine Millisekunde auseinander)
• Die ID wird erzeugt einmal pro Instanz, beim Start
• Die ID muss nur einmalig sein in Bezug auf andere Instanzen, die derzeit ausgeführt werden
• Nur eine kleine Anzahl von IDs jemals