Home > 程序/算法 > 算法基础–哈希表(hash table)

算法基础–哈希表(hash table)

August 14th, 2009 Leave a comment Go to comments

哈希表(hash table)是比较常用的数据结构,它能提供接近常量时间复杂度的数据插入和查找性能。哈希表的本质是利用一个哈希函数(hash function)将一个较大的取值范围映射到一个较小的取值范围,从而一方面节省了存储空间,另一方面又没有失去随机存取的性能。

举个简单的例子,比如我们手里有全班30个学生每个人的生日的数据表格,我要求快速的找出某一天有没有人,有哪些人过生日。最容易(或者说最笨)的算法是在表格里挨个查找,看谁的生日和指定的日期一致,显然这种算法是线性时间复杂度的,换句话说平均所需要的时间和全班人数成正比。

如果想快一点怎么办呢?可以事先把所有同学的名字填到一张有365个格子的大表里,每格代表一年中的一天,这样要知道某一天谁生日只要找到对应的格子,那天过生日的同学名字就在里面了。这个算法是常量复杂度的,就是说不管全班有多少人,我都能在几乎同样的时间里找到指定日期生日的人。

这样就快多了,但是如果全班只有30个人,却需要一张365格的大表显然很浪费,绝大部分格子都是空着的,用计算机术语说就是太浪费内存。那么怎样能改进一些呢?实际上这张表可以只精确到月,也就是用12格来分别对应1~12月,同样把所有同学的名字按生日的月份填到表里。这样需要的存储空间就小多了,而且平均每个格子只有2~3人,查找的效率并没有低多少,仍然是接近常量时间。

当然,你可以说如果全班有100个人怎么办,每个月就会有接近10个人生日了,10个人里找某一天生日的就慢的多了。的确,但是在这种情况下,你可以把表格扩张一些,比如变成每周对应一格,这样就需要54格,每格还是不到两个人。从年月日的日期转换成周算起来可能比较麻烦,但是这种事交给计算机做,算出是哪周和算出是哪月基本上没什么区别。

以上的例子中,把一年365天映射为12个月或者52周,这就是一个哈希函数。甚至最开始的365个格子的映射也可以认为是一种极端的1:1的哈希函数。不同的输入得到相同输出的情况叫做哈希冲突,比如上例中同一个月或同一周生日的同学超过一个。衡量一个哈希函数优劣的标准就是映射的结果在表中的位置是否足够随机,也就是尽量避免哈希冲突。当然这个标准是和输入有关的,比如上面例子中同学们的生日如果是全年平均分布的,那么按月或者按周映射就是一个很好的哈希函数,但是实际情况下貌似有些月份生日的总是偏多,比如十月,十一月(难道是因为过年结婚的人多?),那么取天数除以30或7取余可能会更好。

还有一点要注意,应该保持哈希表的尺寸与表里的元素总数接近(稍多一些更好),这样才能保证同一个“格子”里的数据不会太多。所以一般来说随着用户不断添加数据,哈希表需要按一定的比例扩张。扩张的时候需要把所有表里的数据重新填到新的表里,是开销比较大的操作,所以不能太频繁地扩张,最好每次扩张把表多扩张一些;但是扩张太多又会浪费内存,所以需要找一个合适的平衡点。在visual c++自带的STL实现中,每次扩张到原来的两倍大小。实际应用中如果你了解你将要填到哈希表里的数据的大致规模,也可以一开始就将表的大小设到指定值,以便省去扩张的开销。

Categories: 程序/算法 Tags: ,
  1. yuxuehua
    November 16th, 2009 at 16:18 | #1

    貌似什么hash呀 rand()呀 md5呀 crc32呀都是这个东西 搞不懂为什么这么多叫法

  2. study
    February 23rd, 2010 at 15:19 | #2

    通过LZ的比喻终于能比较形象的知道哈希表是怎么处理数据的了.

  1. No trackbacks yet.

 

Spam Protection by WP-SpamFree