OK, nur 64-Bit-sha1-Hash als ID zu verwenden?

Question

1) Kann ich für den Zweck einer wirklich niedrigen Hash-Kollision mit nur der Hälfte der 128 Bits eines sha1 davonkommen, anstatt sich mit dem sha1 selbst zu beschäftigen? Ich verstehe, dass dies nicht für kryptographische Hashes geeignet ist, aber ich brauche nur die Hashes für Hash-Tabellenschlüssel.

2) Rechenzeit ist keine Priorität, und außerdem hashing ich sehr kleine Daten. Insbesondere werde ich hauptsächlich 2 oder 3 64-Bit-Hashes nehmen und sie hashen, um einen weiteren 64-Bit-Hash zu bekommen. Gibt es zu diesem Zweck eine bessere Option als sha1? Auch hier sollten Kollisionen sehr unwahrscheinlich sein.

3) Ich bin ein sql newb. Ist es eine gute Idee, 64-Bit-Hashes als IDs in SQL zu verwenden? Werden 64-Bit-IDs Leistungsprobleme in SQLite oder Postgres verursachen? Ich werde Daten über mehrere Datenbanken hinweg koordinieren müssen (einschließlich eines Lucene-Indexes), also dachte ich, ich sollte Hashes direkt in den Tabellen behandeln, anstatt sich mit automatisch inkrementierten IDs zu beschäftigen (was nur in einer db sinnvoll wäre) über alle Datenspeicher hinweg). Ich denke, 64-Bit ist ein guter Kompromiss: groß genug für unwahrscheinliche Kollisionen, spart aber Platz (und Nachschlagezeit?).

4) Was ist mit CRC-64? Produziert das eine zufällig genug Verteilung?

Answer 1

Wenn Sie genug Aufzeichnungen haben, ist es fast sicher, dass Sie nie eine Hash-Kollision in 64 Bits haben werden. Wahrscheinlich wirst du in diese Kategorie fallen.

Es sollte kein Problem mit einer kryptografischen Hash wie SHA1 Verschlankung, denn wenn es in der Hash-interne Struktur ist dann wäre es nicht gut genug sein, einen Krypto-Hash zu sein, und wenn es keine Struktur dann irgend Teilmenge der Bits sollte ziemlich zufällig sein. Beachten Sie, dass ich nur davon spreche, das für IDs zu verwenden, nicht für irgendwelche Kryptozwecke!

Aber wirklich, hat Ihr SQL keine Art von GUID? Und wenn ja, warum nicht?

Answer 2

Wenn die Rechenzeit nicht wichtig ist, warum nicht die ganzen 128 Bits gehen? Gibt es einen wirklichen Grund, 64 Bits neben möglichen Speicherproblemen zu wählen? (und dann eine zusätzliche 8 Bytes wird dich nicht mit Speicher so billig töten)

64 Bits vs 128 Bits werden keine Geschwindigkeitsprobleme in SQLite verursachen, ich bin nicht sicher über mySQL.

Answer 3

Für einen guten Vergleich der Längen von Hashes, ein auch bei http://en.wikipedia.org/wiki/List_of_hash_functions

schauen durch haben, nur eine Anmerkung: SHA-1 ist 160 Bit, nicht 128

Answer 4

Ihre Schlüssel Einzigartigkeit absolute brauchen nicht hohe Wahrscheinlichkeit der Einzigartigkeit. Ich würde vorschlagen, GUIDs anstelle von Hashes für Ihre Schlüssel für die datenbankübergreifende Kompatibilität zu verwenden. Generieren Sie den Hash als einen schnellen Suchmechanismus - Sie können einen nicht eindeutigen Index dafür haben - aber im Falle einer Kollision müssen Sie die tatsächlichen Daten vergleichen, um sicherzustellen, dass sie identisch sind. Wenn Sie Ihre Datenbanken synchronisieren, können Sie den Hash-Wert überprüfen (indem Sie schnell den Index verwenden). Wenn Sie eine Kollision finden, müssen Sie dann feststellen, ob die Daten identisch sind und die GUIDs aufgelöst werden müssen. Wenn keine Kollision vorliegt, aktualisieren Sie einfach die Datenbank, die den fehlenden Eintrag benötigt, und fügen sie mit der GUID aus der anderen Datenbank ein.

Auch ich sehe wenig Sinn darin, ein eigenes Hash von Hashes zu erstellen, um Platz zu sparen. Wenn Sie bereits andere Hashes haben, verwenden Sie sie einfach (append, nicht erneut aufrüsten). Wenn nicht, verwenden Sie einfach eine Standard-Hash-Funktion wie MD5 oder SHA1 und speichern Sie die resultierenden Daten.

Answer 5

Bei 64-Bit-Hashes besteht eine Wahrscheinlichkeit von 1% für eine Kollision mit 6.1 × 10 Aufzeichnungen. (Für andere Kombinationen, siehe Wikipedia page on the Birthday problem.) Sie können die ersten 64 Bits oder das letzte jedes zweiten Bits wegwerfen, es macht keinen Unterschied zu den Eigenschaften des Hash.