Eine Abstraktion für assoziative Arrays II

Folgendes wird bei einem konkreten assoziativen Array in Abhängigkeit des Datentyps benötigt:

Eine Hash-Funktion. Damit sie von der Tabellengröße unabhängig ist, kann sie einfach einen Wert vom Typ INTEGER zurückliefern. Die Implementierung des assoziativen Arrays kann dann den Wert in das Intervall [0, n-1] abbilden.

Eine Operation, die zwei Schlüssel auf Identität prüft. Da die Hash-Funktion typischerweise nicht injektiv ist, müssen Schlüssel mit dem gleichen Hash-Wert voneinander unterschieden werden können.

Wie zuvor bei den binären sortierten Bäumen ist es sinnvoll, noch eine Operation hinzuzufügen, die überprüft, ob ein Objekt zu einem konkreten assoziativen Array ``passt''.

Analog zu SortedBinaryTrees gibt es dann die Operationen Insert, Delete und Lookup.

Da es jedoch keine Sortierung gibt, sind Operationen wie Next, Prev und eine Traverse in sortierter Reihenfolge nicht möglich. Stattdessen kann nur eine Iteration mit einer undefinierten Reihenfolge unterstützt werden.