30.2 Hashfunktion
 
  Wir suchen nach einer Funktion, die ein Wort in einen Index transformiert. Bei dieser Transformation wollen wir berücksichtigen, dass es sehr viele Wörter gibt, wir aber nur ein Teil der möglichen Wörter in unsere Tabelle eintragen wollen. Wir brauchen also nicht so viele Indexwerte, wie es Wörter gibt. Zudem sollen die Einträge möglichst gleichmäßig über die Tabelle verteilt werden. 
 

Index
Wort
Schlüssel
Übersetzung
Schlüsselwert
0    
1    
2 Warteschlange queue
3    
4    
5    
6    
7 Keller stack
8    
9    
   
Hashfunktion Um zu lernen, wie eine Hashfunktion arbeitet, vereinfachen wir unser Beispiel noch um einen weiteren Schritt. Wir tragen als Schlüssel kein Wort sondern einen Buchstaben ein. Zusätzlich beschränken wir unsere Tabelle auf 11 Plätze. Eine Funktion die die Anforderungen einer Hashfunktion erfüllt, ist:

H(ki) = ASCII(ki) mod N

Dabei ist ki der Schlüssel z.B. Z . ASCII(ki) ist der ASCII-Kode des Schlüssels ki. Für Z ergibt sich ASCII(Z) = 90. Bleibt noch zu klären, was N bedeutet. Wenn die Tabelle 10 Einträge (0,..,9) hat wähle man für N den Wert der kleinsten Primzahl, die größer ist als N; in unserem Fall also 11. Für das Zeichen Z erhalten wir also

H(Z) = ASCII(Z) mod 11 = 90 mod 11 = 2

Lassen wir die Beschränkung, dass der Schlüssel aus einem Zeichen besteht, wieder fallen, müssen wir die Hashfunktion etwas erweitern. In einer Schleife, die nach und nach jeden Buchstaben des Schlüssels abarbeitet wird die Hashfunktion iterativ bestimmt:

H(Wortn) = (256 * H(Wortn-1) + ASCII(Zeichenn)) mod N

 

Download:
Hashen.java
Wir implementieren die Methode createHashCode(String wort) mit der Primzahl N = 113, also für eine Tabelle mit 112 Plätzen.
import info1.*;
public class Hashen {

  public static void main (String[] args) {
     int hashCode = 0;
     System.out.print("Geben Sie ein Wort ein: ");
     String wort = Console.in.readWord();
     hashCode = createHashCode(wort);
     System.out.println("HashKode("+wort+") = "+hashCode);
  }
  
  public static int createHashCode(String wort){
     char zeichen;
     int hashCode = 0;
     for (int i = 0; i<wort.length();i++){
       zeichen = wort.charAt(i);
       hashCode = (256 * hashCode + (int)zeichen)%113;
     }
     return hashCode;
  }
}
Beispiele für HashKodes HashKode(michael) = 22
HashKode(joachim) = 26
HashKode(dorothea) = 89
HashKode(heinz) = 4
HashKode(ludwig) = 80

 
Hashfunktion nicht injektiv Spätestens nach der Eingabe von mehr als 112 verschiedenen Wörtern müssen sich Hashkodes wiederholen. Unterschiedliche Wörter können also gleiche Hashkodes haben.  Mathematiker sagen dann, dass die Haschfunktion nicht injektiv ist. Injektive Funktionen sind nämlich Funktionen, die unterschiedlichen Werten garantiert unterschiedliche Bildwerte zuordnet. Unsere Hashfunktion ordnet aber den Wörtern 'ludwig' und 'paris' den gleichen Haschkode '80' zu:

HashKode(paris) = 80

Wir haben also ein Problem. Die Lösung zeigt die (erweiterte) Hastabelle.
 

zu 30.3 Hashtabelle
zur Startseite www.pohlig.de  (C) MPohlig 2004