ArrayList und Hashtabelle

ArrayList und HashMap sind häufig verwendete Datenstrukturen in der Programmierung. Wir werden uns nun ihre tatsächliche Implementierung ansehen. Zunächst erinnern wir uns, wie man ein Array verwendet, und dann erstellen wir eine Datenstruktur namens List, die die ArrayList imitiert. Anschließend verwenden wir die Liste, um die Datenstruktur HashTable zu implementieren.

Ein kurzer Rückblick auf Arrays

Ein Array ist ein Objekt, das eine begrenzte Anzahl von Speicherplätzen für Werte enthält. Die Länge (oder Größe) eines Arrays ist die Anzahl der Speicherplätze darin; mit anderen Worten, wie viele Werte im Array gespeichert werden können. Die Größe eines Arrays ist immer vorbestimmt: Sie wird bei der Erstellung des Arrays festgelegt und kann später nicht mehr geändert werden.

Der Array-Typ wird mit eckigen Klammern definiert, die vom Typ der Elemente im Array (typeOfElements[]) gefolgt werden. Ein Array wird mit dem Aufruf new erstellt, gefolgt vom Typ der Elemente in diesem Array, eckigen Klammern und der Anzahl der Elemente im Array, die innerhalb der eckigen Klammern angegeben wird.

int[] numbers = new int[3];
String[] strings = new String[5];

Die Elemente des Arrays werden über die Indizes angesprochen. Im folgenden Beispiel erstellen wir ein Integer-Array der Größe drei und setzen dann Werte an den Indizes 0 und 2. Anschließend geben wir diese Werte aus.

int[] numbers = new int[3];
numbers[0] = 2;
numbers[2] = 5;

System.out.println(numbers[0]);
System.out.println(numbers[2]);

Das Setzen eines einzelnen Wertes an eine bestimmte Position erfolgt ähnlich wie das Setzen eines Wertes für eine normale Variable. Wenn Sie jedoch den Wert in einem Array ablegen, verwenden Sie den Index, um die Position anzugeben.

Um die Größe eines Arrays zu ermitteln, können Sie die öffentliche Objektvariable length verwenden, die Arrays besitzen. Die Elemente einzeln zu durchlaufen, kann zum Beispiel mit einer for-Schleife erreicht werden.

int[] numbers = new int[4];
numbers[0] = 42;
numbers[1] = 13;
numbers[2] = 12;
numbers[3] = 7;

System.out.println("Es gibt " + numbers.length + " Elemente im Array.");

for (int i = 0; i < numbers.length; i++) {
    System.out.println(numbers[i]);
}

Arrays können auf die gleiche Weise wie andere Variablen verwendet werden, sodass sie Objektvariablen, Methodenparameter, Rückgabewerte von Methoden usw. sein können.

Ein bedeutender Teil der allgemein verwendeten Datenstrukturen verwendet Arrays in ihrer internen Implementierung.

Listen

Lassen Sie uns einen Weg untersuchen, wie die Java ArrayList Datenstruktur implementiert werden kann. Java ArrayList verwendet ein Array. Der Typ der Elemente im Array wird durch den Typ-Parameter bestimmt, der der ArrayList übergeben wird. Aus diesem Grund können wir nahezu jeden Datentyp in eine Liste einfügen. Die Java List bietet viele Methoden, aber für uns sind jetzt add, contains, remove und get am relevantesten.

ArrayList<String> strings = new ArrayList<>();
System.out.println(strings.contains("Hello!"));
strings.add("Hello!");
System.out.println(strings.contains("Hello!"));
strings.remove("Hello!");
System.out.println(strings.contains("Hello!"));

Eine neue Liste erstellen

Lassen Sie uns die Klasse List erstellen. Die Liste hat ein generisches Array — der Typ der Elemente im Array wird zur Laufzeit durch Typ-Parameter bestimmt. Setzen wir die Größe des Arrays auf 10. Das Array wird als Typ Objekt erstellt und mit (A[]) new Object[10]; in den generischen Typ geändert — dies wird gemacht, weil Java derzeit den Aufruf new A[10]; nicht unterstützt.

public class List<Type> {
    private Type[] values;

    public List() {
        this.values = (Type[]) new Object[10];
    }
}

Die Liste kapselt ein Array. Zu Beginn enthält jedes Element im Array eine null-Referenz.

Werte zur Liste hinzufügen

Lassen Sie uns die Methode public void add(A value) hinzufügen, die es ermöglicht, Werte zur Liste hinzuzufügen. Wir müssen eine int-Variable hinzufügen, um den ersten freien Index im Array zu verfolgen.

public class List<Type> {

    private Type[] values;
    private int firstFreeIndex;

    public List() {
        this.values = (Type[]) new Object[10];
        this.firstFreeIndex = 0;
    }

    public void add(Type value) {
        this.values[this.firstFreeIndex] = value;
        this.firstFreeIndex++; // entspricht this.firstFreeIndex = this.firstFreeIndex + 1;
    }
}

Jetzt können wir Werte zur Liste hinzufügen — oder zumindest können wir eine Liste erstellen und die add-Methode aufrufen. Wir können jedoch noch nicht testen, ob die Werte tatsächlich in der Liste gespeichert sind.

List<String> myList = new List<>();
myList.add("hello");
myList.add("world");

Werte zur Liste hinzufügen, Teil 2

Es gibt ein kleines Problem mit der add-Methode. Das Problem tritt auf, wenn der folgende Code ausgeführt wird:

List<String> myList = new List<>();
for (int i = 0; i < 11; i++) {
    myList.add("hello");
}

Die Größe der Liste wächst nicht. Einer der Vorteile der ArrayList-Klasse besteht darin, dass sie bei Bedarf wächst — Programmierende müssen sich keine Sorgen machen, dass die Liste voll wird.

Fügen wir die Funktionalität hinzu, die Größe der Liste zu erhöhen. Die Größe der Liste wird erhöht, wenn versucht wird, einen Wert zu einer vollen Liste hinzuzufügen. Die Größe der Liste wird durch Erstellen eines neuen, größeren Arrays erhöht, in das die Werte aus dem alten Array kopiert werden. Danach wird das alte Array verworfen, und die Liste beginnt, das neue Array zu verwenden.

Die Größe des Arrays wird in Java mit der Formel oldSize + oldSize / 2 bestimmt. Lassen Sie uns die gleiche Formel in unserer Implementierung verwenden. Wir erstellen eine neue Methode grow, um die Größe des Arrays zu erhöhen. Die Methode ist nur für andere Methoden in der Klasse verfügbar (sie ist private).

private void grow() {
    int newSize = this.values.length + this.values.length / 2;
    Type[] newValues = (Type[]) new Object[newSize];
    for (int i = 0; i < this.values.length; i++) {
        newValues[i] = this.values[i];
    }

    this.values = newValues;
}

Die Implementierung erstellt ein neues Array, dessen Größe 1,5-mal so groß ist wie die des alten Arrays. Danach werden alle Elemente des alten Arrays in das neue kopiert, und schließlich wird der Wert der Objektvariable values auf das neue Array gesetzt. Der automatische Java-Garbage-Collector entfernt das alte Array irgendwann, da keine Verweise mehr darauf existieren.

Lassen Sie uns die add-Methode so modifizieren, dass die Größe des Arrays bei Bedarf wächst.

public void add(Type value) {
    if(this.firstFreeIndex == this.values.length) {
        grow();
    }

    this.values[this.firstFreeIndex] = value;
    this.firstFreeIndex++;
}

Jetzt können Sie fast unbegrenzt viele Elemente zur Liste hinzufügen.

Überprüfung der Existenz eines Wertes

Als nächstes erstellen wir die Methode public boolean contains(Type value), mit der wir überprüfen können, ob die Liste einen bestimmten Wert enthält oder nicht. Wir nutzen die Tatsache, dass jedes Java-Objekt — unabhängig von seinem Typ — die Klasse Object erbt (oder den Typ Object hat). Daher hat jedes Objekt die Methode public boolean equals(Object object), mit der wir die Gleichheit überprüfen können.

Die Variable firstFreeIndex enthält die Anzahl der Elemente im Array. Wir können die Methode contains so implementieren, dass sie nur die Indizes im Array überprüft, die einen Wert enthalten.

public boolean contains(Type value) {
    for (int i = 0; i < this.firstFreeIndex; i++) {
        if (this.values[i].equals(value)) {
            return true;
        }
    }

    return false;
}

Wir können jetzt die Elemente in der Liste überprüfen.

List<String> myList = new List<>();
System.out.println(myList.contains("hello"));
myList.add("hello");
System.out.println(myList.contains("hello"));

Die Methode oben geht davon aus, dass der Benutzer keinen null-Verweis zur Liste hinzufügt und dass die equals-Methode überprüft, ob der übergebene Wert nicht null ist.

Einen Wert entfernen

Wir können jetzt Werte zur Liste hinzufügen und überprüfen, ob die Liste einen bestimmten Wert enthält. Nun werden wir die Funktionalität implementieren, um einen Wert aus der Liste zu entfernen. Lassen Sie uns die Methode public void remove(Type value) implementieren, die einen Wert des Typs value entfernt.

Eine einfache Implementierung wäre wie folgt:

public void remove(Type value) {
    for (int i = 0; i < this.firstFreeIndex; i++) {
        if (value == this.values[i] || this.values[i].equals(value)) {
            this.values[i] = null;
            this.firstFreeIndex--;
            return;
        }
    }
}

Die oben beschriebene Implementierung ist jedoch problematisch, da sie „leere“ Stellen in der Liste hinterlässt, was dazu führen würde, dass die contains-Methode nicht funktioniert.

public void remove(T value) {
    boolean found = false;
    for (int i = 0; i < this.firstFreeIndex; i++) {
        if (found) {
            this.values[i - 1] = this.values[i];
        } else if (value == this.values[i] || this.values[i].equals(value)) {
            this.firstFreeIndex--;
            found = true;
        }
    }
}

Wir sind mit der obigen Lösung nicht wirklich zufrieden, da sie zu viele Dinge gleichzeitig tut. Die Methode sucht nach einem Element und verschiebt gleichzeitig Elemente. Wir werden die Funktionalität in zwei Methoden aufteilen: private int indexOfValue(Type value), die nach dem Index des übergebenen Wertes sucht, und private void moveToTheLeft(int fromIndex), die die Elemente ab dem angegebenen Index nach links verschiebt.

Zuerst implementieren wir die Methode private int indexOfValue(Type value), die nach dem Index des angegebenen Wertes sucht. Die Methode gibt -1 zurück, wenn der Wert nicht gefunden wird.

private int indexOfValue(Type value) {
    for (int i = 0; i < this.firstFreeIndex; i++) {
        if (this.values[i].equals(value)) {
            return i;
        }
    }

    return -1;
}

Dann implementieren wir die Methode private void moveToTheLeft(int fromIndex), die die Werte ab dem angegebenen Index um eine Stelle nach links verschiebt.

private void moveToTheLeft(int fromIndex) {
    for (int i = fromIndex; i < this.firstFreeIndex - 1; i++) {
        this.values[i] = this.values[i + 1];
    }
}

Jetzt können wir die Methode remove unter Verwendung dieser beiden Methoden implementieren.

public void remove(Type value) {
    int indexOfValue = indexOfValue(value);
    if (indexOfValue < 0) {
        return; // nicht gefunden
    }

    moveToTheLeft(indexOfValue);
    this.firstFreeIndex--;
}

Die Klasse List enthält jetzt einige wiederholte Codezeilen. Die Methode contains ist der Methode indexOfValue sehr ähnlich. Lassen Sie uns die Methode contains so modifizieren, dass sie die Methode indexOfValue verwendet.

public boolean contains(Type value) {
    return indexOfValue(value) >= 0;
}

Jetzt haben wir eine Liste, die die Methoden add, contains und remove hat. Die Liste wächst auch bei Bedarf. Die Implementierung der Liste könnte natürlich weiter verbessert werden, indem beispielsweise eine Funktionalität hinzugefügt wird, die die Größe der Liste verringert, wenn die Anzahl der Werte in ihr abnimmt.

List<String> myList = new List<>();
System.out.println(myList.contains("hello"));
myList.add("hello");
System.out.println(myList.contains("hello"));
myList.remove("hello");
System.out.println(myList.contains("hello"));

Suchen ab einem Index

Lassen Sie uns die Methode public Type value(int index) hinzufügen, die den Wert im angegebenen Index der Liste zurückgibt. Wenn der Benutzer nach einem Wert in einem Index sucht, der außerhalb des Arrays liegt, wird eine IndexOutOfBoundsException ausgelöst.

public Type value(int index) {
    if (index < 0 oder index >= this.firstFreeIndex) {
        throw new ArrayIndexOutOfBoundsException("Index " + index + " außerhalb von [0, " + this.firstFreeIndex + "]");
    }

    return this.values[index];
}

Diese Methode wäre einfacher zu verwenden, wenn der Benutzer Informationen über die Indizes der Werte hätte. Lassen Sie uns die Methode indexOfValue(Type value) so modifizieren, dass sie für alle zugänglich ist, also public statt private.

public int indexOfValue(Type value) {
    for (int i = 0; i < this.firstFreeIndex; i++) {
        if (this.values[i].equals(value)) {
            return i;
        }
    }

    return -1;
}

List<String> myList = new List<>();
System.out.println(myList.contains("hello"));
myList.add("hello");
System.out.println(myList.contains("hello"));
int index = myList.indexOfValue("hello");
System.out.println(index);
System.out.println(myList.value(index));
myList.remove("hello");
System.out.println(myList.contains("hello"));

Größe der Liste

Zum Schluss fügen wir eine Methode hinzu, um die Größe der Liste zu überprüfen. Die Größe der Liste kann durch die Variable firstFreeIndex bestimmt werden.

public int size() {
    return this.firstFreeIndex;
}

Jetzt können wir eine for-Schleife verwenden, um die Elemente der Liste durchzugehen.

List<String> myList = new List<>();
myList.add("hello");
myList.add("world");

for(int i = 0; i < myList.size(); i++) {
    System.out.println(myList.value(i));
}

HashMap

Die HashMap wird als ein Array implementiert, in dem jedes Element eine Liste enthält. Die Listen enthalten (Schlüssel, Wert)-Paare (engl.: key value pairs). Benutzer können in der HashMap nach einem Schlüssel suchen und auch neue Schlüssel-Wert-Paare hinzufügen. Jeder Schlüssel kann höchstens einmal in der HashMap vorkommen.

Die Funktionsweise der HashMap basiert auf dem Hash-Wert des Schlüssels. Wenn ein neues (Schlüssel, Wert)-Paar in einer HashMap gespeichert wird, berechnen wir einen Hash-Wert basierend auf dem zu speichernden Schlüssel. Der Hash-Wert bestimmt den Index des internen Arrays, das zum Speichern verwendet wird. Das (Schlüssel, Wert)-Paar wird in der Liste gespeichert, die an diesem Index gefunden werden kann.

Skizzieren wir, wie eine HashMap funktioniert.

Schlüssel-Wert-Paar

Beginnen wir mit der Erstellung der Klasse Pair, die ein Schlüssel-Wert-Paar darstellt. Wir möchten die HashMap so allgemein wie möglich gestalten, sodass die Typen des Schlüssels und des Wertes zur Laufzeit bestimmt werden. Die Klasse Pair enthält einen Schlüssel und einen Wert sowie die zugehörigen get-Methoden. Die generischen Typen K und V sind nach den Wörtern „key“ und „value“ benannt.

public class Pair<K, V> {

    private K key;
    private V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }
}

Das Erstellen von Schlüssel-Wert-Paaren ist einfach.

Pair<String, Integer> pair = new Pair<>("one", 1);
System.out.println(pair.getKey() + " -> " + pair.getValue());

Eine HashMap erstellen

Eine HashMap enthält ein Array von Listen. Jeder Wert in der Liste ist ein Paar (wie im vorherigen Abschnitt beschrieben), das einen Schlüssel und einen Wert enthält. Eine HashMap kennt auch die Anzahl der Werte. Hier steht uns die zuvor erstellte Klasse List zur Verfügung.

public class HashMap<K, V> {

    private List<Pair<K, V>>[] values;
    private int firstFreeIndex;

    public HashMap() {
        this.values = new List[32];
        this.firstFreeIndex = 0;
    }
}

Einen Wert abrufen

Lassen Sie uns eine Methode namens public V get(K key) implementieren. Sie kann verwendet werden, um einen Wert basierend auf einem Schlüssel zu suchen.

Die Methode beginnt mit der Berechnung eines Hash-Wertes für den Schlüssel und verwendet diesen, um den relevanten Index des internen Arrays der HashMap zu ermitteln. Der Hash-Wert wird mit der Methode hashCode berechnet, die jedes Objekt hat. Dann wird modulo (Rest der Division) verwendet, um sicherzustellen, dass der Index innerhalb der Größenbegrenzungen des internen Arrays bleibt.

Wenn es in dem berechneten Index keine Liste gibt, wurden diesem Index keine Schlüssel-Wert-Paare hinzugefügt. Das bedeutet, dass keine Schlüssel-Wert-Paare mit diesem Schlüssel gespeichert wurden. In diesem Fall geben wir die null-Referenz zurück. Andernfalls durchsucht das Programm die Liste am Index und vergleicht den Parameter key mit dem Schlüssel jedes Schlüssel-Wert-Paares auf dieser Liste. Wenn einer der Schlüssel mit dem Parameter key übereinstimmt, gibt die Methode den Wert dieses Schlüssel-Wert-Paares zurück. Andernfalls finden wir keinen geeigneten Schlüssel (und zugehörigen Wert), sodass die Methode den Wert null zurückgibt.

public V get(K key) {
    int hashValue = Math.abs(key.hashCode() % this.values.length);
    if (this.values[hashValue] == null) {
        return null;
    }

    List<Pair<K, V>> valuesAtIndex = this.values[hashValue];

    for (int i = 0; i < valuesAtIndex.size(); i++) {
        if (valuesAtIndex.value(i).getKey().equals(key)) {
            return valuesAtIndex.value(i).getValue();
        }
    }

    return null;
}

Zur HashMap hinzufügen

Lassen Sie uns die erste Version der Methode public void add(K key, V value) implementieren, mit der Werte zur HashMap hinzugefügt werden. In dieser Version werden wir die Größe des internen Arrays nicht erhöhen, wenn neue Werte zur HashMap hinzugefügt werden.

Die Methode berechnet zunächst den Hash-Wert für den Schlüssel und verwendet diesen, um den passenden Index im internen Array zu bestimmen. Wenn an diesem Index kein Wert vorhanden ist, erstellen wir eine Liste an diesem Index. Danach durchsucht die Methode die Liste am Index und sucht nach einem Schlüssel-Wert-Paar, dessen Schlüssel mit dem Schlüssel des hinzuzufügenden Schlüssel-Wert-Paares übereinstimmt. Wenn der passende Schlüssel gefunden wird, wird der zugehörige Wert so aktualisiert, dass er dem neuen Wert entspricht. Andernfalls fügt die Methode ein neues Schlüssel-Wert-Paar in die Liste ein — in diesem Fall wird auch die Anzahl der gespeicherten Werte um eins erhöht.

public void add(K key, V value) {
    int hashValue = Math.abs(key.hashCode() % values.length);
    if (values[hashValue] == null) {
        values[hashValue] = new List<>();
    }

    List<Pair<K, V>> valuesAtIndex = values[hashValue];

    int index = -1;
    for (int i = 0; i < valuesAtIndex.size(); i++) {
        if (valuesAtIndex.value(i).getKey().equals(key)) {
            index = i;
            break;
        }
    }

    if (index < 0) {
        valuesAtIndex.add(new Pair<>(key, value));
        this.firstFreeIndex++;
    } else {
        valuesAtIndex.value(index).setValue(value);
    }
}

Die Methode ist ziemlich komplex, daher lassen Sie uns sie in kleinere Teile aufteilen. Der erste Teil ist verantwortlich für das Finden der Liste, die dem Schlüssel zugeordnet ist, und der zweite Teil ist verantwortlich für das Finden des Schlüssels in dieser Liste.

private List<Pair<K, V>> getListBasedOnKey(K key) {
    int hashValue = Math.abs(key.hashCode() % values.length);
    if (values[hashValue] == null) {
        values[hashValue] = new List<>();
    }

    return values[hashValue];
}

private int getIndexOfKey(List<Pair<K, V>> myList, K key) {
    for (int i = 0; i < myList.size(); i++) {
        if (myList.value(i).getKey().equals(key)) {
            return i;
        }
    }

    return -1;
}

Jetzt können wir eine etwas klarere Implementierung der Methode public void add(K key, V value) schreiben.

public void add(K key, V value) {
    List<Pair<K, V>> valuesAtIndex = getListBasedOnKey(key);
    int index = getIndexOfKey(valuesAtIndex, key);

    if (index < 0) {
        valuesAtIndex.add(new Pair<>(key, value));
        this.firstFreeIndex++;
    } else {
        valuesAtIndex.value(index).setValue(value);
    }
}

Zur Hashtabelle hinzufügen, Teil 2

Die oben beschriebene Methode zum Hinzufügen zu einer Hashtabelle funktioniert teilweise. Der größte Fehler in der Funktionalität besteht darin, dass die Größe des internen Arrays nicht erhöht wird, wenn die Anzahl der Werte zu groß wird. Fügen wir eine Wachstumsfunktionalität zum Programm hinzu, die die Größe des internen Arrays der HashMap verdoppelt. Die Wachstumsoperation sollte auch jeden Wert in der HashMap in das neu erstellte größere Array verschieben.

Skizzieren wir den Anfang der Wachstumsfunktional

ität. Die verantwortliche Methode sollte ein neues Array erstellen, dessen Größe doppelt so groß ist wie die des alten Arrays. Danach geht sie das alte Array Index für Index durch. Die gefundenen Schlüssel-Wert-Paare werden in das neue Array kopiert. Schließlich wird das alte Array durch das neue ersetzt.

Unten ist eine erste Version, wie die Methode funktionieren sollte. Wir haben das Kopieren noch nicht implementiert.

private void grow() {
    // erstelle ein neues Array
    List<Pair<K, V>>[] newValues = new List[this.values.length * 2];

    for (int i = 0; i < this.values.length; i++) {
        // kopiere die Werte des alten Arrays in das neue

    }

    // ersetze das alte Array durch das neue
    this.values = newValues;
}

Dann beginnen wir damit, eine Methode zu erstellen, die die Liste der Werte an einem Index des alten Arrays in das neue Array kopiert. Beim Kopieren wird der Speicherort jedes Schlüssel-Wert-Paares für das neue Array neu berechnet — dies geschieht, weil die Größe des internen Arrays wächst und wir alle Schlüssel-Wert-Paare so gleichmäßig wie möglich in diesem Array verteilen möchten.

private void copy(List<Pair<K, V>>[] newArray, int fromIdx) {
    for (int i = 0; i < this.values[fromIdx].size(); i++) {
        Pair<K, V> value = this.values[fromIdx].value(i);

        int hashValue = Math.abs(value.getKey().hashCode() % newArray.length);
        if(newArray[hashValue] == null) {
            newArray[hashValue] = new List<>();
        }

        newArray[hashValue].add(value);
    }
}

Jetzt können Sie die copy-Methode aus der grow-Methode aufrufen.

private void grow() {
    // erstelle ein neues Array
    List<Pair<K, V>>[] newArray = new List[this.values.length * 2];

    for (int i = 0; i < this.values.length; i++) {
        // kopiere die Werte des alten Arrays in das neue
        copy(newArray, i);
    }

    // ersetze das alte Array durch das neue
    this.values = newArray;
}

Zum Schluss fügen wir die Wachstumsfunktionalität als Teil der add-Methode hinzu. Wir möchten die Größe der HashMap erhöhen, wenn die Anzahl der Schlüssel-Wert-Paare darin größer ist als 75 % der Größe des internen Arrays.

public void add(K key, V value) {
    List<Pair<K, V>> valuesAtIndex = getListBasedOnKey(key);
    int index = getIndexOfKey(valuesAtIndex, key);

    if (index < 0) {
        valuesAtIndex.add(new Pair<>(key, value));
        this.firstFreeIndex++;
    } else {
        valuesAtIndex.value(index).setValue(value);
    }

    if (1.0 * this.firstFreeIndex / this.values.length > 0.75) {
        grow();
    }
}

Entfernen

Geben wir der HashMap die Funktionalität, ein Schlüssel-Wert-Paar basierend auf dem Schlüssel zu entfernen. Die Entfernungsfunktionalität gibt null zurück, wenn der Wert nicht gefunden werden kann, und entfernt andernfalls den Wert, der mit dem zu entfernenden Schlüssel gekoppelt ist.

Wir können die bereits implementierte Methode in der Entfernen-Methode nutzen. Erklären Sie sich selbst (laut), wie die unten beschriebene Methode konkret funktioniert.

public V remove(K key) {
    List<Pair<K, V>> valuesAtIndex = getListBasedOnKey(key);
    if (valuesAtIndex.size() == 0) {
        return null;
    }

    int index = getIndexOfKey(valuesAtIndex, key);
    if (index < 0) {
        return null;
    }

    Pair<K, V> pair = valuesAtIndex.value(index);
    valuesAtIndex.remove(pair);
    return pair.getValue();
}

Über die Leistung der Suche

Vergleichen wir die Leistung der Suche in einer Liste oder einer HashMap. Um die Leistung zu bewerten, können wir die Methode System.nanoTime() verwenden und den von ihr zurückgegebenen Wert, der die Zeit in Nanosekunden darstellt. Das Programm erstellt zunächst eine HashMap und eine Liste, die jeweils eine Million Elemente enthalten, wonach tausend zufällig ausgewählte Werte aus beiden ausgewählt werden. Etwa 50 % der Werte werden sowohl in den Strukturen gefunden.

List<String> myList = new List<>();
HashMap<String, String> hashMap = new HashMap<>();

for (int i = 0; i < 1000000; i++) {
    myList.add("" + i);
    hashMap.add("" + i, "" + i);
}

List<String> elements = new List<>();
Random randomizer = new Random();
for (int i = 0; i < 1000; i++) {
    elements.add("" + randomizer.nextInt(2000000));
}

long listSearchStartTime = System.nanoTime();
for (int i = 0; i < elements.size(); i++) {
    myList.contains(elements.value(i));
}
long listSearchEndTime = System.nanoTime();

long hashMapSearchStartTime = System.nanoTime();
for (int i = 0; i < elements.size(); i++) {
    hashMap.hae(elements.value(i));
}
long hashMapSearchEndTime = System.nanoTime();

long listSearch = listSearchEndTime - listSearchStartTime;
System.out.println("List: Die Suche dauerte etwa " + listSearch / 1000000 + " Millisekunden (" +
    listSearch + " Nanosekunden.)");

long hashMapSearch = hashMapSearchEndTime - hashMapSearchStartTime;
System.out.println("HashMap: Die Suche dauerte etwa " + hashMapSearch / 1000000 +
    " Millisekunden (" + hashMapSearch + " Nanosekunden.)");

Die Liste und HashMap, die in diesem Kapitel beschrieben werden, unterscheiden sich zwar in einigen Details von den fertigen Tools, die wir in anderen Teilen des Kurses verwenden. Die von der Programmiersprache angebotenen Datenstrukturen enthalten eine Vielzahl von Optimierungen — andere Kurse gehen detaillierter auf diese ein. Für die Zwecke dieses Kurses ist es ausreichend, zu wissen, wie man die Datenstrukturen verwendet und ein gewisses Verständnis für die Leistungsunterschiede und deren Einsatzmöglichkeiten zu haben.