LISP - 雜湊表


雜湊表的資料結構表示是基於鍵雜湊程式碼進行組織鍵 - 值對的集合。它使用鍵來存取集合中的元素。

雜湊表是用於需要使用一鍵存取元素,可以找出一個有用的鍵值。在雜湊表中每個專案都有一個鍵/值對。鍵是用於存取該集合中的項。

LISP中建立雜湊表

在Common Lisp中表是一種通用的集合。可以隨心所欲的使用物件作為一個鍵或索引。

當在一個雜湊表中儲存的值,設定鍵 - 值對,並將其儲存在該鍵。以後可以從雜湊表中使用相同的key檢索值。每個鍵對映到一個單一的值,雖然可以在一鍵儲存新值。

雜湊表,在LISP,可分為三種型別,基於這樣的鍵所不能compared - eq, eql 或 equal。如果雜湊表進行雜湊處理的LISP物件然後將鑰匙與eq或eql比較。如果在樹結構中的雜湊表雜湊,那麼它會使用相等比較。

make-hash-table函式用於建立一個雜湊表。此函式語法的是:

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

那麼:

  • key 引數提供了鍵。

  • :test 引數確定鍵如何比較- 它應該有一個三個值 #'eq, #'eql 或 #'equal或三個符號式之一,eq, eql, 或 equal。如果未指定,則使用eql。

  • :size 引數設定雜湊表的初始大小。這應該是一個大於零的整數。

  • :rehash-size 引數指定用多少提高雜湊表的大小時已滿。這可以是一個大於零的整數,這是新增的項的數量,或者它可以是一個浮點數大於1,這是新的尺寸,以舊的大小的比率。該引數的預設值是實現相關。

  • :rehash-threshold 引數指定的雜湊表如何能充分得到之前,它必須成長。這可以是一個大於零的整數,並且小於 :rehash-size(在這種情況下,每當該表是生長其將被縮小),或者它可以是零和1之間的浮點數此預設值。引數是實現相關的。

也可以呼叫 make-hash-table函式的無引數形式。

正在從項和新增項到雜湊表

gethash函式通過搜尋其鍵檢索從雜湊表中的項。如果沒有找到鍵,那麼它返回nil。

它的語法如下:

gethash key hash-table &optional default

那麼:

  • key: 是相關聯的鍵

  • hash-table: 是要被搜尋的雜湊表

  • default: 要返回的值,如果沒有找到該入口,它是nil,如果不是指定的值。

gethash函式實際上返回兩個值,第二個是一個謂詞值,如果發現一個項則是true;如果被發現沒有專案返回false。

對於將項新增到雜湊表中,可以使用setf函式及gethash函式。

範例

建立一個名為main.lisp一個新的原始碼檔案,並在其中輸入如下程式碼:

(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))  

當執行程式碼,它返回以下結果:

(CHARLIE BROWN)
(FREDDIE SEAL)

刪除條目

remhash函式刪除在雜湊表中的特定鍵的任何項。如果是一個謂詞,那麼它為true,如果沒有有一個項則為false。

其函式語法:

remhash key hash-table

範例

建立一個名為main.lisp一個新的原始碼檔案,並在其中輸入如下程式碼:

(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))  

當執行程式碼,它返回以下結果:

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

maphash函式

maphash函式允許在每個鍵 - 值對應用一個指定的函式在一個雜湊表。

它有兩個引數 - 函式和雜湊表,並呼叫該函式一次為每個鍵/值對的雜湊表中。

範例

建立一個名為main.lisp一個新的原始碼檔案,並在其中輸入如下程式碼:

(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)

當執行程式碼,它返回以下結果:

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