Iteration versus Rekursion

Hashtabelle mit linearer Verkettung

Pessimistischer Ansatz: Kollisionen treten häufig auf, deshalb wird unter jedem Hashindex gleich eine Liste angelegt, in der Einträge aufgenommen werden können.

Implementation in Python

HashNode ist eine Hilfsdatenstruktur, die Schlüssel und Wert speichert und mit hilfe von next eine verkettete Liste darstellt

 class HashNode:
     def __init__(self,key,data,next):
         self.key = key
         self.data = data
         self.next = next #Verkettung!

Die eigentliche Hashtabelle wir in der Klasse HashTable implementier:

 class HashTable:
     def __init__(self):
        self.capacity = ... #Geigneter Wert
        self.size = 0
        self.array = [None]*self.capacity

In Python wird der Zugriffsoperator [ ] für eine Datenstruktur wie folgt (innerhalb einer Klasse) implementiert:

 def __setitem__(self, key, value)

So dass im Programmtext dann folgender Syntax möglich ist: a[key] = value

Genauso wir die Zuweisung value=a[key] wie folgt umgesetzt

 def __getitem__(self, key, value)

Implementierung der __setitem__ Funktionen in der HashTable Klasse:

 def __setitme__(self, key, value):
     index = hash(key) % self.capacity
     node = self.array[index]
     while node is not None:
         if node.key == key:
             #Element key ist schon in der Tabelle
             #Überschreibe die Daten mit dem neuen Wert
             node.data = value
             return
         #Kollision des Hashwerts, probiere nächsten Key aus
         node = node.next
      #Kein Element hatte den richtigen Schlüssel.
      #==>Es gibt diesen Schlüssel noch nicht
      #Füge also ein neues Element in die Hashtabelle ein
      
      self.array[index] = HashNode(key, value, self.array[index])
      #Der alte Anfang der List wurde der Nachfolger vom neue eingefügten
      #ersten Element
      
      size+=1

Und die Implementierung der __getitem__ Funktionen:

 def __getItem__(self, key):
     index = hash(key) % self.capacity
     node = self.array[index]
     while node is not None:
          if node.key == key #Gefunden!
              return Node.data
          node = node.next
     raise KeyError(key)

Hashtabelle mit offener Adressierung (offenes Hashing)

Optimistischer Ansatz: Kollisionen werden nicht so häufig auftreten.

Idee

Wenn array[index] durch Kollision bereits vergeben ist, probiere einen anderen Index aus.

• Das Array enthält pro Element höchstens ein (key,value)-Paar
• Das Array muss stets mindestens einen freien Platz haben (sonst gäbe es eine Endlosschleife). Es gilt immer self.size < self.capacity. Dies galt für die vorige Hash Implementation nicht.