Was ist ein assoziatives Array?
Ein assoziatives Array, das auch als Hash -Tabelle oder Hash -Karte bezeichnet wird, ähnelt einem Standardarray, außer dass der Index des Arrays eine Zeichenfolge anstelle einer Ganzzahl sein kann. In vielen Datenbankanwendungen und in anderen Programmen, die sich mit großen Datenmengen befassen, ist ein assoziatives Array ein wesentliches Element, um auf effiziente Weise auf Informationen zu sortieren und zugreifen zu können. Im Kern eines assoziativen Arrays befindet sich ein Standardarray, das mit Ganzzahlen indiziert ist, wie es normalerweise der Fall ist. Ein spezieller Algorithmus, der als Hash -Funktion bezeichnet wird, wandelt den String -Index in einen Ganzzahlindex um, um den Wert zu ermitteln. Dies ist eine konsistente Konvertierung, daher muss der tatsächliche Ganzzahl -Index nie gespeichert werden, sondern wird stattdessen jedes Mal aus der Zeichenfolge berechnet. Was normalerweise als Index bezeichnet wird - der numerische Ort eines Elements in einem Array - heißt dieSchlüssel. Die mit dem Schlüssel zugeordneten Daten werden als Wert bezeichnet. Dies bedeutet, dass innerhalb eines assoziativen Arrays ein Schlüssel zu einem Wert zugeordnet ist, der mit einem Index korreliert, das ein Element in einem Standardarray in der Datenstruktur verweist.
im Herzen jedes assoziativen Arrays ist die Hash -Funktion. Dies ist ein Algorithmus, der verwendet wird, um den numerischen Index eines Werts basierend auf dem Schlüssel zu bestimmen. Es gibt verschiedene Arten von Hash -Funktionen, von denen einige für Tasten betrieben werden, die Ganzzahlen sind, und einige für die Arbeit an Schlüsseln, die Saiten sind. Im Falle eines Ganzzahlschlüssel
Die Hash -Funktion kann für Tasten, die Saiten sind, viel komplexer sein. Einige Methoden umfassen das Hinzufügen des numerischen Werts jedes Zeichens in der Zeichenfolge und dann durch eine Zahl,Oder verwenden Sie nur die ersten Zeichen der Zeichenfolge, um eine eindeutige Zahl zu erhalten. Es gibt viele Möglichkeiten, eine Zahl aus einer Zeichenfolge abzuleiten.
Bei einem großen Teil von Schlüsselwertpaaren in einem assoziativen Array wird ein Problem, das auftreten kann, als Kollision bezeichnet. Kollision tritt auf, wenn der von einem Schlüssel abgeleitete Ganzzahl -Index mit dem Ganzzahlindex eines anderen Schlüssels identisch ist. Diese beiden Schlüssel weisen dann effektiv auf denselben Index im Wert -Array hin. Es gibt verschiedene Lösungen für die Kollision, vor allem, weil es in den meisten praktischen Anwendungen eine hohe Wahrscheinlichkeit hat.
Eine Lösung für die Kollision besteht darin, dass jeder Wertindex tatsächlich eine verknüpfte Liste ist, sodass der Speicherort mehr als einen Wert behalten kann, wenn mehr als ein Schlüssel zu diesem Indexspeicherort auflöst. Dies wird als Ketten bezeichnet und ist eine einfache Möglichkeit, mit einer Kollision umzugehen, aber es kann auch die Zeit verlangsamen, die zum Abrufen der Informationen benötigt wird. Eine andere Methode des Umgangs mit einer Kollision wird als lineare Untersuchung bezeichnet.Wenn eine Kollision auftritt, bewegt sich lineare Untersuchungen, indem sie sich durch das Wert -Array bewegt, bis ein nicht verwendeter Index gefunden wird. Diese Lösung kann dazu beitragen, die Daten gleichmäßig im assoziativen Array verteilt zu halten, aber sie kann auch die Zeit erhöhen, die erforderlich ist, um einen Wert zu suchen.