关联表和哈希表

本章中，我会讲解用于表示数据关联的关联表和哈希表。关联的数据是由键和值组成的序对，值由键唯一确定的。

表1显示了书和作者构成的配对。书籍可以确定作者，反之由作者确定书籍则不可，这是因为一个作者可能会写很多本书。

表1中，由于 P. Graham 和 L.Carroll 分别写了两本书，因此他们的书无法被作者的名字唯一确定。

R5RS 定义了关联表，因此它在所有 Scheme 实现中都可用。但是使用关联表搜索速度较慢（O(n) 的时间复杂度）。

使用哈希表在速度方面更好一些（O(1) 的时间复杂度），但是哈希表并未在 R5RS 中定义而是依赖于相关实现。MIT-Scheme 实现了哈希表。

关联表

关联表是一个由序对组成的表，它是一个用于表达关联的基本数据类型。符号，字符，和数字常被作为键使用，因为它们可以使用诸如eq?或者eqv?的快速比较函数被比较。在作为键被使用前，字符串应该被转换为符号，从而获得更好的性能。

下面是一个关联表的例子。关联表应该要么由点序对要么由普通表组成。

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

函数assq，assv，和assoc从关联表中搜寻一个项。这些函数从开始一步步搜索关联表。如果它们找到序对的car等于给定的key，就返回该序对。如果找不到函数返回#f。这些函数分别使用eq?，eqv?，和equal?比较键，这意味着assq最快，assoc最慢。这表示作为键的话，字符串，向量和表应该转化为符号或者数字（如果可能的话）以提高性能。

一般来说，哈希表在大量数据中搜索表现得更好一些。

下面展示在关联表中进行搜索的例子。

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

哈希表

哈希表是一种数据类型，它使用哈希函数将键转化为整数，并将值存储在由该整数所指示的位置。当表足够稀疏时，搜索，插入，更新都能以O(1)完成。下面展示了MIT-Scheme里哈希表的一些基本函数。

这些函数创建哈希表。这些函数分别使用eq?，eqv?，equal?，和string=?比较键的值。哈希表的初始大小（size）可以选择性指定（optional）。由于只比较键的地址，所以eq-hash-table是最快的。由于键是序列，所以equal-hash-table和string-hash-table比较慢。

生成密码

让我们写一个密码创建程序作为关联表和哈希表的例子。

从字典里得到的密码很容易被破解，但另一方面，完全随机的密码又很难记忆和输入。程序使用无规则的拼写创建10个密码。密码应该尽可能频繁更改，但是我懒于自己创建密码。使用这个程序，我可以简单地改变密码。

程序由两部分构成。一部分用于创建连续字符出现频率的数据（stat-spell.scm），另一个用于基于这个数据创建密码（make-pw.scm）。

stat-spell.scm

这个程序可以阅读英语句子，数据存在哈希表里，并转换为关联表输出到一个文件（stat-spell.data）。[代码1]显示了源代码。

 ;;; make an alist of probable spelling from a given English text

 (define (skip-char? c)
   (or (not (char-graphic? c)) (memv c '(#\: #\; #\' #\" #\`))))

 (define (ss-make-alist c alist)
   (let ((p (assv c alist)))
     (if p
         (begin
          (set-cdr! p (1+ (cdr p)))
          alist)
       (cons (cons c 1) alist))))

 (define (ss-make-dat filename)
   (let ((char-hash (make-eqv-hash-table)))
     (with-input-from-file filename
       (lambda ()
     (let loop ((c #\Space))
       (let ((c1 (read-char)))
                  (if (not (eof-object? c1))
                      (if (skip-char? c1)
                          (loop c)
                          (let ((c1 (char-downcase c1)))
                (hash-table/put! char-hash c
                         (ss-make-alist c1 (hash-table/get char-hash c '())))
                (loop c1))))))))
     (with-output-to-file "stat-spell.dat"
       (lambda ()
     (display "(define *stat-spell* \'(")
     (newline)
     (let loop ((alst (sort (hash-table->alist char-hash) 
                    (lambda (x y) (char       (if (pair? alst)
           (begin
         (write (car alst))
         (newline)
         (loop (cdr alst)))))
         (display "))")
         (newline)))))

(skip-char? c)

如果c不是图像字符或者c是 #\:, #\;, #\’, or #\”，就返回#t。读取文本时，这些字符会被跳过。

(ss-make-alist c alist)

有两个参数；字符的频率的关联表（alist）和字符（c）。如果c在alist中，在序对的cdr部分增加一。如果不在，返回 (cons (cons c 1) alist)。这个函数使用了set-cdr!。

(ss-make-dat filename)

从名为filename的文件中读取字符，并使用跟随字符的频率的关联表来关联这些读出的字符。结果以关联表形式存储在文件stat-spell.dat_blank。在34和35行，它在哈希表中更新了频率的关联表。存储在 stat-spell.dat 的最终数据是一个关联表的关联表。例如：

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

表示 #\y, #\a, #\o, #\e, 和 #\i 跟随 #\v 之后出现的次数分别是1, 3, 7, 51, 和15次。

make-pw.scm

基于 stat-spell.dat 创建十个密码。过程如下：

 ;;; make password from the alist of probable spelling

 (load "stat-spell.dat") ; *stat-spell* (alist for following characters) is in.

 (define (alist->hash al mode)
   (let ((h (case mode
              ((eq) (make-eq-hash-table))
              ((eqv) (make-eqv-hash-table))
              ((equal) (make-equal-hash-table))
              ((string) (make-string-hash-table)))))
     (for-each (lambda (p)
                 (hash-table/put! h (car p) (cdr p)))
               al)
     h))

 (define *stat-spell-hash* (alist->hash *stat-spell* 'eqv))

 (define (pw-random-select vec)
   (vector-ref vec (random (vector-length vec))))

 (define (random00)
   (let loop ((i 0) (acc '()))
     (if (= i 2)
         (list->string acc)
       (loop (1+ i) (cons (pw-random-select '#(#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9)) acc)))))

 (define (occasional-upcase c)
   (if (< (random 10) 3)
       (char-upcase c)
     c))

 (define (pw-enhance ls)
   (list->string
    (map (lambda (c)
           (cond
            ((char=? c #\Space)
             (pw-random-select  '#(#\- #\_ #\/  #\Space  #\. #\, #\@ #\? #\( #\))))
            ((char-alphabetic? c)
             (occasional-upcase c))
            (else c)))
         (cdr (reverse! ls)))))


 (define (random-following alist)
   (let ((n (random (apply + (map cdr alist)))))
     (let loop ((j 0) (alist alist))
       (if (pair? alist)
       (let* ((pair (car alist))
          (k (+ j (cdr pair))))
         (if (> k n)
         (car pair)
         (loop k (cdr alist))))))))

 (define (make-pw h n)
   (let loop ((i 0) (c #\Space) (acc '()))
     (if (= i n)
         (string-append
          (pw-enhance (cons #\Space (cons c acc)))
          (random00))
       (loop (1+ i)
         (random-following (hash-table/get h c '((#\Space . 1))))
         (cons c acc)))))

 (define (pw-candidates)
   (let loop ((i 0))
     (if (< i 10)
         (begin
          (display i)
          (display ": ")
          (write (make-pw *stat-spell-hash* (+ 9 (random 4))))
          (newline)
          (loop (1+ i)))
       'done)))