Einzigartiger Code im Tinyurl-Stil: potenzieller Algorithmus zur Vermeidung von Kollisionen

8

Ich habe ein System, das einen eindeutigen sechsstelligen Code benötigt, um ein Objekt darzustellen, und ich versuche mir einen guten Algorithmus zur Erzeugung dieser Objekte vorzustellen. Hier sind die Vorbedingungen:

  • Ich verwende ein Basis-20-System (keine Großbuchstaben, Zahlen, Vokale oder l, um Verwirrung und ungezogene Wörter zu vermeiden)
    • Die Basis-20 erlaubt 64 Millionen Kombinationen
  • Ich werde etwa 5-10.000 Einträge gleichzeitig einfügen, also würde ich theoretisch Masseneinfügungen verwenden, was bedeutet, dass die Verwendung eines eindeutigen Schlüssels wahrscheinlich nicht effizient oder hübsch ist (besonders wenn es viele Kollisionen gibt) )
  • Es ist nicht ausgeschlossen, 10% der Kombinationen auszufüllen, damit ein hohes Potential für viele Kollisionen besteht
  • Ich möchte sicherstellen, dass die Codes nicht aufeinanderfolgend sind

Ich hatte eine Idee, die klang, als würde es funktionieren, aber ich bin nicht gut genug in Mathe, um herauszufinden, wie man es implementiert: Wenn ich bei 0 anfange und um N inkrementiere, dann konvertiere ich zu base-20 Es sollte ein Wert für N sein, der es mir erlaubt, jeden Wert von 0-63.999.999 zu zählen, bevor ich einen wiederhole.

Gehen Sie beispielsweise von 0 bis 9 mit N = 3 (also 10 mod 3): 0, 3, 6, 9, 2, 5, 8, 1, 4, 7.

Gibt es eine magische mathematische Methode, um Werte von N für eine größere Zahl herauszufinden, die in der Lage ist, durch den gesamten Bereich zu zählen, ohne sich zu wiederholen? Im Idealfall würde die Nummer, die ich auswähle, sozusagen um das Set springen, so dass es nicht offensichtlich ist, dass es ein Muster gibt, aber ich bin mir nicht sicher, wie das möglich ist.

Alternativ könnte ein Hashalgorithmus funktionieren, der die Eindeutigkeit für Werte von 0-64 Millionen garantiert, aber ich bin viel zu blöd um zu wissen, ob das möglich ist.

    
Dan Breen 10.08.2009, 23:44
quelle

6 Antworten

8

Alles was Sie brauchen ist eine Zahl, die keine Faktoren mit Ihrem Schlüsselraum teilt. Am einfachsten ist es, eine Primzahl zu verwenden. Sie können nach großen Primzahlen suchen oder Ссылка

verwenden     
Cullen Walsh 10.08.2009, 23:48
quelle
1

Jede Primzahl, die kein Faktor der Länge der Sequenz ist, sollte in der Lage sein, die Sequenz ohne Wiederholung zu überspannen. Für 64000000, das heißt, Sie sollten nicht 2 oder 5 verwenden. Natürlich, wenn Sie nicht wollen, dass sie nacheinander erzeugt werden, ist es wahrscheinlich auch nicht sehr gut, sie 2 oder 5 auseinander zu erzeugen. Ich persönlich mag die Nummer 73973!

    
Nick Lewis 10.08.2009 23:50
quelle
1

Es gibt eine andere Methode, um ein ähnliches Ergebnis zu erhalten (das Springen über die gesamte Menge der Werte, ohne sich zu wiederholen), ohne die Primzahlen zu benutzen - mit Sequenzen maximaler Länge , die Sie mit speziell konstruierten Schieberegistern erzeugen können.

    
Andrew Y 11.08.2009 00:21
quelle
0

Meine Mathematik ist ein bisschen rostig, aber ich denke, Sie müssen nur sicherstellen, dass der GCF von N und 64 Millionen 1 ist. Ich würde mit einer Primzahl gehen (die sich nicht gleichmäßig in 64 Millionen teilt) Fall jedoch.

    
Jonathan Rupp 10.08.2009 23:50
quelle
0

@Nick Lewis:

Nun, nur wenn die Primzahl 64 Millionen nicht teilt. Für die Zwecke des Fragestellers wären also Zahlen wie 2 oder 5 wahrscheinlich nicht ratsam.

    
quanticle 10.08.2009 23:52
quelle
-3

Erfinde das Rad nicht neu: Ссылка

    
Pyrolistical 10.08.2009 23:51
quelle