LISP之hash table

hash table是一个非常重要的数据结构，虽然我们学习过很多数据结构，但是，hash table使用的场景是最多的。hash table 提供了一种key-value的信息组织形式，完美情况下，我们可以常数时间获取到任何一个我们需要的信息条目，哪怕存储有上百万的信息条目。片汤话我也不多说了，本文介绍下LISP对hash table的支持。

hash table对LISP 来说 一种advance 的数据结构，里面的实现我的功底尚浅，不知道如何实现的，本文主要啊介绍一下API。

创建hash table

Lisp语言用make-hash-table 来创建一个hash table。

 (defparameter *my-hash* (make-hash-table)) 

我们可以看到创建出一个hash表。Lisp提供了判断某变量是否是hash table的接口hash-table-p,如果某变量或者某对象是hash table，那么返回T，否则返回NIL。

    Break 2 [3]> (defparameter *my-hash* (make-hash-table))
    *MY-HASH*
    Break 6 [7]> (setf a (list 1 2))
    (1 2)
    Break 6 [7]> (hash-table-p a)
    NIL
    Break 6 [7]> (hash-table-p *my-hash*)
    T 

key-->vaule

Lisp提供了gethash 函数，来根据key查找value的值。

 Break 6 [7]> (gethash 'key_1 *my-hash*)
    NIL ;
    NIL 

我们返回了两个值，第一个NIL表示key_1对应的value是NIL，但是有两种可能，一种是key_1压根不再hash-table里面，另一种是key_1在hash table中，只不过对应的value就是NIL，如果只返回NIL，这两种情况区分不开，所以，需要第二个返回值。NIL表示没找到，T表示找到了。

add item

另外一种就是给hash table添加key -value 对。这是用setf+gethash来实现的。

 Break 6 [7]> (setf (gethash 'key_2 *my-hash*) "value_2")
    "value_2"
    Break 6 [7]> (gethash 'key_2 *my-hash*)
    "value_2" ;
    T
    Break 6 [7]> (setf (gethash 'key_3 *my-hash*) NIL)
    NIL
    Break 6 [7]> (gethash 'key_3 *my-hash*)
    NIL ;
    T
    Break 7 [8]> (setf (gethash 'another_entry *my-hash*) 2.5)
    2.5
    Break 7 [8]> (gethash 'another_entry *my-hash*)
    2.5 ;
    T 

看上面的key_3，我们给key_3对应的value设成了NIL，我们执行get-hash，发现第二个值为T,表示hash table中的确是有key_3的。

del item

Lisp提供了remhash来删除hash table中的一个条目或者说key-value对。 如果hash table中存在 key对应的条目，那么返回T,否则返回NIL。

    Break 7 [8]> (remhash 'no_such_key *my-hash*)
    NIL
    Break 7 [8]> (remhash 'another_entry *my-hash*)
    T
    Break 7 [8]> (gethash 'another_entry *my-hash*)
    NIL ;
    NIL 

judge presence

判断一个key是否存在在hash table中，是经常需要做的事情。前面提高过，gethash返回两个值，第二个值是用来判断是否存在在hash table中的。

 (if (nth-value 1 (gethash 'no-entry *my-hash*))
     "Key exists"
     "Key does not exist") 

nth-value 1,表示第二个返回值（0-index）

count of entry

hash table总共的条目总数，lisp提供了hash-table-count这个function。、

 Break 7 [8]> (hash-table-count *my-hash*)
    2 

Traversing a Hash Table

遍历hash table，对于hash table的每个key -value对执行相应的操作是经常要做的事情，Lisp提供了maphash 函数。 下面我定义一个打印函数，将key value打印出来，然后遍历hash table，让每个key-value对都执行我定义的函数：

 (defun print-hash-entry (key value)
        (format t "~a-----------~a ~%" key value))
    (maphash #'print-hash-entry *my-hash*) 

输出如下

 KEY_3-----------NIL 
    KEY_2-----------value_2 
    NIL 

clear hash table

最后不用说了，就是清空hash table。Lisp提供了 clrhash 接口，它会删除所有记录。

 Break 8 [9]> (clrhash *my-hash*)
    #S(HASH-TABLE :TEST FASTHASH-EQL)
    Break 8 [9]> (hash-table-p *my-hash*)
    T
    Break 8 [9]> (hash-table-count *my-hash*)   
    0 

other

我们可以看到，Lisp对hash table这种非常有用的数据结构做了封装，提供了非常好的接口出来。可是作为一个骨子里面想understand一切，debug一切的C程序员来讲，用的很舒服，但是我不爽，因为不知道是怎么实现的，或者用流行语言说，总感觉不接地气儿，让人发虚。下面的内容多少能窥见hash table实现的一些内容。

对于我们C程序员来讲，都知道hash table是有bucket的概念的，或者说是链表头。计算出来hash值，扔到对应的桶里面去，如果不同的key计算出来的桶号是一样的， 那么链接起来，来解决冲突。一个问题就是，我们需要多少个桶。这取决与应用场景。比如我们要用hash table 存储1000个级别的key-value对，那么你一上来分配百万个桶，那纯粹是浪费内存，如果反过来，hash table需要存储百万级别的key-value对，你分配了10个桶，那时间性能有不行了，因为平均下来要遍历百万/10，10万次才能找到key对应的value，这效率有降下来了。

Lisp hash table也有这个类似的概念，hash table是动态调整的。当然也可以创建hash table的时候指定最大容纳记录的条数。

hash-table-size就是hash table不需要扩展所能容纳的最大key-value对的个数。。不幸的是，不同的LISP实现，默认值是不同的。我Ubuntu上装了gcl 和clisp两个，我们看下：

 >(defparameter *my-gcl-hash* (make-hash-table))

    *MY-GCL-HASH*

    >(hash-table-size *my-gcl-hash*)

    1024 

上面是GCL实现，可以看到默认是1024个key-value对，CLISP默认是1个key-value对，这个有点。。。 显而易见，hash table必须是可以扩展的，比如CLISP如果不能扩展的话，我们hash table就退化成数组或者链表了。OK，这就存在何时扩展，扩展多大的问题。

不一定是完全满了才增加桶的个数看下CLISP的默认实现：

    Break 11 [12]> (defparameter *my-2rd-hash* (make-hash-table))
    *MY-2RD-HASH*
    Break 11 [12]> (hash-table-rehash-threshold *my-2rd-hash*)
    0.75s0
    Break 11 [12]> (hash-table-rehash-size *my-2rd-hash*)
    1.5s0 

我们看到，对于CLISP来说，如果75%的桶有item（此处不一定准确，也可能是item总数是桶个数的75%）,那么我要扩充桶的个数，扩充多大呢，扩充为目前的1.5倍。

我写了一个测试程序，来测试hash table expand的时机和新的size，发现并不是75%满的时候扩展，而是，条目或者记录个数等于size的时候，才发生扩展，扩展的新size是老size的1.5倍。下面看下我的测试程序：

 (defun test_rehash(*my-hash*)
        (defparameter *size_last* (hash-table-size *my-hash*))
        (dotimes (n 10000)
            (setf (gethash n *my-hash*) n)
            (let ((size_cur (hash-table-size *my-hash*)))
                (when (/= size_cur *size_last*)
                    (format t "items:~a    size:~a  ~%" n *size_last*)
                    (setf *size_last* size_cur)
                ) 
            )
        )   
    )

    (defparameter *my-hash* (make-hash-table))
    (format t "threshold is ~a~%" (hash-table-rehash-threshold *my-hash*) )     
    (format t "rehash size is ~a~%" (hash-table-rehash-size *my-hash*) )
    (times (test_rehash *my-hash*)) 

输出如下：

 root@manu:~/code/lisp# clisp test_hash.fas
    threshold is 0.75s0
    rehash size is 1.5s0
    items:1    size:1  
    items:2    size:2  
    items:3    size:3  
    items:5    size:5  
    items:8    size:8  
    items:12    size:12  
    items:18    size:18  
    items:27    size:27  
    items:41    size:41  
    items:62    size:62  
    items:93    size:93  
    items:140    size:140  
    items:210    size:210  
    items:315    size:315  
    items:473    size:473  
    items:710    size:710  
    items:1065    size:1065  
    items:1598    size:1598  
    items:2397    size:2397  
    items:3596    size:3596  
    items:5394    size:5394  
    items:8091    size:8091  
     ..........

     ...........                                                                                                    
    Real time: 0.008987 sec.
    Run time: 0.008001 sec.
    Space: 745072 Bytes
    GC: 1, GC time: 0.004001 sec. 

参考文献
1 The Common Lisp Cookbook
2 实用Common Lisp 编程
3 Common Lisp the lanuage
4 Land of Lisp