DEC 5.2 String hashen?

[Michael II]

Zitat:

Heißt also je genauer, desto weniger Kollisionen UND desto eher ändert sich der Hash bei Änderungen des Inputs?

Beispiel: 1Bit Hash
Wenn deine Wertemenge 2 Elemente enthält, dann werden alle Elemente deiner Definitionsmenge auf 0 oder 1 abgebildet. Du kannst also deine Definitionsmenge in "zwei Pakete" unterteilen. Wie du die Unterteilung (d.h. deine Hash Funktion) definierst ist abgängig davon, was deine Hash Funktion tun soll.

Beispiel: Wenn h alle Zeichenketten mit dem Wort Delphi erkennen soll, dann reicht eine 1Bit Funktion vollauf. Jeder Zeichenkette, welche Delphi enthält ordnet h die 1 zu, jeder anderen Kette 0 (oder umgekehrt).
Wenn wir davon ausgehen, dass du deiner Funktion h alle Texte dieser Welt füttern willst, dann enthalten die meisten Texte das Wort Delphi nicht. Deine Funktion ist aber für deinen Zweck absolut genau: Du erkennst alle Texte mit dem Wort Delphi.
Du nimmst ohne Einschränkung in Kauf, dass viel mehr Elemente auf 0 als auf die 1 abgebildet werden. D.h. du hast, wenn du zwei zufällige Texte nimmst mit sehr grosser Wahrscheinlichkeit (ungefähr 1) eine Kollision zu erwarten.

Bei anderen Aufgaben bist du eher daran interessiert, die Kollisionswahrscheinlichkeit zu minimieren. (Sortieren, Komprimieren)


Grössere Wertemenge
Wenn du die Wertemenge grösser wählst, dann kannst du natürlich die Definitionsmenge in mehr Pakete unterteilen.

Beispiel:
Eine Hash Funktion h mit einer Wertemenge mit n Elementen erlaubt es dir, deine Definitionsmenge in n Pakte zu untereilen. Je grösser du deine Wertemenge wählst, desto mehr Pakete schnürst du.

Beispiel:
In 32Bits kannst du 2^32 Werte speichern und damit deine Definitionsmenge in 2^32 Pakete unterteilen.


Deine Hash Funktion soll deiner EXE einen Wert zuordnen.

Du musst also eine Hash Funktion wählen
- mit möglichst grosser Wertemenge
- (dieser Teil ist schwierig, wenn du's selbst tun willst), welche EXEs mit ähnlicher Zeichenkette (du bist ja interessiert an Änderungen deines Programms) auf voneinander verschiedene Werte abbildet. [Es kann dir egal sein, ob Word und dein Programm durch h im gleichen Topf landen.]

Es ist eine Riesenaufgabe, solche Hash Funktionen zu definieren. Nimm besser eine erprobte mit grosser Wertemenge.