LISP - Hash-Tabelle

Die Datenstruktur der Hash-Tabelle repräsentiert eine Sammlung von key-and-valuePaare, die basierend auf dem Hash-Code des Schlüssels organisiert sind. Es verwendet den Schlüssel, um auf die Elemente in der Sammlung zuzugreifen.

Eine Hash-Tabelle wird verwendet, wenn Sie mithilfe eines Schlüssels auf Elemente zugreifen müssen, und Sie können einen nützlichen Schlüsselwert identifizieren. Jedes Element in der Hash-Tabelle hat ein Schlüssel / Wert-Paar. Der Schlüssel wird verwendet, um auf die Elemente in der Sammlung zuzugreifen.

Erstellen einer Hash-Tabelle in LISP

In Common LISP ist die Hash-Tabelle eine allgemeine Sammlung. Sie können beliebige Objekte als Schlüssel oder Index verwenden.

Wenn Sie einen Wert in einer Hash-Tabelle speichern, erstellen Sie ein Schlüssel-Wert-Paar und speichern es unter diesem Schlüssel. Später können Sie den Wert mit demselben Schlüssel aus der Hash-Tabelle abrufen. Jeder Schlüssel ist einem einzelnen Wert zugeordnet, obwohl Sie einen neuen Wert in einem Schlüssel speichern können.

Hash-Tabellen in LISP können basierend auf der Art und Weise, wie die Schlüssel verglichen werden können, in drei Typen eingeteilt werden - eq, eql oder gleich. Wenn die Hash-Tabelle für LISP-Objekte gehasht wird, werden die Schlüssel mit eq oder eql verglichen. Wenn die Hash-Tabelle in der Baumstruktur hasht, wird sie mit gleich verglichen.

Das make-hash-tableFunktion wird zum Erstellen einer Hash-Tabelle verwendet. Die Syntax für diese Funktion lautet -

make-hash-table &key :test :size :rehash-size :rehash-threshold

Wo -

  • Das key Argument liefert den Schlüssel.

  • Das :testDas Argument bestimmt, wie Schlüssel verglichen werden. Es sollte einen von drei Werten # 'eq, #' eql oder # 'gleich oder eines der drei Symbole eq, eql oder gleich haben. Wenn nicht angegeben, wird eql angenommen.

  • Das :sizeArgument legt die Anfangsgröße der Hash-Tabelle fest. Dies sollte eine ganze Zahl größer als Null sein.

  • Das :rehash-sizeDas Argument gibt an, um wie viel die Hash-Tabelle vergrößert werden soll, wenn sie voll ist. Dies kann eine Ganzzahl größer als Null sein, dh die Anzahl der hinzuzufügenden Einträge, oder eine Gleitkommazahl größer als 1, dh das Verhältnis der neuen Größe zur alten Größe. Der Standardwert für dieses Argument ist implementierungsabhängig.

  • Das :rehash-thresholdDas Argument gibt an, wie voll die Hash-Tabelle werden kann, bevor sie wachsen muss. Dies kann eine Ganzzahl sein, die größer als Null und kleiner als die: Rehash-Größe ist (in diesem Fall wird sie skaliert, wenn die Tabelle vergrößert wird), oder es kann eine Gleitkommazahl zwischen Null und 1 sein. Der Standardwert hierfür Argument ist implementierungsabhängig.

Sie können die Funktion make-hash-table auch ohne Argumente aufrufen.

Abrufen von Elementen aus und Hinzufügen von Elementen zur Hash-Tabelle

Das gethashDie Funktion ruft ein Element aus der Hash-Tabelle ab, indem sie nach seinem Schlüssel sucht. Wenn der Schlüssel nicht gefunden wird, wird null zurückgegeben.

Es hat die folgende Syntax -

gethash key hash-table &optional default

wo -

  • Schlüssel: ist der zugehörige Schlüssel

  • Hash-Tabelle: ist die zu durchsuchende Hash-Tabelle

  • Standard: ist der Wert, der zurückgegeben werden soll, wenn der Eintrag nicht gefunden wird. Wenn nicht angegeben, ist er null.

Das gethash Die Funktion gibt tatsächlich zwei Werte zurück, wobei der zweite ein Prädikatwert ist, der wahr ist, wenn ein Eintrag gefunden wurde, und falsch, wenn kein Eintrag gefunden wurde.

Zum Hinzufügen eines Elements zur Hash-Tabelle können Sie die verwenden setf Funktion zusammen mit dem gethash Funktion.

Beispiel

Erstellen Sie eine neue Quellcodedatei mit dem Namen main.lisp und geben Sie den folgenden Code ein.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(write (gethash '001 empList)) 
(terpri)
(write (gethash '002 empList))

Wenn Sie den Code ausführen, wird das folgende Ergebnis zurückgegeben:

(CHARLIE BROWN)
(FREDDIE SEAL)

Einen Eintrag entfernen

Das remhashDie Funktion entfernt alle Einträge für einen bestimmten Schlüssel in der Hash-Tabelle. Dies ist ein Prädikat, das wahr ist, wenn es einen Eintrag gab, oder falsch, wenn es keinen gab.

Die Syntax für diese Funktion lautet -

remhash key hash-table

Beispiel

Erstellen Sie eine neue Quellcodedatei mit dem Namen main.lisp und geben Sie den folgenden Code ein.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(setf (gethash '003 empList) '(Mark Mongoose)) 

(write (gethash '001 empList)) 
(terpri)
(write (gethash '002 empList)) 
(terpri)
(write (gethash '003 empList))  
(remhash '003 empList)
(terpri)
(write (gethash '003 empList))

Wenn Sie den Code ausführen, wird das folgende Ergebnis zurückgegeben:

(CHARLIE BROWN)
(FREDDIE SEAL)
(MARK MONGOOSE)
NIL

Die Maphash-Funktion

Das maphash Mit dieser Funktion können Sie eine bestimmte Funktion auf jedes Schlüssel-Wert-Paar in einer Hash-Tabelle anwenden.

Es werden zwei Argumente verwendet - die Funktion und eine Hash-Tabelle. Die Funktion wird einmal für jedes Schlüssel / Wert-Paar in der Hash-Tabelle aufgerufen.

Beispiel

Erstellen Sie eine neue Quellcodedatei mit dem Namen main.lisp und geben Sie den folgenden Code ein.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(setf (gethash '003 empList) '(Mark Mongoose)) 

(maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) empList)

Wenn Sie den Code ausführen, wird das folgende Ergebnis zurückgegeben:

3 => (MARK MONGOOSE)
2 => (FREDDIE SEAL)
1 => (CHARLIE BROWN)