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)