none
Ideale Hashfunktion RRS feed

  • Frage

  • Hallo,

    ich arbeite gerade an einer Datenbank die zahlreiche Werte speichern muss. Als Schlüssel ein Hash-Wert, der aus dem Key gewonnen wird, dienen. 

    Gibt es eine Hashfunktion die einen Hash aus einem String generiert, der gleichzeitig alle Werte [0; 2³²] (int -> 4 Byte) abbildfet, und wo die Werete gleich verteilt werden.

    Von der Idee her soll das etwas wie eine Verteilte Hashtable sein, blos, dass diese Am Anfang erstmal nicht verteilt wird, sondern auf einem Rechner läuft.

    Welche Hashfunktion würdest ihr mir da raten?


    © 2015 Thomas Roskop


    • Bearbeitet Thomas Roskop Freitag, 19. Dezember 2014 13:11 Titel verbessert
    Freitag, 19. Dezember 2014 13:11

Antworten

  • Hallo,
    ich vermute mal, das dein String deutlich länger als 4 Byte (2 Zeichen unter .NET) sein kann. In dem Fall müsstest du eine Möglichkeit finden aus den n Bytes des Strings 4 zusammen eindeutige Bytes zu machen. Das geht nicht. Hashfunktionen sind zwar darauf ausgelegt möglichst eindeutig und nicht wiederkehrend zu sein, ein Beweis für Eindeutigkeit kann dadurch aber nicht erbracht werden.

    Noch komplizierter würde es werden, wenn du aus den 4 Bytes wieder den String machen müsstest. Das ginge gleich gar nicht, da es der Dekomprimierung eines komprimierten Strings in sehr hohem Maße entsprechen würde.

    Ich kenne dein genaues Vorhaben nicht, aber wäre es denn nicht möglich einfach eine fortlaufende Zahl als Primary Key zu nehmen und den String in einer 2. Spalte zu speichern?

    Wenn du anhand des Hashs die Datensätze identifizieren willst, hätte ich aber auch noch einen anderen Ansatz:
    Suche dir eine Hashfunktion die an sich möglichst eindeutige Werte liefert. Im einfachsten Fall GetHashCode von .NET. Diesen Hash fügst zusammen mit einer fortlaufenden Nummer und dem String in die DB ein.
    Wenn du nun nach einem Datensatz anhand des Strings suchen willst, brauchst du nur den Hash zu berechnen und zunächst die Datensätze danach zu filtern. Die verbleibenden Datensätze vergleichst du nun noch mit dem richtigen String. So sollte die Abfrage schneller als bei String-Vergleichen gehen und zu gleich absolute Sicherheit bieten.
    Was eine Volltextindizierung bringen würde kann ich leider nicht beurteilen.


    Tom Lambert - C# MVP
    Wozu Antworten markieren und für Beiträge abstimmen? Klicke hier.
    Nützliche Links: .NET Quellcode | C# ↔ VB.NET Konverter | Account bestätigen (Verify Your Account)
    Ich: Webseite | Code Beispiele | Facebook | Twitter | Snippets

    • Als Antwort markiert Thomas Roskop Dienstag, 6. Januar 2015 15:51
    Freitag, 19. Dezember 2014 13:27
    Moderator
  • Hallo,

    danke für die Antworten. Ich habe mich dann doch umentschieden, siehe diesen Thread: https://social.msdn.microsoft.com/Forums/de-DE/7ac4f962-0e30-464a-9540-5a10f42d7394/userid-durchnummerieren?forum=securityde

    Danke.


    © 2015 Thomas Roskop

    • Als Antwort markiert Thomas Roskop Dienstag, 6. Januar 2015 15:52
    Dienstag, 6. Januar 2015 15:51

Alle Antworten

  • Hallo,
    ich vermute mal, das dein String deutlich länger als 4 Byte (2 Zeichen unter .NET) sein kann. In dem Fall müsstest du eine Möglichkeit finden aus den n Bytes des Strings 4 zusammen eindeutige Bytes zu machen. Das geht nicht. Hashfunktionen sind zwar darauf ausgelegt möglichst eindeutig und nicht wiederkehrend zu sein, ein Beweis für Eindeutigkeit kann dadurch aber nicht erbracht werden.

    Noch komplizierter würde es werden, wenn du aus den 4 Bytes wieder den String machen müsstest. Das ginge gleich gar nicht, da es der Dekomprimierung eines komprimierten Strings in sehr hohem Maße entsprechen würde.

    Ich kenne dein genaues Vorhaben nicht, aber wäre es denn nicht möglich einfach eine fortlaufende Zahl als Primary Key zu nehmen und den String in einer 2. Spalte zu speichern?

    Wenn du anhand des Hashs die Datensätze identifizieren willst, hätte ich aber auch noch einen anderen Ansatz:
    Suche dir eine Hashfunktion die an sich möglichst eindeutige Werte liefert. Im einfachsten Fall GetHashCode von .NET. Diesen Hash fügst zusammen mit einer fortlaufenden Nummer und dem String in die DB ein.
    Wenn du nun nach einem Datensatz anhand des Strings suchen willst, brauchst du nur den Hash zu berechnen und zunächst die Datensätze danach zu filtern. Die verbleibenden Datensätze vergleichst du nun noch mit dem richtigen String. So sollte die Abfrage schneller als bei String-Vergleichen gehen und zu gleich absolute Sicherheit bieten.
    Was eine Volltextindizierung bringen würde kann ich leider nicht beurteilen.


    Tom Lambert - C# MVP
    Wozu Antworten markieren und für Beiträge abstimmen? Klicke hier.
    Nützliche Links: .NET Quellcode | C# ↔ VB.NET Konverter | Account bestätigen (Verify Your Account)
    Ich: Webseite | Code Beispiele | Facebook | Twitter | Snippets

    • Als Antwort markiert Thomas Roskop Dienstag, 6. Januar 2015 15:51
    Freitag, 19. Dezember 2014 13:27
    Moderator
  • Also ich will eigentlich soetwas wie folgendes:

    f("Max Mustermann") = 0xF4 F8 97 41

    Mit diesem Hash kann dann das System nach den Richtigen Cluster suchen (hirachisch):

    C1: F4

       -> C2: F8

            -> C3: 97

                  -> C4: 41 -> Ergebnis!!

    Ein Kollisionssystem hätte ich auch bereits. Und ferner ist mir auch bewusst, dass solch ein System schaon nur duch die Cluster mehr 16 GB verbraucht, aber es scheint die richtige Lösung zu sein.


    © 2015 Thomas Roskop

    Freitag, 19. Dezember 2014 13:33
  • Hallo Thomas,

    Bist Du mit der Hash-Funktion weitergekommen? Hast Du dir eine Hash-Funktion ausgesucht?

    Gruß,
    Dimitar


    Bitte haben Sie Verständnis dafür, dass im Rahmen dieses Forums, welches auf dem Community-Prinzip „IT-Pros helfen IT-Pros“ beruht, kein technischer Support geleistet werden kann oder sonst welche garantierten Maßnahmen seitens Microsoft zugesichert werden können.

    Dienstag, 6. Januar 2015 15:26
    Moderator
  • Hallo,

    danke für die Antworten. Ich habe mich dann doch umentschieden, siehe diesen Thread: https://social.msdn.microsoft.com/Forums/de-DE/7ac4f962-0e30-464a-9540-5a10f42d7394/userid-durchnummerieren?forum=securityde

    Danke.


    © 2015 Thomas Roskop

    • Als Antwort markiert Thomas Roskop Dienstag, 6. Januar 2015 15:52
    Dienstag, 6. Januar 2015 15:51