Einführung Algorithmen und Datenstrukturen

exemplarische Lösung der Aufgaben SS 03 von Markus Durzinsky. Zurück zur Algodat Hauptseite.

13. Übungsblatt

Aufgabe 61 - Prioritätsschlangen

not yet.

Aufgabe 62 - Hashtable - ein Beispiel

  1. Ich denke es ist nicht schwer auf folgende Belegung der Hashtabelle zu kommen:

    
     0:  .
     1:  Saake  .
     2:  Tamassia  .
     3:  .
     4:  Goodrich  .
     5:  Toennies  .
     6:  .
     7:  Engelke  .
     8:  Schallehn  Schulz  .
     9:  .
    10:  Bluemel  .
  2. Warum eine Hashtabelle entwerfen, die nur speziell für eine Datenstruktur (String, hash = 3. Buchstabe) geeignet ist? Im Prinzip kann jede Hashtabelle verwendet werden, es mus nur die Methode hashCode() der übergebenen Objekte angepasst werden. Wie dass aussieht steht in der nächsten Aufgabe.

Aufgabe 63 - Hashtable in Java

  1. Nun muss eine Klasse her (LinkedHashTable ist doch bestimmt eine sinnvollere Bezeichnung als immer dieses MyXXX).

    
      package algodat;
    
      import java.util.Iterator;
      import java.util.ListIterator;
      import java.util.LinkedList;
    
      public class LinkedHashTable {
    
        protected LinkedList[] table;
        protected int modulo;
    
        public LinkedHashTable(int mod) {
          this.modulo = (mod <= 0 ? 101 : mod);
          table = new LinkedList[modulo];
          for (int i = 0;  i < modulo;  i++) {
            table[i] = null;
          }
        }
    
        public LinkedHashTable() {
          this(101);
        }
    
        public int getModulo() {
          return modulo;
        }
    
        ...
      }

    Beim Einfügen von Objekten, liefert die hashCode() Methode irgend einen Hashcode beliebiger Grösse. Damit das Objekt in die Tabelle eingefügt werden kann muss dieser auf ein sinnvolles Maß (die Grösse der Tabelle) begrenzt werden. Dies geschieht durch hashCode() % modulo. Der Wert von modulo sollte natürlich eine Primzahl sein, um häufige Kolissionen zu vermeiden (Standard = 101).

    Die Methode zum Einfügen von Elementen, berechnet erst hashcode % modulo. Da das Feld mit den Listen mit null-Elementen gefüllt wurde, muss geprüft werden, ob schon eine Liste für den Hashcode existiert. Dann wird das Element am Ende dieser Liste angehangen.

    
        public void insert(Object element) {
          int pos = element.hashCode() % modulo;
          if (table[pos] == null) {
            table[pos] = new LinkedList();
          }
          table[pos].addLast(element);
        }

    Es fehlen noch Methoden zum Ausgeben der Elemente. Dies erfolgt durch einen Iterator. Wir müssen also eine Klasse schreiben, die dieses Interface implementiert. Meiner Meinung nach ist es sinnvoll zwei solcher Iteratoren zu erstellen. Einer, der nur die Elemente eines Hashcodes liefert, und ein zweiter, der die gesamte Tabelle durchläuft. Um die Elemente eines Hashcodes zu bekommen, kann auf den ListIterator von LinkedList zurückgegriffen werden. Beim Durchlaufen der gesamten Tabelle ist das komplizierter, da man beim Erreichen des letzten Elements einer Liste zur nächsten springen muss.

    
      protected class EntryIterator implements Iterator {
        public ListIterator iter;
    
        public EntryIterator(int pos) {
          iter = (table[pos] == null ? null : table[pos].listIterator(0));
        }
    
        public boolean hasNext() {
          return (iter == null ? false : iter.hasNext());
        }
    
        public Object next() {
          return (iter == null ? null : iter.next());
        }
    
        public void remove() {
          // do nothing
        }
      }
    
      protected class FullIterator implements Iterator {
        public ListIterator iter;
        public int pos;
    
        public FullIterator() {
          pos = -1;
          iter = null;
          step();
        }
    
        public boolean hasNext() {
          return (iter != null) && (iter.hasNext());
        }
    
        private void step() {
          while (((iter == null) || !iter.hasNext()) && (pos + 1 < modulo)) {
            pos++;
            iter = (table[pos] == null ? null : table[pos].listIterator(0));
          }
        }
    
        public Object next() {
          if (hasNext()) {
            Object result = iter.next();
            step();
            return result;
          }
          return null;
        }
    
        public void remove() {
          // do nothing
        }
      }

    Erstellt werden die Iteratoren durch diese Methoden:

    
      public Iterator elements(int hash) {
        return new EntryIterator(hash % modulo);
      }
    
      public Iterator elements() {
        return new FullIterator();
      }
  2. Es folgt ein kleiner Testrahmen:

    
      LinkedHashTable table = new LinkedHashTable(11);  // hash modulo 11
      String[] names = {"Saake", "Tamassia", "Goodrich", "Toennies", "Engelke",
          "Schallehn", "Schulz", "Bluemel"};
    
      for (int i = 0;  i < names.length;  i++) {
        final String x = names[i];
        table.insert(new Object() {
          String name = x;
    
          public int hashCode() {
            char c = (name.length() >= 3 ? name.toLowerCase().charAt(2) : 'a');
            return 1 + (int) c - (int) 'a';
          }
    
          public String toString() {
            return name;
          }
        });
      }
    
      System.out.println("iterating per hash code");
      for (int i = 0;  i < table.getModulo();  i++) {
        Iterator iter = table.elements(i);  // Iterator for single hash code
        System.out.print("  "+i+":");
        while (iter.hasNext()) {
          System.out.print("  "+iter.next().toString());
        }
        System.out.println("  .");
      }
    
      System.out.println("iterating full table");
      Iterator iter = table.elements();  // Iterator for the whole table
      while (iter.hasNext()) {
        Object o = iter.next();
        System.out.println("  "+(o.hashCode() % table.getModulo())+": "+o.toString());
      }

    Die Ausgabe des ersten Iterators steht in Aufgabe 62. Die zweite Schleife gibt folgendes aus:

    
       1: Saake
       2: Tamassia
       4: Goodrich
       5: Toennies
       7: Engelke
       8: Schallehn
       8: Schulz
      10: Bluemel

Aufgabe 64 - Hashtable - Berechnung umgekehrt

NummerQuersummeHashcodePosition
6660
1641141
9922
21333
731034
22445
891736

Als erstes wurde die 21 eingefügt, da sie an der richtigen Position steht, sich aber den Hashcode mit anderen Nummern teilt. Nun wurden 73, 22, 89, 6 und 164 genau in dieser Reihenfolge eingefügt. Die letzte Zahl, die 9, wurde zu irgend einem Zeitpunkt hinzugenommen, da sie an der richtigen Stelle steht und keine andere Zahl behindert.

Dies sind also alle Möglichkeiten: 9,21,73,22,89,6,164 oder 21,9,73,22,89,6,164 oder 21,73,9,22,89,6,164 oder 21,73,22,9,89,6,164 oder 21,73,22,89,9,6,164 oder 21,73,22,89,6,9,164 oder 21,73,22,89,6,164,9. Sie wollten es ja wissen.

Aufgabe 65 - Tutoraufgabe - insertion sort und heap sort

not yet.


Erstellt von Markus Durzinsky, aktualisiert 27. April 2003
Für Fragen, Probleme oder Anregungen stehe ich gerne zur Verfügung