Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3181010
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8546
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: LINUX

2013-02-02 16:05:47

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

阅读(3420) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册