Was ist ein assoziatives Array?
Ein assoziatives Array, auch Hash-Tabelle oder Hash-Map genannt, ähnelt einem Standard-Array, mit der Ausnahme, dass der Index des Arrays eine Zeichenfolge anstelle einer Ganzzahl sein kann. In vielen Datenbankanwendungen und in anderen Programmen, die große Datenmengen verarbeiten, ist ein assoziatives Array ein wichtiges Element, um Informationen effizient zu sortieren und darauf zuzugreifen. Kern eines assoziativen Arrays ist ein Standard-Array, das wie üblich mit ganzen Zahlen indiziert ist. Ein spezieller Algorithmus namens Hash-Funktion konvertiert den String-Index in einen Integer-Index, um den Wert zu finden. Dies ist eine konsistente Konvertierung, sodass der tatsächliche Ganzzahlindex nie gespeichert werden muss, sondern bei Bedarf jedes Mal aus der Zeichenfolge berechnet wird.
Die Terminologie, die bei der Bezugnahme auf ein assoziatives Array verwendet wird, kann sich geringfügig von der Terminologie für ein normales Array unterscheiden. Was normalerweise als Index bezeichnet wird - die numerische Position eines Elements innerhalb eines Arrays - wird als Schlüssel bezeichnet. Die dem Schlüssel zugeordneten Daten werden als Wert bezeichnet. Dies bedeutet, dass innerhalb eines assoziativen Arrays ein Schlüssel einem Wert zugeordnet ist, der mit einem Index korreliert, der auf ein Element in einem Standardarray in der Datenstruktur verweist.
Das Herzstück eines jeden assoziativen Arrays ist die Hash-Funktion. Dies ist ein Algorithmus, mit dem der numerische Index eines Werts basierend auf dem Schlüssel ermittelt wird. Es gibt verschiedene Arten von Hash-Funktionen, von denen einige für die Verarbeitung ganzer Schlüssel und andere für die Verarbeitung von Zeichenfolgen entwickelt wurden. Im Fall eines Ganzzahlschlüssels besteht eine beliebte Methode darin, den Schlüsselwert durch die Größe des Arrays zu dividieren und den Rest der Division zu verwenden, um hoffentlich einen eindeutigen Indexwert zu erhalten.
Die Hash-Funktion kann für Schlüssel, die Zeichenfolgen sind, sehr viel komplexer sein. Einige Methoden umfassen das Hinzufügen des numerischen Werts jedes Zeichens in der Zeichenfolge und das anschließende Teilen durch eine Zahl oder das Verwenden nur der ersten Zeichen der Zeichenfolge, um eine eindeutige Nummer zu erhalten. Es gibt viele Möglichkeiten, eine Zahl aus einer Zeichenfolge abzuleiten.
Bei der Verarbeitung einer großen Anzahl von Schlüssel-Wert-Paaren in einem assoziativen Array kann ein Problem auftreten, das als Kollision bezeichnet wird. Kollision tritt auf, wenn der von einem Schlüssel abgeleitete Ganzzahlindex mit dem Ganzzahlindex eines anderen Schlüssels identisch ist. Diese beiden Schlüssel verweisen dann effektiv auf denselben Index im Wertearray. Es gibt verschiedene Lösungen für Kollisionen, vor allem, weil sie in den meisten praktischen Anwendungen mit hoher Wahrscheinlichkeit auftreten.
Eine Lösung für eine Kollision besteht darin, dass jeder Wertindex tatsächlich eine verknüpfte Liste ist. Wenn also mehr als ein Schlüssel zu dieser Indexposition aufgelöst wird, kann die Position mehr als einen Wert enthalten. Dies wird als Verkettung bezeichnet und ist eine einfache Methode zum Behandeln einer Kollision. Sie kann jedoch auch die Zeit verlangsamen, die zum Abrufen der Informationen erforderlich ist. Eine andere Methode, mit einer Kollision umzugehen, ist das lineare Abtasten. Bei einer Kollision durchläuft die lineare Abtastung das Wertearray, bis ein nicht verwendeter Index gefunden wird. Diese Lösung kann dazu beitragen, die Daten im assoziativen Array gleichmäßig zu verteilen, aber auch den Zeitaufwand für die Suche nach einem Wert erhöhen.