Hash für 128-Bit-Daten

knivil

Oh, schon werden die Verben weggelassen. Gleich sind es die Substantive.

volkard

fgdfdfs schrieb:

OK, ich will 2^128 Bit -> ~32 Bit hashen.

Ich zweifle ein wenig. 2^128 Bit sind ca 2^116 Festplatten und die wiegen ca 2^113 Tonnen, was ungefähr 5000 Sonnenmassen entspricht.

dot schrieb:

128 Bit in 32 Bit hashen? Na zerteil das Ding in 32bit Blöcke, XOR die zusammen und fertig. Wenn du eine hilfreichere Antwort haben willst, musst du eine sinnvollere Frage stellen.

Dann lies doch: Es soll kollisionssischer und schnell geschehen.

dot

Kollisionssicher geht aber nicht wenn die Definitionsmenge mächtiger ist als die Zielmenge...

Kollisionssicher, nicht -frei.

dot

Ich dachte eigentlich es soll kein kryptographischer Hash sein?

Aber naja, volkard hat ja schon eine Tabelle bekannter Hashfunktionen gepostet. Da sind einige dabei die 32 Bit Hashes erzeugen, also such dir eine aus...

volkard

fgdfdfs schrieb:

Quatsch, 128 Bit -> ca. 32 Bit

Na, dan haben wir's ja. Dann paßt auch die verlinkte Seite.

Die gute Wahl der Hashfunktion ist eine Kunst für sich. Ohne nähere Kenntniss der Datenlage würde ich bei sowas wie CRC32 anfangen und richtung schlichtem XOR oder gar nur Nehmen der hinteren Bits gehen, wenn es die Kollissionen nicht stark vermehrt.

volkard

dasdsf schrieb:

Kollisionssicher, nicht -frei.

Du drückst dich aber auch merkwürdig aus.

template <typename T>
uint32_t hash_data(const T& data)
{ //kollisionssicher
  return 4711;
}

Allesquatsch

fgdfdfs schrieb:

fgdfdfs schrieb:

Es geht mir nicht um kryptographische
Sicherheit, nur für eine Hashtable.

Aber es geht mir um Schnelligkeit
und Kollisionssicherheit.

Verstehe ich Dich richtig, dass Du eine große Hashtabelle realisieren willst, um die Lauf-/Zugriffszeiten noch unter den Erwartungswert zu drücken, den Du mit Suche in einem Baum hättest?

Dein Suchkriterium ist 128 bit lang und Du hast einen 1GB großen
Speicherbereich zur Verfügung? (Dann fehlt noch die Anzahl bzw. die Größe der
einzelnen Zellen, falls Du mehr als die Keys ablegen musst.)

Außer der Hashfunktion musst Du Dir noch die Kollisionsstrategie(Hash-Algorithmus) überlegen, die ja ggf. die Zugriffszeiten im Schnitt und im Maximum verändert. Relevant, auf welche Parameter/Fälle es Dir ankommt.

Bei zuvor bekannten, statischen Werten kannst Du außerdem anders vorgehen als
bei dynamischen Werten oder wenn Du Änderungen zulassen musst. Mit bekannten, statischen Werten kannst Du ja mit Tabellengröße, Hashfunktion und Kollisionsstrategie etwas spielen und dann die Beste auswählen. Hängt aber von den Dimensionen ab, ob so viel Hirnschmalz für die Optimierung lohnt.

Ich würde ruhig eine schnelle, krypotologische Hashfunktion wählen, weil Du eine gute Streuung hast. Ungünstige Kombinationen von Hashfunktion und Rohdaten können nämlich katastrophale Laufzeiten bringen (z.B. die XOR-Idee).

Vielleicht gibt es eine solche Funktion ohnehin schon in einer Library. Auf die gewünschte Anzahl kannst Du das ja durch einen linearen Faktor bringen.

Geht es um eine Hashtabelle?

Ciao, Allesquatsch

Wie gut ist die Hash-Funktion x % (previousPrime(2^30)) ?

SeppJ

hmmmmmm schrieb:

Wie gut ist die Hash-Funktion x % (previousPrime(2^30)) ?

38.41

hustbaer

SeppJ schrieb:

hmmmmmm schrieb:

Wie gut ist die Hash-Funktion x % (previousPrime(2^30)) ?

38.41

Optimistisch geschätzt.

rapso

volkard schrieb:

dasdsf schrieb:

Kollisionssicher, nicht -frei.

Du drückst dich aber auch merkwürdig aus.
template <typename T>
uint32_t hash_data(const T& data)
{ //kollisionssicher
  return 4711;
}

wegen dir hab ich hier in der arbeit traenen gelacht als es oben ankam, you made my day

ich denke, falls die source menge gleichmaessig in 128bit verteilt ist, wird dir

cooky451 schrieb:

Hier:
template <typename T>
T hash_data(const T& data)
{
  return data;
}
Sehr schnell und 100% kollisionssicher.

mindestens so gute resultate liefern, wie die sonstigen hashes.

falls du z.b. von 0 bis 2^128 hochzaehlen wuerdest, werden die allermeisten hash algirthmen vorher eine kollision haben.

hashes bringen etwas fuer faelle von ungleich verteilten daten, falls deine 128bit schon zufalls daten sind (z.B. ein MD5 resultat), wird ein zweites hashing nicht mehr wirklich was bringen.

falls du also etwas besseres haben moechtest als von cooky vorgeschlagen, solltest du uns etwas ueber die quelldaten sagen.