第十三章 關(guān)聯(lián)表和哈希表

13.1 簡(jiǎn)介

本章中，我會(huì)講解用于表示數(shù)據(jù)關(guān)聯(lián)的關(guān)聯(lián)表和哈希表。關(guān)聯(lián)的數(shù)據(jù)是由鍵和值組成的序?qū)Γ涤涉I唯一確定的。表1顯示了書(shū)和作者構(gòu)成的配對(duì)。書(shū)籍可以確定作者，反之由作者確定書(shū)籍則不可，這是因?yàn)橐粋€(gè)作者可能會(huì)寫(xiě)很多本書(shū)。表1中，由于 P. Graham 和 L.Carroll 分別寫(xiě)了兩本書(shū)，因此他們的書(shū)無(wú)法被作者的名字唯一確定。

表1：作者和書(shū)

R5RS 定義了關(guān)聯(lián)表，因此它在所有 Scheme 實(shí)現(xiàn)中都可用。但是使用關(guān)聯(lián)表搜索速度較慢（O(n) 的時(shí)間復(fù)雜度）。使用哈希表在速度方面更好一些（O(1) 的時(shí)間復(fù)雜度），但是哈希表并未在 R5RS 中定義而是依賴(lài)于相關(guān)實(shí)現(xiàn)。MIT-Scheme 實(shí)現(xiàn)了哈希表。

關(guān)聯(lián)表

關(guān)聯(lián)表是一個(gè)由序?qū)M成的表，它是一個(gè)用于表達(dá)關(guān)聯(lián)的基本數(shù)據(jù)類(lèi)型。符號(hào)，字符，和數(shù)字常被作為鍵使用，因?yàn)樗鼈兛梢允褂弥T如eq?或者eqv?的快速比較函數(shù)被比較。在作為鍵被使用前，字符串應(yīng)該被轉(zhuǎn)換為符號(hào)，從而獲得更好的性能。

下面是一個(gè)關(guān)聯(lián)表的例子。關(guān)聯(lián)表應(yīng)該要么由點(diǎn)序?qū)σ从善胀ū斫M成。

'((hi . 3) (everybody . 5) (nice . 3) (to . 10) (meet . 4) (you . 8))
'((1 2 3) (4 5 6) (7 8 9))

函數(shù)assq，assv，和assoc從關(guān)聯(lián)表中搜尋一個(gè)項(xiàng)。這些函數(shù)從開(kāi)始一步步搜索關(guān)聯(lián)表。如果它們找到序?qū)Φ腸ar等于給定的key，就返回該序?qū)?。如果找不到函?shù)返回#f。這些函數(shù)分別使用eq?，eqv?，和equal?比較鍵，這意味著assq最快，assoc最慢。這表示作為鍵的話(huà)，字符串，向量和表應(yīng)該轉(zhuǎn)化為符號(hào)或者數(shù)字（如果可能的話(huà)）以提高性能。

一般來(lái)說(shuō)，哈希表在大量數(shù)據(jù)中搜索表現(xiàn)得更好一些。

下面展示在關(guān)聯(lián)表中進(jìn)行搜索的例子。

(define wc '((hi . 3) (everybody . 5) (nice . 3) (to . 10) (meet . 4) (you . 8)))
? wc
(assq 'hi wc)
?  (hi . 3)
(assq 'you wc)
?  (you . 8)
(assq 'i wc)
?  ()
(define n '((1 2 3) (4 5 6) (7 8 9)))
?  n
(assv 1 n)
?  (1 2 3)
(assv 8 n)
?  ()

哈希表

哈希表是一種數(shù)據(jù)類(lèi)型，它使用哈希函數(shù)將鍵轉(zhuǎn)化為整數(shù)，并將值存儲(chǔ)在由該整數(shù)所指示的位置。當(dāng)表足夠稀疏時(shí)，搜索，插入，更新都能以O(shè)(1)完成。下面展示了MIT-Scheme里哈希表的一些基本函數(shù)。

(make-eq-hash-table size),

(make-eqv-hash-table size),

(make-equal-hash-table size),

(make-string-hash-table size)

這些函數(shù)創(chuàng)建哈希表。這些函數(shù)分別使用eq?，eqv?，equal?，和string=?比較鍵的值。哈希表的初始大?。╯ize）可以選擇性指定（optional）。由于只比較鍵的地址，所以eq-hash-table是最快的。由于鍵是序列，所以equal-hash-table和string-hash-table比較慢。

(hash-table/put! hash-table key datum)

將hash-table中key對(duì)應(yīng)的值設(shè)為datum。

(hash-table/get hash-table key default)

返回hash-table中的key對(duì)應(yīng)的值。如果key不存在于hash-table中，返回default。

(hash-table->alist hash-table)

將hash-table轉(zhuǎn)換為關(guān)聯(lián)表。

生成密碼

讓我們寫(xiě)一個(gè)密碼創(chuàng)建程序作為關(guān)聯(lián)表和哈希表的例子。

從字典里得到的密碼很容易被破解，但另一方面，完全隨機(jī)的密碼又很難記憶和輸入。程序使用無(wú)規(guī)則的拼寫(xiě)創(chuàng)建10個(gè)密碼。密碼應(yīng)該盡可能頻繁更改，但是我懶于自己創(chuàng)建密碼。使用這個(gè)程序，我可以簡(jiǎn)單地改變密碼。

程序由兩部分構(gòu)成。一部分用于創(chuàng)建連續(xù)字符出現(xiàn)頻率的數(shù)據(jù)（stat-spell.scm），另一個(gè)用于基于這個(gè)數(shù)據(jù)創(chuàng)建密碼（make-pw.scm）。

stat-spell.scm

這個(gè)程序可以閱讀英語(yǔ)句子，數(shù)據(jù)存在哈希表里，并轉(zhuǎn)換為關(guān)聯(lián)表輸出到一個(gè)文件（stat-spell.data）。[代碼1]顯示了源代碼。

[代碼1]

01:     ;;; make an alist of probable spelling from a given English text
02:     
03:     (define (skip-char? c)
04:       (or (not (char-graphic? c)) (memv c '(#\: #\; #\' #\" #\`))))
05:     
06:     (define (ss-make-alist c alist)
07:       (let ((p (assv c alist)))
08:         (if p
09:             (begin
10:              (set-cdr! p (1+ (cdr p)))
11:              alist)
12:           (cons (cons c 1) alist))))
13:     
14:     (define (ss-make-dat filename)
15:       (let ((char-hash (make-eqv-hash-table)))
16:         (with-input-from-file filename
17:           (lambda ()
18:         (let loop ((c #\Space))
19:           (let ((c1 (read-char)))
20:                      (if (not (eof-object? c1))
21:                          (if (skip-char? c1)
22:                              (loop c)
23:                              (let ((c1 (char-downcase c1)))
24:                    (hash-table/put! char-hash c
25:                             (ss-make-alist c1 (hash-table/get char-hash c '())))
26:                    (loop c1))))))))
27:         (with-output-to-file "stat-spell.dat"
28:           (lambda ()
29:         (display "(define *stat-spell* \'(")
30:         (newline)
31:         (let loop ((alst (sort (hash-table->alist char-hash) 
32:                        (lambda (x y) (char33:           (if (pair? alst)
34:               (begin
35:             (write (car alst))
36:             (newline)
37:             (loop (cdr alst)))))
38:             (display "))")
39:             (newline)))))

(skip-char? c)

如果c不是圖像字符或者c是 #\:, #\;, #\’, or #\”，就返回#t。讀取文本時(shí)，這些字符會(huì)被跳過(guò)。

(ss-make-alist c alist)

有兩個(gè)參數(shù)；字符的頻率的關(guān)聯(lián)表（alist）和字符（c）。如果c在alist中，在序?qū)Φ腸dr部分增加一。如果不在，返回 (cons (cons c 1) alist)。這個(gè)函數(shù)使用了set-cdr!。

(ss-make-dat filename)

從名為filename的文件中讀取字符，并使用跟隨字符的頻率的關(guān)聯(lián)表來(lái)關(guān)聯(lián)這些讀出的字符。結(jié)果以關(guān)聯(lián)表形式存儲(chǔ)在文件stat-spell.dat_blank。在34和35行，它在哈希表中更新了頻率的關(guān)聯(lián)表。存儲(chǔ)在 stat-spell.dat 的最終數(shù)據(jù)是一個(gè)關(guān)聯(lián)表的關(guān)聯(lián)表。例如：

(#\v (#\y . 1) (#\a . 3) (#\o . 7) (#\e . 51) (#\i . 15))

表示 #\y, #\a, #\o, #\e, 和 #\i 跟隨 #\v 之后出現(xiàn)的次數(shù)分別是1, 3, 7, 51, 和15次。

make-pw.scm

基于 stat-spell.dat 創(chuàng)建十個(gè)密碼。過(guò)程如下：

1. 基于頻率數(shù)據(jù)創(chuàng)建由9到13個(gè)隨機(jī)字符組成字符串表。字符 #\Space 被添加在表結(jié)尾。
2. 添加一個(gè)00到99之間的隨機(jī)數(shù)在隨機(jī)選取的字符串表的結(jié)尾。
3. 隨機(jī)地將 #\Space 轉(zhuǎn)換為 #-, #_, #\/, #\Space, #., 或者 #\,。
4. 隨機(jī)地將30%的字母字符變?yōu)榇髮?xiě)。

01:     ;;; make password from the alist of probable spelling
02:     
03:     (load "stat-spell.dat") ; *stat-spell* (alist for following characters) is in.
04:     
05:     (define (alist->hash al mode)
06:       (let ((h (case mode
07:                  ((eq) (make-eq-hash-table))
08:                  ((eqv) (make-eqv-hash-table))
09:                  ((equal) (make-equal-hash-table))
10:                  ((string) (make-string-hash-table)))))
11:         (for-each (lambda (p)
12:                     (hash-table/put! h (car p) (cdr p)))
13:                   al)
14:         h))
15:     
16:     (define *stat-spell-hash* (alist->hash *stat-spell* 'eqv))
17:     
18:     (define (pw-random-select vec)
19:       (vector-ref vec (random (vector-length vec))))
20:     
21:     (define (random00)
22:       (let loop ((i 0) (acc '()))
23:         (if (= i 2)
24:             (list->string acc)
25:           (loop (1+ i) (cons (pw-random-select '#(#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9)) acc)))))
26:     
27:     (define (occasional-upcase c)
28:       (if (< (random 10) 3)
29:           (char-upcase c)
30:         c))
31:     
32:     (define (pw-enhance ls)
33:       (list->string
34:        (map (lambda (c)
35:               (cond
36:                ((char=? c #\Space)
37:                 (pw-random-select  '#(#\- #\_ #\/  #\Space  #\. #\, #\@ #\? #\( #\))))
38:                ((char-alphabetic? c)
39:                 (occasional-upcase c))
40:                (else c)))
41:             (cdr (reverse! ls)))))
42:         
43:     
44:     (define (random-following alist)
45:       (let ((n (random (apply + (map cdr alist)))))
46:         (let loop ((j 0) (alist alist))
47:           (if (pair? alist)
48:           (let* ((pair (car alist))
49:              (k (+ j (cdr pair))))
50:             (if (> k n)
51:             (car pair)
52:             (loop k (cdr alist))))))))
53:     
54:     (define (make-pw h n)
55:       (let loop ((i 0) (c #\Space) (acc '()))
56:         (if (= i n)
57:             (string-append
58:              (pw-enhance (cons #\Space (cons c acc)))
59:              (random00))
60:           (loop (1+ i)
61:             (random-following (hash-table/get h c '((#\Space . 1))))
62:             (cons c acc)))))
63:         
64:     (define (pw-candidates)
65:       (let loop ((i 0))
66:         (if (< i 10)
67:             (begin
68:              (display i)
69:              (display ": ")
70:              (write (make-pw *stat-spell-hash* (+ 9 (random 4))))
71:              (newline)
72:              (loop (1+ i)))
73:           'done)))