Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


16. Hashing



Übungen

  1. Beschreiben Sie, wie Sie unter Verwendung eines guten Zufallszahlengenerators eine Hash-Funktion implementieren könnten. Wäre es sinnvoll, unter Verwendung einer Hash-Funktion einen Zufallszahlengenerator zu implementieren?
  2. Wie lange könnte es im ungünstigsten Fall dauern, N Schlüssel in eine ursprünglich leere Tabelle einzufügen, wenn getrennte Verkettung mit ungeordneten Listen angewandt wird? Beantworten Sie die gleiche Frage für sortierte Listen.
  3. Geben Sie den Inhalt der sich ergebenden Hash-Tabelle an, wenn die Schlüssel E A S Y Q U E S T I O N unter Verwendung des linearen Austestens in der angegebenen Reihenfolge in eine ursprünglich leere Tabelle der Größe 13 eingefügt werden. (Verwenden Sie h1(k) = k mod 13 als Hash-Funktion für den k-ten Buchstaben des Alphabets.)
  4. Geben Sie den Inhalt der sich ergebenden Hash-Tabelle an, wenn die Schlüssel E A S Y Q U E S T I O N unter Verwendung des doppelten Hashing in der angegebenen Reihenfolge in eine ursprünglich leere Tabelle der Größe 13 eingefügt werden. (Verwenden Sie h1(k) aus der vorangegangenen Übung, h2(k) = 1 + (k mod 11) als zweite Hash-Funktion.)
  5. Wie viele Tests sind bei doppeltem Hashing etwa erforderlich, um eine Tabelle zu erzeugen, die aus N gleichen Schlüsseln besteht?
  6. Welche Hashing-Methode würden Sie für eine Anwendung benutzen, in der wahrscheinlich viele gleiche Schlüssel auftreten?
  7. Angenommen, die Anzahl der Elemente, die in einer Hash-Tabelle angeordnet werden sollen, ist im voraus bekannt. Unter welchen Bedingungen ist getrennte Verkettung doppeltem Hashing vorzuziehen?
  8. Angenommen, einem Programmierer ist in seinem Programm für doppeltes Hashing ein Fehler unterlaufen, so daß eine der Hash-Funktionen immer den gleichen Wert zurückgibt (nicht 0). Beschreiben Sie, was in jeder Situation (wenn die erste Hash-Funktion falsch ist und wenn die zweite falsch ist) passiert.
  9. Welche Hash-Funktion sollte verwendet werden, wenn im voraus bekannt ist, daß die Schlüsselwerte in einen relativ kleinen Bereich fallen?
  10. Beurteilen Sie den folgenden Algorithmus zum Löschen aus einer Hash-Tabelle, die mit linearem Austesten erzeugt wurde: Durchsuche die Tabelle von dem zu löschenden Element aus nach rechts (falls erforderlich, mit Rückkehr zum Tabellenanfang), bis eine leere Position gefunden wird, durchsuche sie dann nach links, bis ein Element mit dem gleichen Hash-Wert gefunden wird. Ersetze dann das zu löschende Element durch dieses Element, wobei dessen Position in der Tabelle leer bleibt.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]