32 Bit Hash



  • Guten Abend,

    Also gleich ins Thema. Ich hab hier mein Buch das mir Hashwerte wunderschön in allen Details beschreibt. Soweit alles kein Problem, aber es gibt auch einen Hinweis, dass ein 32 Bit Hash nicht immer reichen würde, z.B. zwei unterschiedlich Strings würden den gleichen Hashwert erzeugen.

    Also ich fantasiere jetzt einfach mal ein bisschen: Mal angenommen, mir würden die 4,3 Millionen Möglichkeiten (die ja mit 32 Bit gegeben sind) nicht reichen (weil ich nen Superserver hab, bei dem selbst 5 Millionen Dateien ein Witz sind), dann müsste ich ja selber das Programmieren anfangen (ist ja auch ne gute Idee 🙂 ). Gibt es dafür schon Projekte die sich diesem "Problem" annehmen? Welche Daten zieht man für einen Hashwert heran, und wie verarbeitet man diese zu einem Hashwert?

    Gruß

    Markus Seidl



  • Das Problem ist meistens nicht, dass die Anzahl möglicher Hashwerte nicht ausreichen, sondern dass Hashwerte kollidieren, d.h. verschiedene Objekte liefern den selben Hashcode. Dies ist normal kein übermäßig großes Problem für die normale Anwendung wie Hashtabellen, man muss nur damit rechnen, dass es passiert.
    Ein Problem wird es allerdings bei Hashfunktionen, die man kryptographisch nutzen will. Für den allseits beliebten MD5 Hash ist es beispielsweise schon gelungen, auf performante Weise viele Eingabewörter zu einem Hashcode zu finden, wenn bereits ein Eingabewort bekannt ist. Kollisionen sind dort ein Sicherheitsrisiko, deshalb gibt es ja jetzt zum Glück SHA.

    Diese Funktionen verwenden eben auch deshalb mehr als 32 Bit, weil Kollisionen damit unwahrscheinlicher werden. Mach dir mal bewusst, wie dein Login beim Betriebssystem gespeichert wird. Was du als Passwort eingibst, wird verschlüsselt und es wird geprüft, ob es mit dem verschlüsselt abgelegten richtigen Passwort übereinstimmt. Wenn dein Passwort "foo" ist und den Hashwert 1234 hat und ich "bar" eingebe und den selben Hashwert damit bekomme (was bei 4 Bits nicht so unwahrscheinlich ist), hast du ein Problem.

    Aber wenn du jetzt nicht gerade kryptographische Anwendungsgebiete hast, dann sollten bei einer guten Hashfunktion 32 Bit Hashs reichen. Wenn deine Hashfunktion schlecht ist, kannst du die Werte mit einer zweiten Hashfunktion weiter verstreuen. Bei mir hat sich folgende Funktion recht bewährt, die man für die Implementierung des Java-API über eine automatische Suche ermittelt hat:

    private long hash(long value)
    		{	
    		value += ~(value << 9);		
    	value ^=  (value >> 14);		
    	value +=  (value << 4);		
    	value ^=  (value >> 10);	
    		return value;	
    	}
    

    (OMG, §%§" Unicode line separators)

    Welche Daten zieht man für einen Hashwert heran, und wie verarbeitet man diese zu einem Hashwert?

    Die Daten, anhand deren du sagen willst, ob ein Objekt gleich oder ungleich ist. Man verarbeitet sie möglichst so, dass die Werte gut verstreut werden. Siehe dazu auch Streuung, Standardabweichung als Suchbegriffe. 🙂



  • Ich kenne mich grundsätzlich mit dem Thema aus (FI-SI), aber das mit der Streuung wusste ich jetzt noch nicht. Ein Datei Server mit 5 Millionen Dateien, selbst da würde natürlich das 32 Bit Wort reichen. Weil ich ja die Dateien nicht mit seinem Hash Identifiziere, sondern nur prüfen würde, ob sich seit dem Letzten durchlauf an der Datei was geändert hat.

    Aber Hey ich merci dir voll fett für Antwort 🙂

    Gruß

    Markus Seidl


Log in to reply