UP | HOME

哈希表

Table of Contents

本章中，会讲解用于表示 数据关联 的 关联表 和 哈希表 。关联的数据是由 键 和 值 组成的 序对 ， 值由键唯一确定的 。表1显示了书和作者构成的配对：

Table 1: 作者和书
Author Book
P. Graham On Lisp
P. Graham ANSI Common Lisp
E. S. Raymond The Cathedral and the Bazaar
K. Dybvig The Scheme Programming Language
F. P. Brooks, Jr. The Mythical Man-Month
L. Carroll Alice's Adventures in Wonderland
L. Carroll Through the Looking-Glass, and What Alice Found There 
  书籍可以确定作者，反之由作者确定书籍则不可，这是因为一个作者可能会写很多本书

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

MIT-Scheme实现了哈希表。如果你喜欢的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)))
(assq 'hi wc) ; => (hi .3) 
(assq 'you wc) ; => (you . 8) 
(assq 'i wc) ; => #f 

(define n '((1 2 3) (4 5 6) (7 8 9)))
(assv 1 n) ; => ( 1 2 3) 
(assv 8 n) ; => #f

哈希表

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

  • 创建哈希表， 初始大小 可以 选择性指定
    • (make-eq-hash-table size) : 使用 eq? 比较键的值
    • (make-eqv-hash-table size) : 使用 eqv? 比较键的值
    • (make-equal-hash-table size) : 使用 equal? 比较键的值
    • (make-string-hash-table size) : 使用 string=? 比较键的值
    由于只比较键的地址，所以 eq-hash-table 是最快的

    由于键是序列，所以 equal-hash-table 和 string-hash-table 比较慢
  • (hash-table/put! hash-table key datum) : 将 hash-table 中 key 对应的 值 设为 datum
  • (hash-table/get hash-table key default) : 返回 hash-table 中的 key 对应的值
    • 如果 key 不存在于 hash-table 中，返回 default
  • (hash-table->alist hash-table): 将 hash-table 转换为 关联表

实例：生成密码

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

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

程序由两部分构成：

  1. stat-spell.scm : 用于创建连续字符出现频率的数据
  2. make-pw.scm : 用于基于这个数据创建密码

stat-spell

(skip-char? c) : 如果 c 不是图像字符 或者 c 是 #\: , #\; , #\' , or #\" ，就返回 #t 。 读取文本时，这些字符会被跳过 

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

(ss-make-alist c alist) : 有两个参数

  • alist : 字符频率 的 关联表
  • c: 字符
  • 如果 c 在 alist 中，在 序对的cdr 部分增加 1
  • 如果不在，返回 (cons (cons c 1) alist)

这个函数使用了 set-cdr! 

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

(ss-make-dat filename) :

  • 从名为 filename 的文件中 读取字符
  • 并使用跟随 字符频率的关联表 来 关联 这些读出的 字符
  • 结果以 关联表 形式存储在文件 stat-spell.dat
    • 它在哈希表中更新了频率的关联表
    • 存储在 stat-spell.dat 的最终数据是一个 关联表的关联表
(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<? (car x) (car y))))))
          (if (pair? alst)
              (begin
                (write (car alst))
                (newline)
                (loop (cdr alst)))))
        (display "))")
        (newline)))))

make-pw

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

  1. 基于 频率数据 创建由 9 到 13个随机字符组成字符串表。字符 #\Space 被添加在 表结尾
  2. 添加一个 00 到 99 之间的 随机数 在随机选取的字符串 表结尾
  3. 随机地将 #\Space 转换为 #- , #_ , #\/, #\Space, #., 或者 #\
  4. 随机地将 30%的字母 字符变为 大写

(alist->hash al mode) : 转换一个关联表到哈希表 

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

(pw-random-select vec) : 随机从一个向量表里获得一个元素 

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

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

(random00) : 生成一个 00~99 的随机数 

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

(occasional-upcase c)：把 30%的字符变成大写 

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

(pw-enhance ls) ：加强密码的安全性

  • 替换 \#Space 为特殊字符
  • 30%几率把字符替换为大写
(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)))))

(random-following alist) : 根据频率从字符关联表随机获得一个字符 

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

(make-pw h n) : 创建一个 n + 3 长度的密码，最后2位是随机数字 

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

(pw-candidates) : 随机生成10个 12～15 个字符的密码 

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

测试代码： 

(compile-file "stat-spell.scm")
(load "stat-spell")
;;; creating spelling data according to sicp_foreword.txt
(ss-make-dat "sicp_foreword.txt")

(compile-file "make-pw.scm")
(load "make-pw")

;;; making ten passwords using the spelling data.
(pw-candidates)

Next：结构体

Previous：符号

Home：目录