[讨论] 闲聊哈希表（上）

richiefang 2010-3-4 20:49 楼主

经典数据结构教科书中，“表”是数据结构的一个大家族。其中，有顺序表（数组）、单向链表、双向链表、循环链表等等。我们今天聊的不是这些，而是“表”中的异类——哈希表(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)。假设，我们要建立一张EEWorld全球访问量统计表，每条记录包含下面的数据结构：
struct access_record_t {

unsigned index_i; /* Index*/

charcountry_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即为EEWorld在中国大陆地区的访问量。
然而，我们知道，“China”比起数字86来，明显更接近自然语言，对于人脑的记忆来说更方便，所以，我们能不能想一个办法，做一个从国家/地区名到数字索引的映射呢？这就涉及到散列函数(Hash Function)了。