4.8 哈希表 (Hash Table)

第三章演示过列表可以用来表示集合（sets）与映射（mappings）。但当列表的长度大幅上升时（或是 10 个元素），使用哈希表的速度比较快。你通过调用 make-hash-table 来构造一个哈希表，它不需要传入参数：

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

和函数一样，哈希表总是用 #<...> 的形式来显示。

一个哈希表，与一个关联列表类似，是一种表达对应关系的方式。要取出与给定键值有关的数值，我们调用 gethash 并传入一个键值与哈希表。预设情况下，如果没有与这个键值相关的数值， gethash 会返回 nil 。

  1. > (gethash 'color ht)
  2. NIL
  3. NIL

在这里我们首次看到 Common Lisp 最突出的特色之一：一个表达式竟然可以返回多个数值。函数 gethash 返回两个数值。第一个值是与键值有关的数值，第二个值说明了哈希表是否含有任何用此键值来储存的数值。由于第二个值是 nil ，我们知道第一个 nil 是缺省的返回值，而不是因为 nil 是与 color 有关的数值。

大部分的实现会在顶层显示一个函数调用的所有返回值，但仅期待一个返回值的代码，只会收到第一个返回值。 5.5 节会说明，代码如何接收多个返回值。

要把数值与键值作关联，使用 gethash 搭配 setf ：

  1. > (setf (gethash 'color ht) 'red)
  2. RED

现在如果我们再次调用 gethash ，我们会得到我们刚插入的值：

  1. > (gethash 'color ht)
  2. RED
  3. T

第二个返回值证明，我们取得了一个真正储存的对象，而不是预设值。

存在哈希表的对象或键值可以是任何类型。举例来说，如果我们要保留函数的某种讯息，我们可以使用哈希表，用函数作为键值，字符串作为词条（entry）：

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

由于 gethash 缺省返回 nil ，而 push 是 setf 的缩写，可以轻松的给哈希表新添一个词条。 （有困扰的 our-member 定义在 16 页。）

可以用哈希表来取代用列表表示集合。当集合变大时，哈希表的查询与移除会来得比较快。要新增一个成员到用哈希表所表示的集合，把 gethash 用 setf 设成 t ：

  1. > (setf fruit (make-hash-table))
  2. #<Hash-Table BFDE76>
  3. > (setf (gethash 'apricot fruit) t)
  4. T

然后要测试是否为成员，你只要调用：

  1. > (gethash 'apricot fruit)
  2. T
  3. T

由于 gethash 缺省返回真，一个新创的哈希表，会很方便地是一个空集合。

要从集合中移除一个对象，你可以调用 remhash ，它从一个哈希表中移除一个词条：

  1. > (remhash 'apricot fruit)
  2. T

返回值说明了是否有词条被移除；在这个情况里，有。

哈希表有一个迭代函数： maphash ，它接受两个实参，接受两个参数的函数以及哈希表。该函数会被每个键值对调用，没有特定的顺序：

  1. > (setf (gethash 'shape ht) 'spherical
  2.         (gethash 'size ht) 'giant)
  3. GIANT
  5. > (maphash #'(lambda (k v)
  6.                (format t "~A = ~A~%" k v))
  7.            ht)
  8. SHAPE = SPHERICAL
  9. SIZE = GIANT
  10. COLOR = RED
  11. NIL

maphash 总是返回 nil ，但你可以通过传入一个会累积数值的函数，把哈希表的词条存在列表里。

哈希表可以容纳任何数量的元素，但当哈希表空间用完时，它们会被扩张。如果你想要确保一个哈希表，从特定数量的元素空间大小开始时，可以给 make-hash-table 一个选择性的 :size 关键字参数。做这件事情有两个理由：因为你知道哈希表会变得很大，你想要避免扩张它；或是因为你知道哈希表会是很小，你不想要浪费内存。 :size 参数不仅指定了哈希表的空间，也指定了元素的数量。平均来说，在被扩张前所能够容纳的数量。所以

(make-hash-table :size 5)

会返回一个预期存放五个元素的哈希表。

和任何牵涉到查询的结构一样，哈希表一定有某种比较键值的概念。预设是使用 eql ，但你可以提供一个额外的关键字参数 :test 来告诉哈希表要使用 eq ， equal ，还是 equalp ：

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

这是一个让哈希表变得有效率的取舍之一。有了列表，我们可以指定 member 为判断相等性的谓词。有了哈希表，我们可以预先决定，并在哈希表构造时指定它。

大多数 Lisp 编程的取舍（或是生活，就此而论）都有这种特质。起初你想要事情进行得流畅，甚至赔上效率的代价。之后当代码变得沉重时，你牺牲了弹性来换取速度。