Wie zufällige Hashes erzeugen?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Freitag 2. November 2007, 15:08

Gerold: Ja, UUIDs werden offenbar genau so hergestellt, wie ich mir das wünsche. Allerdings sind sie einfach zu lang. Sobald ich zwei oder drei davon kombiniere (angenommen, man will sie in einem Forum verwenden, das IDs für Kategorien, Themen und Beiträge verwendet), habe ich schon eine URL, die zweimal um die nördliche Hemisphäre reicht. Ohne RFCs bzgl. der zulässigen Maximallänge zu konsultieren, gefällt mir das verständlicherweise schon nicht.

Für komplett interne Bezeichner würde der Ansatz ansonsten in Frage kommen. Ich möchte diese Dinger aber eben gerne u.a. in URLs und als Dateinamen verwenden. Für letztere fällt auch die Unterscheidung von Groß-/Kleinbuchstaben weg, wenn man nicht möchte, dass einem der unter Unix entwickelte Kram unter Windows um die Ohren fliegt.

An Plattformen (win32) oder DMBS (PostgreSQL) möchte ich mich ungern binden, aber danke für die Hinweise - vielleicht sind sie mir ein andermal von Nutzen.
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Montag 12. November 2007, 14:18

Y0Gi hat geschrieben:Wenn ich den Timestamp verwende, so dachte ich, erhalte ich bei theoretisch möglichen mehreren parallelen Zugriffen ja identische Hashes (da ich ja sonst keinen Wert habe, den ich in den Hash mit einbeziehen kann). Jedoch habe ich außer acht gelassen, dass `time.time()` eine Fließkommazahl liefert, bei der Kollisionen durch parallele Aufrufe (die entsprechend so einen eindeutigen Hash erfordern) in einer Webanwendung praktisch fast auszuschließen sind.
Ein Blick in die Doku hat mich wieder an folgendes erinnert:
Note that even though the time is always returned as a floating point number, not all systems provide time with a better precision than 1 second.
Schade :/


Ich habe mich jetzt für ``uuid.uuid4().hex[:12]`` entschieden. Auf diesem Weg wird in einer Funktion, die als `default`-Argument über die Spaltendefinition in SA oder Elixir übergeben wird, ein Wert generiert und auf dessen Existenz in der Datenbank geprüft (bis zu X mal, damit im Falle eines Fehlers nicht die Applikation hängt).
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Donnerstag 22. November 2007, 16:03

Warum nicht einfach einen SHA Digest nehmen und dann auf Buchstaben von a-zA-Z0-9 umrechnen?
TUFKAB – the user formerly known as blackbird
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Donnerstag 22. November 2007, 17:06

Solange der Digest einigermaßen zufällig ist, ginge das, klar.

Von Großbuchstaben, falls ich das noch nicht erwähnt habe (edit: doch, habe ich schon), halte ich übrigens nicht so viel, weil die bei Verwendung in Dateinamen problematisch sind, da z.B. Windows Groß-/Kleinschreibung dabei ignoriert.
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Donnerstag 22. November 2007, 17:09

Code: Alles auswählen

try:
    from haslib import md5
except ImportError:
    from md5 import new as md5
from time import time
from random import random

base16 = '0123456789abcdef'
base62 = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'

def get_id():
    result = []
    x = reduce(lambda a, b: a * 16 + base16.index(b),
               md5('%s|%s' % (random(), time())).hexdigest(), 0)
    while x:
        result.append(base61[x % 62])
        x //= 62
    return ''.join(result)
Damit sind die Hashes nicht mehr so lange. Man könnte natürlich auch noch mehr Zeichen einbauen, aber ich finde die sind schon ziemlich kurz. Wie viele Kollisionen du rausbekommst musst du testen.
TUFKAB – the user formerly known as blackbird
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Donnerstag 22. November 2007, 18:34

Auf Kollisionen (mit vorhandenen Identifiern) muss ich ohnehin testen.

Meine o.g. Lösung ist *etwas*... kompakter als deine. Nimm's mir bitte nicht übel, wenn ich dabei bleibe ;)

Dein Beispiel ist dennoch hilfreich, wenn man einen bestimmten, evtl. eingeschränkten Zeichensatz benutzen möchte, danke.


Um zum Prüfen auf Kollisionen zurück zu kommen: Ich kann zwar eine Datenbank nach einem bestimmten Wert fragen und ihn, wenn dieser darin noch nicht vorhanden ist, einfügen. Allerdings ist nicht sichergestellt, dass nicht in der Zwischenzeit ein anderer Thread der Anwendung *(sehr, sehr) zufällig* auch diesen Wert erzeugt, abgefragt und eingefügt hat.

Wie lässt sich das verhindern? Ist ein `Lock`-Objekt eine gute Lösung (z.B. auch für das Erzeugen/ungestörte Einlesen/whatever von Dateien)? Würde es im Zusammenhang mit einer Datenbank evtl. zuviel Wartezeit verursachen und den Rest der Applikation ausbremsen?
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Donnerstag 22. November 2007, 23:52

Transaktionen nehmen und einen UNIQUE index auf das Feld.
TUFKAB – the user formerly known as blackbird
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Freitag 23. November 2007, 11:54

Urgs, Transaktionen, klar, danke.

Unique benutze ich natürlich schon. Hierzu wüsste ich bei der Gelegenheit jedoch gerne mal, wie man Datenbank-Exceptions z.B. durch Contraint-Überschreitungen sauber abfangen kann. Soweit ich weiß werfen die alle einen recht allgemeinen (SQLAlchemy-)Fehler, auf den sich schlecht reagieren lässt (und die Einbeziehung der Fehlermeldungen selbst ist mir zu riskant angesichts von Versionsänderungen).
Antworten