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)