第四章：特殊數(shù)據(jù)結(jié)構(gòu)

在之前的章節(jié)里，我們討論了列表，Lisp 最多功能的數(shù)據(jù)結(jié)構(gòu)。本章將演示如何使用 Lisp 其它的數(shù)據(jù)結(jié)構(gòu)：數(shù)組（包含向量與字符串），結(jié)構(gòu)以及哈希表。它們或許不像列表這么靈活，但存取速度更快并使用了更少空間。

Common Lisp 還有另一種數(shù)據(jù)結(jié)構(gòu)：實(shí)例（instance）。實(shí)例將在 11 章討論，講述 CLOS。

4.1 數(shù)組 (Array)

在 Common Lisp 里，你可以調(diào)用?make-array?來(lái)構(gòu)造一個(gè)數(shù)組，第一個(gè)實(shí)參為一個(gè)指定數(shù)組維度的列表。要構(gòu)造一個(gè)?2?x?3?的數(shù)組，我們可以：

> (setf arr (make-array '(2 3) :initial-element nil))
#<Simple-Array T (2 3) BFC4FE>

Common Lisp 的數(shù)組至少可以達(dá)到七個(gè)維度，每個(gè)維度至少可以容納 1023 個(gè)元素。

:initial-element?實(shí)參是選擇性的。如果有提供這個(gè)實(shí)參，整個(gè)數(shù)組會(huì)用這個(gè)值作為初始值。若試著取出未初始化的數(shù)組內(nèi)的元素，其結(jié)果為未定義（undefined）。

用?aref?取出數(shù)組內(nèi)的元素。與 Common Lisp 的存取函數(shù)一樣，?aref?是零索引的（zero-indexed）：

> (aref arr 0 0)
NIL

要替換數(shù)組的某個(gè)元素，我們使用?setf?與?aref?：

> (setf (aref arr 0 0) 'b)
B
> (aref arr 0 0)
B

要表示字面常量的數(shù)組（literal array），使用?#na?語(yǔ)法，其中?n?是數(shù)組的維度。舉例來(lái)說(shuō)，我們可以這樣表示?arr?這個(gè)數(shù)組：

#2a((b nil nil) (nil nil nil))

如果全局變量?*print-array*?為真，則數(shù)組會(huì)用以下形式來(lái)顯示：

> (setf *print-array* t)
T
> arr
#2A((B NIL NIL) (NIL NIL NIL))

如果我們只想要一維的數(shù)組，你可以給?make-array?第一個(gè)實(shí)參傳一個(gè)整數(shù)，而不是一個(gè)列表：

> (setf vec (make-array 4 :initial-element nil))
#(NIL NIL NIL NIL)

一維數(shù)組又稱為向量（vector）。你可以通過(guò)調(diào)用?vector?來(lái)一步驟構(gòu)造及填滿向量，向量的元素可以是任何類型：

> (vector "a" 'b 3)
#("a" b 3)

字面常量的數(shù)組可以表示成?#na?，字面常量的向量也可以用這種語(yǔ)法表達(dá)。

可以用?aref?來(lái)存取向量，但有一個(gè)更快的函數(shù)叫做?svref?，專門用來(lái)存取向量。

> (svref vec 0)
NIL

在?svref?內(nèi)的 “sv” 代表“簡(jiǎn)單向量”（“simple vector”），所有的向量缺省是簡(jiǎn)單向量。?[1]

4.2 示例：二叉搜索 (Example: Binary Search)

作為一個(gè)示例，這小節(jié)演示如何寫(xiě)一個(gè)在排序好的向量里搜索對(duì)象的函數(shù)。如果我們知道一個(gè)向量是排序好的，我們可以比（65頁(yè)）find?做的更好，?find?必須依序檢查每一個(gè)元素。我們可以直接跳到向量中間開(kāi)始找。如果中間的元素是我們要找的對(duì)象，搜索完畢。要不然我們持續(xù)往左半部或往右半部搜索，取決于對(duì)象是小于或大于中間的元素。

圖 4.1 包含了一個(gè)這么工作的函數(shù)。其實(shí)這兩個(gè)函數(shù)：?bin-search?設(shè)置初始范圍及發(fā)送控制信號(hào)給?finder?，?finder?尋找向量?vec內(nèi)?obj?是否介于?start?及?end?之間。

(defun bin-search (obj vec)
  (let ((len (length vec)))
    (and (not (zerop len))
         (finder obj vec 0 (- len 1)))))

(defun finder (obj vec start end)
  (let ((range (- end start)))
    (if (zerop range)
        (if (eql obj (aref vec start))
            obj
            nil)
        (let ((mid (+ start (round (/ range 2)))))
          (let ((obj2 (aref vec mid)))
            (if (< obj obj2)
                (finder obj vec start (- mid 1))
                (if (> obj obj2)
                    (finder obj vec (+ mid 1) end)
                    obj)))))))

圖 4.1: 搜索一個(gè)排序好的向量

如果要找的?range?縮小至一個(gè)元素，而如果這個(gè)元素是?obj?的話，則?finder?直接返回這個(gè)元素，反之返回?nil?。如果?range?大于1?，我們?cè)O(shè)置?middle?(?round?返回離實(shí)參最近的整數(shù)) 為?obj2?。如果?obj?小于?obj2?，則遞歸地往向量的左半部尋找。如果?obj大于?obj2?，則遞歸地往向量的右半部尋找。剩下的一個(gè)選擇是?obj=obj2?，在這個(gè)情況我們找到要找的元素，直接返回這個(gè)元素。

如果我們插入下面這行至?finder?的起始處：

(format t "~A~%" (subseq vec start (+ end 1)))

我們可以觀察被搜索的元素的數(shù)量，是每一步往左減半的：

> (bin-search 3 #(0 1 2 3 4 5 6 7 8 9))
#(0 1 2 3 4 5 6 7 8 9)
#(0 1 2 3)
#(3)
3

4.3 字符與字符串 (Strings and Characters)

字符串是字符組成的向量。我們用一系列由雙引號(hào)包住的字符，來(lái)表示一個(gè)字符串常量，而字符?c?用?#\c?表示。

每個(gè)字符都有一個(gè)相關(guān)的整數(shù) ── 通常是 ASCII 碼，但不一定是。在多數(shù)的 Lisp 實(shí)現(xiàn)里，函數(shù)?char-code?返回與字符相關(guān)的數(shù)字，而?code-char?返回與數(shù)字相關(guān)的字符。

字符比較函數(shù)?char<?（小于），?char<=?（小于等于)，?char=?（等于)，?char>=?（大于等于) ，?char>?（大于)，以及?char/=?（不同)。他們的工作方式和 146 頁(yè)（譯注 9.3 節(jié))比較數(shù)字用的操作符一樣。

> (sort "elbow" #'char<)
"below"

由于字符串是字符向量，序列與數(shù)組的函數(shù)都可以用在字符串。你可以用?aref?來(lái)取出元素，舉例來(lái)說(shuō)，

> (aref "abc" 1)
#\b

但針對(duì)字符串可以使用更快的?char?函數(shù)：

> (char "abc" 1)
#\b

可以使用?setf?搭配?char?（或?aref?）來(lái)替換字符串的元素：

> (let ((str (copy-seq "Merlin")))
   (setf (char str 3) #\k)
   str)

如果你想要比較兩個(gè)字符串，你可以使用通用的?equal?函數(shù)，但還有一個(gè)比較函數(shù)，是忽略字母大小寫(xiě)的?string-equal?：

> (equal "fred" "fred")
T
> (equal "fred" "Fred")
NIL
>(string-equal "fred" "Fred")
T

Common Lisp 提供大量的操控、比較字符串的函數(shù)。收錄在附錄 D，從 364 頁(yè)開(kāi)始。

有許多方式可以創(chuàng)建字符串。最普遍的方式是使用?format?。將第一個(gè)參數(shù)設(shè)為?nil?來(lái)調(diào)用?format?，使它返回一個(gè)原本會(huì)印出來(lái)的字符串：

> (format nil "~A or ~A" "truth" "dare")
"truth or dare"

但若你只想把數(shù)個(gè)字符串連結(jié)起來(lái)，你可以使用?concatenate?，它接受一個(gè)特定類型的符號(hào)，加上一個(gè)或多個(gè)序列：

> (concatenate 'string "not " "to worry")
"not to worry"

4.4 序列 (Sequences)

在 Common Lisp 里，序列類型包含了列表與向量（因此也包含了字符串）。有些用在列表的函數(shù)，實(shí)際上是序列函數(shù)，包括remove?、?length?、?subseq?、?reverse?、?sort?、?every?以及?some?。所以 46 頁(yè)（譯注 3.11 小節(jié)的?mirror??函數(shù)）我們所寫(xiě)的函數(shù)，也可以用在其他種類的序列上：

> (mirror? "abba")
T

我們已經(jīng)看過(guò)四種用來(lái)取出序列元素的函數(shù)： 給列表使用的?nth?， 給向量使用的?aref?及?svref?，以及給字符串使用的?char?。 Common Lisp 也提供了通用的?elt?，對(duì)任何種類的序列都有效：

> (elt '(a b c) 1)
B

針對(duì)特定類型的序列，特定的存取函數(shù)會(huì)比較快，所以使用?elt?是沒(méi)有意義的，除非在代碼當(dāng)中，有需要支持通用序列的地方。

使用?elt?，我們可以寫(xiě)一個(gè)針對(duì)向量來(lái)說(shuō)更有效率的?mirror??版本：

(defun mirror? (s)
  (let ((len (length s)))
    (and (evenp len)
         (do ((forward 0 (+ forward 1))
              (back (- len 1) (- back 1)))
             ((or (> forward back)
                  (not (eql (elt s forward)
                            (elt s back))))
              (> forward back))))))

這個(gè)版本也可用在列表，但這個(gè)實(shí)現(xiàn)更適合給向量使用。頻繁的對(duì)列表調(diào)用?elt?的代價(jià)是昂貴的，因?yàn)榱斜韮H允許順序存取。而向量允許隨機(jī)存取，從任何元素來(lái)存取每一個(gè)元素都是廉價(jià)的。

許多序列函數(shù)接受一個(gè)或多個(gè)，由下表所列的標(biāo)準(zhǔn)關(guān)鍵字參數(shù)：

一個(gè)接受所有關(guān)鍵字參數(shù)的函數(shù)是?position?，返回序列中一個(gè)元素的位置，未找到元素時(shí)則返回?nil?。我們使用?position?來(lái)演示關(guān)鍵字參數(shù)所扮演的角色。

> (position #\a "fantasia")
1
> (position #\a "fantasia" :start 3 :end 5)
4

第二個(gè)例子我們要找在第四個(gè)與第六個(gè)字符間，第一個(gè)?a?所出現(xiàn)的位置。?:start?關(guān)鍵字參數(shù)是第一個(gè)被考慮的元素位置，缺省是序列的第一個(gè)元素。?:end?關(guān)鍵字參數(shù)，如果有給的話，是第一個(gè)不被考慮的元素位置。

如果我們給入?:from-end?關(guān)鍵字參數(shù)，

> (position #\a "fantasia" :from-end t)
7

我們得到最靠近結(jié)尾的?a?的位置。但位置是像平常那樣計(jì)算；而不是從尾端算回來(lái)的距離。

:key?關(guān)鍵字參數(shù)是序列中每個(gè)元素在被考慮之前，應(yīng)用至元素上的函數(shù)。如果我們說(shuō)，

> (position 'a '((c d) (a b)) :key #'car)
1

那么我們要找的是，元素的?car?部分是符號(hào)?a?的第一個(gè)元素。

:test?關(guān)鍵字參數(shù)接受需要兩個(gè)實(shí)參的函數(shù)，并定義了怎樣是一個(gè)成功的匹配。缺省函數(shù)為?eql?。如果你想要匹配一個(gè)列表，你也許想使用?equal?來(lái)取代：

> (position '(a b) '((a b) (c d)))
NIL
> (position '(a b) '((a b) (c d)) :test #'equal)
0

:test?關(guān)鍵字參數(shù)可以是任何接受兩個(gè)實(shí)參的函數(shù)。舉例來(lái)說(shuō)，給定?<?，我們可以詢問(wèn)第一個(gè)使第一個(gè)參數(shù)比它小的元素位置：

> (position 3 '(1 0 7 5) :test #'<)
2

使用?subseq?與?position?，我們可以寫(xiě)出分開(kāi)序列的函數(shù)。舉例來(lái)說(shuō)，這個(gè)函數(shù)

(defun second-word (str)
  (let ((p1 (+ (position #\  str) 1)))
    (subseq str p1 (position #\  str :start p1))))

返回字符串中第一個(gè)單字空格后的第二個(gè)單字：

> (second-word "Form follows function")
"follows"

要找到滿足謂詞的元素，其中謂詞接受一個(gè)實(shí)參，我們使用?position-if?。它接受一個(gè)函數(shù)與序列，并返回第一個(gè)滿足此函數(shù)的元素：

> (position-if #'oddp '(2 3 4 5))
1

position-if?接受除了?:test?之外的所有關(guān)鍵字參數(shù)。

有許多相似的函數(shù)，如給序列使用的?member?與?member-if?。分別是，?find?（接受全部關(guān)鍵字參數(shù)）與?find-if?（接受除了?:test之外的所有關(guān)鍵字參數(shù)）：

> (find #\a "cat")
#\a

> (find-if #'characterp "ham")
#\h

不同于?member?與?member-if?，它們僅返回要尋找的對(duì)象。

通常一個(gè)?find-if?的調(diào)用，如果解讀為?find?搭配一個(gè)?:key?關(guān)鍵字參數(shù)的話，會(huì)顯得更清楚。舉例來(lái)說(shuō)，表達(dá)式

(find-if #'(lambda (x)
             (eql (car x) 'complete))
         lst)

可以更好的解讀為

(find 'complete lst :key #'car)

函數(shù)?remove?（22 頁(yè)）以及?remove-if?通常都可以用在序列。它們跟?find?與?find-if?是一樣的關(guān)系。另一個(gè)相關(guān)的函數(shù)是remove-duplicates?，僅保留序列中每個(gè)元素的最后一次出現(xiàn)。

> (remove-duplicates "abracadabra")
"cdbra"

這個(gè)函數(shù)接受前表所列的所有關(guān)鍵字參數(shù)。

函數(shù)?reduce?用來(lái)把序列壓縮成一個(gè)值。它至少接受兩個(gè)參數(shù)，一個(gè)函數(shù)與序列。函數(shù)必須是接受兩個(gè)實(shí)參的函數(shù)。在最簡(jiǎn)單的情況下，一開(kāi)始函數(shù)用序列前兩個(gè)元素作為實(shí)參來(lái)調(diào)用，之后接續(xù)的元素作為下次調(diào)用的第二個(gè)實(shí)參，而上次返回的值作為下次調(diào)用的第一個(gè)實(shí)參。最后調(diào)用最終返回的值作為?reduce?整個(gè)函數(shù)的返回值。也就是說(shuō)像是這樣的表達(dá)式：

(reduce #'fn '(a b c d))

等同于

(fn (fn (fn 'a 'b) 'c) 'd)

我們可以使用?reduce?來(lái)擴(kuò)充只接受兩個(gè)參數(shù)的函數(shù)。舉例來(lái)說(shuō)，要得到三個(gè)或多個(gè)列表的交集(intersection)，我們可以：

> (reduce #'intersection '((b r a d 's) (b a d) (c a t)))
(A)

4.5 示例：解析日期 (Example: Parsing Dates)

作為序列操作的示例，本節(jié)演示了如何寫(xiě)程序來(lái)解析日期。我們將編寫(xiě)一個(gè)程序，可以接受像是 “16 Aug 1980” 的字符串，然后返回一個(gè)表示日、月、年的整數(shù)列表。

(defun tokens (str test start)
  (let ((p1 (position-if test str :start start)))
    (if p1
        (let ((p2 (position-if #'(lambda (c)
                                   (not (funcall test c)))
                               str :start p1)))
          (cons (subseq str p1 p2)
                (if p2
                    (tokens str test p2)
                    nil)))
        nil)))

(defun constituent (c)
  (and (graphic-char-p c)
       (not (char= c #\ ))))

圖 4.2 辨別符號(hào) (token)

圖 4.2 里包含了某些在這個(gè)應(yīng)用里所需的通用解析函數(shù)。第一個(gè)函數(shù)?tokens?，用來(lái)從字符串中取出語(yǔ)元 （token）。給定一個(gè)字符串及測(cè)試函數(shù)，滿足測(cè)試函數(shù)的字符組成子字符串，子字符串再組成列表返回。舉例來(lái)說(shuō)，如果測(cè)試函數(shù)是對(duì)字母返回真的?alpha-char-p?函數(shù)，我們得到：

> (tokens "ab12 3cde.f" #'alpha-char-p 0)
("ab" "cde" "f")

所有不滿足此函數(shù)的字符被視為空白 ── 他們是語(yǔ)元的分隔符，但永遠(yuǎn)不是語(yǔ)元的一部分。

函數(shù)?constituent?被定義成用來(lái)作為?tokens?的實(shí)參。

在 Common Lisp 里，圖形字符是我們可見(jiàn)的字符，加上空白字符。所以如果我們用?constituent?作為測(cè)試函數(shù)時(shí)，

> (tokens "ab12 3cde.f gh" #'constituent 0)
("ab12" "3cde.f" "gh")

則語(yǔ)元將會(huì)由空白區(qū)分出來(lái)。

圖 4.3 包含了特別為解析日期打造的函數(shù)。函數(shù)?parse-date?接受一個(gè)特別形式組成的日期，并返回代表這個(gè)日期的整數(shù)列表：

> (parse-date "16 Aug 1980")
(16 8 1980)

(defun parse-date (str)
  (let ((toks (tokens str #'constituent 0)))
    (list (parse-integer (first toks))
          (parse-month (second toks))
          (parse-integer (third toks)))))

(defconstant month-names
  #("jan" "feb" "mar" "apr" "may" "jun"
    "jul" "aug" "sep" "oct" "nov" "dec"))

(defun parse-month (str)
  (let ((p (position str month-names
                         :test #'string-equal)))
    (if p
        (+ p 1)
        nil)))

圖 4.3 解析日期的函數(shù)

parse-date?使用?tokens?來(lái)解析日期字符串，接著調(diào)用?parse-month?及?parse-integer?來(lái)轉(zhuǎn)譯年、月、日。要找到月份，調(diào)用parse-month?，由于使用的是?string-equal?來(lái)匹配月份的名字，所以輸入可以不分大小寫(xiě)。要找到年和日，調(diào)用內(nèi)置的?parse-integer?，?parse-integer?接受一個(gè)字符串并返回對(duì)應(yīng)的整數(shù)。

如果需要自己寫(xiě)程序來(lái)解析整數(shù)，也許可以這么寫(xiě)：

(defun read-integer (str)
  (if (every #'digit-char-p str)
      (let ((accum 0))
        (dotimes (pos (length str))
          (setf accum (+ (* accum 10)
                         (digit-char-p (char str pos)))))
        accum)
    nil))

這個(gè)定義演示了在 Common Lisp 中，字符是如何轉(zhuǎn)成數(shù)字的 ── 函數(shù)?digit-char-p?不僅測(cè)試字符是否為數(shù)字，同時(shí)返回了對(duì)應(yīng)的整數(shù)。

4.6 結(jié)構(gòu) (Structures)

結(jié)構(gòu)可以想成是豪華版的向量。假設(shè)你要寫(xiě)一個(gè)程序來(lái)追蹤長(zhǎng)方體。你可能會(huì)想用三個(gè)向量元素來(lái)表示長(zhǎng)方體：高度、寬度及深度。與其使用原本的?svref?，不如定義像是下面這樣的抽象，程序會(huì)變得更容易閱讀，

(defun block-height (b) (svref b 0))

而結(jié)構(gòu)可以想成是，這些函數(shù)通通都替你定義好了的向量。

要想定義結(jié)構(gòu)，使用?defstruct?。在最簡(jiǎn)單的情況下，只要給出結(jié)構(gòu)及字段的名字便可以了：

(defstruct point
  x
  y)

這里定義了一個(gè)?point?結(jié)構(gòu)，具有兩個(gè)字段?x?與?y?。同時(shí)隱式地定義了?make-point?、?point-p?、?copy-point?、?point-x?及point-y?函數(shù)。

2.3 節(jié)提過(guò)， Lisp 程序可以寫(xiě)出 Lisp 程序。這是目前所見(jiàn)的明顯例子之一。當(dāng)你調(diào)用?defstruct?時(shí)，它自動(dòng)生成了其它幾個(gè)函數(shù)的定義。有了宏以后，你將可以自己來(lái)辦到同樣的事情（如果需要的話，你甚至可以自己寫(xiě)出?defstruct?）。

每一個(gè)?make-point?的調(diào)用，會(huì)返回一個(gè)新的?point?。可以通過(guò)給予對(duì)應(yīng)的關(guān)鍵字參數(shù)，來(lái)指定單一字段的值：

(setf p (make-point :x 0 :y 0))
#S(POINT X 0 Y 0)

存取?point?字段的函數(shù)不僅被定義成可取出數(shù)值，也可以搭配?setf?一起使用。

> (point-x p)
0
> (setf (point-y p) 2)
2
> p
#S(POINT X 0 Y 2)

定義結(jié)構(gòu)也定義了以結(jié)構(gòu)為名的類型。每個(gè)點(diǎn)的類型層級(jí)會(huì)是，類型?point?，接著是類型?structure?，再來(lái)是類型?atom?，最后是t?類型。所以使用?point-p?來(lái)測(cè)試某個(gè)東西是不是一個(gè)點(diǎn)時(shí)，也可以使用通用性的函數(shù)，像是?typep?來(lái)測(cè)試。

> (point-p p)
T
> (typep p 'point)
T

我們可以在本來(lái)的定義中，附上一個(gè)列表，含有字段名及缺省表達(dá)式，來(lái)指定結(jié)構(gòu)字段的缺省值。

(defstruct polemic
  (type (progn
          (format t "What kind of polemic was it? ")
          (read)))
  (effect nil))

如果?make-polemic?調(diào)用沒(méi)有給字段指定初始值，則字段會(huì)被設(shè)成缺省表達(dá)式的值：

> (make-polemic)
What kind of polemic was it? scathing
#S(POLEMIC :TYPE SCATHING :EFFECT NIL)

結(jié)構(gòu)顯示的方式也可以控制，以及結(jié)構(gòu)自動(dòng)產(chǎn)生的存取函數(shù)的字首。以下是做了前述兩件事的?point?定義：

(defstruct (point (:conc-name p)
                  (:print-function print-point))
  (x 0)
  (y 0))

(defun print-point (p stream depth)
  (format stream "#<~A, ~A>" (px p) (py p)))

:conc-name?關(guān)鍵字參數(shù)指定了要放在字段前面的名字，并用這個(gè)名字來(lái)生成存取函數(shù)。預(yù)設(shè)是?point-?；現(xiàn)在變成只有?p?。不使用缺省的方式使代碼的可讀性些微降低了，只有在需要常常用到這些存取函數(shù)時(shí)，你才會(huì)想取個(gè)短點(diǎn)的名字。

:print-function?是在需要顯示結(jié)構(gòu)出來(lái)看時(shí)，指定用來(lái)打印結(jié)構(gòu)的函數(shù) ── 需要顯示的情況比如，要在頂層顯示時(shí)。這個(gè)函數(shù)需要接受三個(gè)實(shí)參：要被印出的結(jié)構(gòu)，在哪里被印出，第三個(gè)參數(shù)通?？梢院雎浴?[2]?我們會(huì)在 7.1 節(jié)討論流（stream）?，F(xiàn)在來(lái)說(shuō)，只要知道流可以作為參數(shù)傳給?format?就好了。

函數(shù)?print-point?會(huì)用縮寫(xiě)的形式來(lái)顯示點(diǎn)：

> (make-point)
#<0,0>

4.7 示例：二叉搜索樹(shù) (Example: Binary Search Tree)

由于?sort?本身系統(tǒng)就有了，極少需要在 Common Lisp 里編寫(xiě)排序程序。本節(jié)將演示如何解決一個(gè)與此相關(guān)的問(wèn)題，這個(gè)問(wèn)題尚未有現(xiàn)成的解決方案：維護(hù)一個(gè)已排序的對(duì)象集合。本節(jié)的代碼會(huì)把對(duì)象存在二叉搜索樹(shù)里（?binary search tree?）或稱作 BST。當(dāng)二叉搜索樹(shù)平衡時(shí)，允許我們可以在與時(shí)間成?log?n?比例的時(shí)間內(nèi)，來(lái)尋找、添加或是刪除元素，其中?n?是集合的大小。

第三章演示過(guò)列表可以用來(lái)表示集合（sets）與映射（mappings）。但當(dāng)列表的長(zhǎng)度大幅上升時(shí)（或是 10 個(gè)元素），使用哈希表的速度比較快。你通過(guò)調(diào)用?make-hash-table?來(lái)構(gòu)造一個(gè)哈希表，它不需要傳入?yún)?shù)：

> (setf ht (make-hash-table))
#<Hash-Table BF0A96>

和函數(shù)一樣，哈希表總是用?#<...>?的形式來(lái)顯示。

一個(gè)哈希表，與一個(gè)關(guān)聯(lián)列表類似，是一種表達(dá)對(duì)應(yīng)關(guān)系的方式。要取出與給定鍵值有關(guān)的數(shù)值，我們調(diào)用?gethash?并傳入一個(gè)鍵值與哈希表。預(yù)設(shè)情況下，如果沒(méi)有與這個(gè)鍵值相關(guān)的數(shù)值，?gethash?會(huì)返回?nil?。

> (gethash 'color ht)
NIL
NIL

在這里我們首次看到 Common Lisp 最突出的特色之一：一個(gè)表達(dá)式竟然可以返回多個(gè)數(shù)值。函數(shù)?gethash?返回兩個(gè)數(shù)值。第一個(gè)值是與鍵值有關(guān)的數(shù)值，第二個(gè)值說(shuō)明了哈希表是否含有任何用此鍵值來(lái)儲(chǔ)存的數(shù)值。由于第二個(gè)值是?nil?，我們知道第一個(gè)?nil是缺省的返回值，而不是因?yàn)?nil?是與?color?有關(guān)的數(shù)值。

大部分的實(shí)現(xiàn)會(huì)在頂層顯示一個(gè)函數(shù)調(diào)用的所有返回值，但僅期待一個(gè)返回值的代碼，只會(huì)收到第一個(gè)返回值。 5.5 節(jié)會(huì)說(shuō)明，代碼如何接收多個(gè)返回值。

要把數(shù)值與鍵值作關(guān)聯(lián)，使用?gethash?搭配?setf?：

> (setf (gethash 'color ht) 'red)
RED

現(xiàn)在如果我們?cè)俅握{(diào)用?gethash?，我們會(huì)得到我們剛插入的值：

> (gethash 'color ht)
RED
T

第二個(gè)返回值證明，我們?nèi)〉昧艘粋€(gè)真正儲(chǔ)存的對(duì)象，而不是預(yù)設(shè)值。

存在哈希表的對(duì)象或鍵值可以是任何類型。舉例來(lái)說(shuō)，如果我們要保留函數(shù)的某種訊息，我們可以使用哈希表，用函數(shù)作為鍵值，字符串作為詞條（entry）：

> (setf bugs (make-hash-table))
#<Hash-Table BF4C36>
> (push "Doesn't take keyword arguments."
        (gethash #'our-member bugs))
("Doesn't take keyword arguments.")

由于?gethash?缺省返回?nil?，而?push?是?setf?的縮寫(xiě)，可以輕松的給哈希表新添一個(gè)詞條。 （有困擾的?our-member?定義在 16 頁(yè)。）

可以用哈希表來(lái)取代用列表表示集合。當(dāng)集合變大時(shí)，哈希表的查詢與移除會(huì)來(lái)得比較快。要新增一個(gè)成員到用哈希表所表示的集合，把?gethash?用?setf?設(shè)成?t?：

> (setf fruit (make-hash-table))
#<Hash-Table BFDE76>
> (setf (gethash 'apricot fruit) t)
T

然后要測(cè)試是否為成員，你只要調(diào)用：

> (gethash 'apricot fruit)
T
T

由于?gethash?缺省返回真，一個(gè)新創(chuàng)的哈希表，會(huì)很方便地是一個(gè)空集合。

要從集合中移除一個(gè)對(duì)象，你可以調(diào)用?remhash?，它從一個(gè)哈希表中移除一個(gè)詞條：

> (remhash 'apricot fruit)
T

返回值說(shuō)明了是否有詞條被移除；在這個(gè)情況里，有。

哈希表有一個(gè)迭代函數(shù)：?maphash?，它接受兩個(gè)實(shí)參，接受兩個(gè)參數(shù)的函數(shù)以及哈希表。該函數(shù)會(huì)被每個(gè)鍵值對(duì)調(diào)用，沒(méi)有特定的順序：

> (setf (gethash 'shape ht) 'spherical
        (gethash 'size ht) 'giant)
GIANT

> (maphash #'(lambda (k v)
               (format t "~A = ~A~%" k v))
           ht)
SHAPE = SPHERICAL
SIZE = GIANT
COLOR = RED
NIL

maphash?總是返回?nil?，但你可以通過(guò)傳入一個(gè)會(huì)累積數(shù)值的函數(shù)，把哈希表的詞條存在列表里。

哈希表可以容納任何數(shù)量的元素，但當(dāng)哈希表空間用完時(shí)，它們會(huì)被擴(kuò)張。如果你想要確保一個(gè)哈希表，從特定數(shù)量的元素空間大小開(kāi)始時(shí)，可以給?make-hash-table?一個(gè)選擇性的?:size?關(guān)鍵字參數(shù)。做這件事情有兩個(gè)理由：因?yàn)槟阒拦１頃?huì)變得很大，你想要避免擴(kuò)張它；或是因?yàn)槟阒拦１頃?huì)是很小，你不想要浪費(fèi)內(nèi)存。?:size?參數(shù)不僅指定了哈希表的空間，也指定了元素的數(shù)量。平均來(lái)說(shuō)，在被擴(kuò)張前所能夠容納的數(shù)量。所以

(make-hash-table?:size?5)

會(huì)返回一個(gè)預(yù)期存放五個(gè)元素的哈希表。

和任何牽涉到查詢的結(jié)構(gòu)一樣，哈希表一定有某種比較鍵值的概念。預(yù)設(shè)是使用?eql?，但你可以提供一個(gè)額外的關(guān)鍵字參數(shù)?:test來(lái)告訴哈希表要使用?eq?，?equal?，還是?equalp?：

> (setf writers (make-hash-table :test #'equal))
#<Hash-Table C005E6>
> (setf (gethash '(ralph waldo emerson) writers) t)
T

這是一個(gè)讓哈希表變得有效率的取舍之一。有了列表，我們可以指定?member?為判斷相等性的謂詞。有了哈希表，我們可以預(yù)先決定，并在哈希表構(gòu)造時(shí)指定它。

大多數(shù) Lisp 編程的取舍（或是生活，就此而論）都有這種特質(zhì)。起初你想要事情進(jìn)行得流暢，甚至賠上效率的代價(jià)。之后當(dāng)代碼變得沉重時(shí)，你犧牲了彈性來(lái)?yè)Q取速度。

Chapter 4 總結(jié) (Summary)

1. Common Lisp 支持至少 7 個(gè)維度的數(shù)組。一維數(shù)組稱為向量。
2. 字符串是字符的向量。字符本身就是對(duì)象。
3. 序列包括了向量與列表。許多序列函數(shù)都接受標(biāo)準(zhǔn)的關(guān)鍵字參數(shù)。
4. 處理字符串的函數(shù)非常多，所以用 Lisp 來(lái)解析字符串是小菜一碟。
5. 調(diào)用?defstruct?定義了一個(gè)帶有命名字段的結(jié)構(gòu)。它是一個(gè)程序能寫(xiě)出程序的好例子。
6. 二叉搜索樹(shù)見(jiàn)長(zhǎng)于維護(hù)一個(gè)已排序的對(duì)象集合。
7. 哈希表提供了一個(gè)更有效率的方式來(lái)表示集合與映射 (mappings)。

Chapter 4 習(xí)題 (Exercises)

1. 定義一個(gè)函數(shù)，接受一個(gè)平方數(shù)組（square array，一個(gè)相同維度的數(shù)組?(n?n)?)，并將它順時(shí)針轉(zhuǎn) 90 度。

> (quarter-turn #2A((a b) (c d)))
#2A((C A) (D B))

你會(huì)需要用到 361 頁(yè)的?array-dimensions?。

1. 閱讀 368 頁(yè)的?reduce?說(shuō)明，然后用它來(lái)定義：

(a) copy-list
(b) reverse（針對(duì)列表）

1. 定義一個(gè)結(jié)構(gòu)來(lái)表示一棵樹(shù)，其中每個(gè)節(jié)點(diǎn)包含某些數(shù)據(jù)及三個(gè)小孩。定義：

(a) 一個(gè)函數(shù)來(lái)復(fù)制這樣的樹(shù)（復(fù)制完的節(jié)點(diǎn)與本來(lái)的節(jié)點(diǎn)是不相等（ `eql` ）的）
(b) 一個(gè)函數(shù)，接受一個(gè)對(duì)象與這樣的樹(shù)，如果對(duì)象與樹(shù)中各節(jié)點(diǎn)的其中一個(gè)字段相等時(shí)，返回真。

1. 定義一個(gè)函數(shù)，接受一棵二叉搜索樹(shù)，并返回由此樹(shù)元素所組成的，一個(gè)由大至小排序的列表。
2. 定義?bst-adjoin?。這個(gè)函數(shù)應(yīng)與?bst-insert?接受相同的參數(shù)，但應(yīng)該只在對(duì)象不等于任何樹(shù)中對(duì)象時(shí)將其插入。

勘誤:?bst-adjoin?的功能與?bst-insert?一模一樣。

1. 任何哈希表的內(nèi)容可以由關(guān)聯(lián)列表（assoc-list）來(lái)描述，其中列表的元素是?(k?.?v)?的形式，對(duì)應(yīng)到哈希表中的每一個(gè)鍵值對(duì)。定義一個(gè)函數(shù)：

(a) 接受一個(gè)關(guān)聯(lián)列表，并返回一個(gè)對(duì)應(yīng)的哈希表。
(b) 接受一個(gè)哈希表，并返回一個(gè)對(duì)應(yīng)的關(guān)聯(lián)列表。

腳注

[1] | 一個(gè)簡(jiǎn)單數(shù)組大小是不可調(diào)整、元素也不可替換的，并不含有填充指針（fill-pointer）。數(shù)組缺省是簡(jiǎn)單的。簡(jiǎn)單向量是個(gè)一維的簡(jiǎn)單數(shù)組，可以含有任何類型的元素。

[2] | 在 ANSI Common Lisp 里，你可以給一個(gè)?:print-object?的關(guān)鍵字參數(shù)來(lái)取代，它只需要兩個(gè)實(shí)參。也有一個(gè)宏叫做print-unreadable-object?，能用則用，可以用?#<...>?的語(yǔ)法來(lái)顯示對(duì)象。