闲聊哈希表 (上)
作者 帅云霓 | 2010-03-02 06:47 | 类型 专题分析 | 5条用户评论 »
经典数据结构教科书中,“表”是数据结构的一个大家族。其中,有顺序表(数组)、单向链表、双向链表、循环链表等等。我们今天聊的不是这些,而是“表”中的异类——哈希表(Hash Table)。 为什么会有哈希表这种数据结构呢?让我们用一个通俗的例子来理解: 大家一定都查过字典吧,我们知道,《新华字典》是按照读音排序的,可以理解为一个以读音为key,按升序排列的数据库。对于读音已知的字,可以通过“二分查找法”,很快地查找到要找的字,其时间复杂度为O(log2n)。但是,对于不知道读音的字怎么办呢?如果使用“顺序查找”,一页一页地翻字典,假设一本新华字典600页,每翻查一页的时间开销为0.5分钟,那么,每查到一个字耗费的时间t的数学期望值E(t) = 600 * 0.5min / 2 = 150min,也就是查一个字需要两个半小时!当然,这是难以接受的! 为了解决这个问题,《新华字典》的编辑们,很快就想出了解决办法,那就是在字典的前面加入一个“检字表”,如“四角号码检字表”“部首检字表”等,其特点是以每个字的字形为依据,计算出一个索引值,并映射到对应的页数。比如“法”字,按四角号码检字法,其索引值为34131,再根据这个数值,就可以找到相应的字了。在这种情况下,查找算法的时间复杂度接近于O(1)。换句话说,字典再厚,也不会明显地影响到查字典的效率了。 好,让我们回到计算机的世界中来。 哈希表的最大特点,是数据存储位置(偏移量)和数据记录的内容相关,存在着一个函数换算关系: Offset = Hash (Key) 其中,Offset为数据存储的偏移量,Hash为散列函数(Hash Function),Content为数据记录内容的关键字(Hash Key)。假设,我们要建立一张《弯曲评论》全球访问量统计表,每条记录包含下面的数据结构: struct access_record_t { unsigned index_i; /* Index */ char country_name[MAX_COUNTRY_NAME_LEN]; /* 国家/地区名 */ unsigned long long access_count; /* 访问量 */ }; 我们可以用一个一维数组access_record存储这张表,其中access_record[index_i]为编号为index_i的国家的记录,也就是说,数据的存储位置由index_i值唯一确定。例如,中国大陆的index_i值为86,那么,access_record[86].access_count即为《弯曲评论》在中国大陆地区的访问量。 然而,我们知道,“China”比起数字86来,明显更接近自然语言,对于人脑的记忆来说更方便,所以,我们能不能想一个办法,做一个从国家/地区名到数字索引的映射呢?这就涉及到散列函数(Hash Function)了。 欲知后事,请继续关注弯曲评论,关注帅云霓~ | |
雁过留声
“闲聊哈希表 (上)”有5个回复
喜欢这种戏说方式的科普文章。
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=
DDB6E65A1E82C6DD8C3A059370CC37CB?
doi=10.1.1.127.9672&rep=rep1&type=pdf
this is all about hash for net work
简单易懂,喜欢这样的文章,科技不一定是死板的
第一次看一个人能把哈希表描绘的这么生动,谢谢楼主,呵呵
中和下呢?