Hashen in Java

Auf dieser Seite wird das Hashen in Java genauer behandelt.

In Java gibt es viele vordefinierte Klassen und Methoden zur Unterstützung von Hashing. Es gibt eine vordefinierte Hashfunktion für beliebige Objekte und verschiedene hashbasierte Datenstrukturen wie Maps und Sets. Es ist aber auch möglich eine eigene Implementierung eines Hashverfahrens durchzuführen. Dafür wird die Datenstruktur definiert die Hashfunktion geschieht durch eine Indexberechnung und es muss eine Kollisionsbehandlung festgelegt werden.

Eine vordefinierte Methode zur Berechnung eines Hashwertes ist int java.lang.Object.hashCode(). Diese kann überschrieben werden. Bei jedem Aufruf hat die Methode den gleichen Wert und gleiche Objekte liefert gleiche Hashwerte. Vergleiche finden mit der Equals Methode statt.

Die Default Implementierung in Java erfolgt durch die Speicheradresse des Objekts. Für einen java.lang.String lautet diese: $h(s)=s[0]\cdot 31^{(n-1)}+s[1]\cdot 31^{(n-2)}+...+s[n-1]$

Eine Hashtabelle <K,V> ist eine Array basierte Implementierung einer Hashtabelle mit verketteter Liste als Kollisionsbehandlung ( kein Sondieren in irgendeiner Javaklasse), Rehashing und Steuerung der Tabellengröße und maximalen loadFactor, welcher bis 0.75 effizient ist.

Eine HashMap <K,V> ist ähnlich einer Hashtabelle, erlaubt aber zusätzlich null als Schlüssel.

Eine LinkedHashMap <K,V> verwaltet zusätzlich eine doppelte verkettete Liste zum Erhalten der Einfügereihenfolge.

Das HashSet<E> ist eine HashMap basierte Implementierung einer Menge mit dem Aufwand O(1) für ein Lookup.

Das LinkedHashSet<E> ist eine LinkedHashMap basierte Implementierung einer Menge.

Die IdentityHashMap<K,V> ist eine Hash Tabelle unter Verwendung der Gleichheit der Objektreferenz statt der Gleichheit der Objektwerte. Die WeakHashMap<K,V> ist eine Hash Tabelle, aus der als Referenz gelöschte Elemente automatisch gelöscht werden.

Schnittstellen

interface Hashing {
   void add(Object o)
     throws HashTableOverflowException;
   boolean contains (Object o);
}

Das Einfügen des Objekt erfolgt mit add. Der Test auf Erhalten sein (Auslesen) erfolgt mit contains. Die Hashfunktion erfolgt mit Object.hashCode().

Implementierung Hashtabelle

 public class LinkedHashTable
     implements Hashing {
   LinkedList [] table; // Feld mit Listen
   public LinkedHashTable (int size) { // Feld aufbauen
     table= new LinkedList [size];
   }
public void add (Object o) { // Feldindex über Hashwert bestimmen
    int idx = (o.hashCode() & 0x7fffffff) %
       table.length;
    if (table [idx] == null) // noch keine Liste vorhanden
       table [idx] = new LinkedList(); // an Liste anhängen
    table [idx].addLast(o);
}
public boolean contains (Object o) { //Feldindex über Hashwert bestimmen
   int idx=(o.hashCode() & 0x7fffffff) %
      table.length;
   if (table [idx]!=null)} //Liste gefunden
      Iterator it= table[idx].iterator();
      while (it.hasNext()){ //sequenzielle Suche nach Element
          Object obj=it.next();
          if (obj.equals(o)) return true;
      }
   }
   return false;
}

Variante mit Sondieren

 public class HashTable implements Hashing {
     Object [] table;

     public HashTable (int size) {
         table=new Object [size];
     }
    public void add (Object o)
         throws HashTableOverflowException {
         int idx, oidx;

         oidx=idx= (o.hashCode() & 0x7fffffff) %
             table.length;
         while (table[idx] != null) {
             idx= ++idx % table.length;
             if (idx==oidx)
                throw nes HashTableOverflowException();
        }
        table [idx] =o;
}
public boolean contains (Object o) {
     int idx, oidx;

     oidx=idx= (o.hashCode() & 0x7fffffff) %
        table.length;
     while (table[idx] != null) {
        if (o.equals(table[idx]))
            return true;
        idx = ++idx % table.length;
        if (idx==oidx)
            break;
     }
     return false;
}