3. 哈希表

下图示意了哈希表(Hash Table)这种数据结构。

图 26.12. 哈希表

哈希表

如上图所示,首先分配一个指针数组,数组的每个元素是一个链表的头指针,每个链表称为一个槽(Slot)。哪个数据应该放入哪个槽中由哈希函数决定,在这个例子中我们简单地选取哈希函数h(x) = x % 11,这样任意数据x都可以映射成0~10之间的一个数,就是槽的编号,将数据放入某个槽的操作就是链表的插入操作。

如果每个槽里至多只有一个数据,可以想像这种情况下searchinsertdelete操作的时间复杂度都是O(1),但有时会有多个数据被哈希函数映射到同一个槽中,这称为碰撞(Collision),设计一个好的哈希函数可以把数据比较均匀地分布到各个槽中,尽量避免碰撞。如果能把n个数据比较均匀地分布到m个槽中,每个糟里约有n/m个数据,则searchinsertdelete和操作的时间复杂度都是O(n/m),如果n和m的比是常数,则时间复杂度仍然是O(1)。一般来说,要处理的数据越多,构造哈希表时分配的槽也应该越多,所以n和m成正比这个假设是成立的。

请读者自己编写程序构造这样一个哈希表,并实现searchinsertdelete操作。

如果用我们学过的各种数据结构来表示n个数据的集合,下表是searchinsertdelete操作在平均情况下的时间复杂度比较。

表 26.1. 各种数据结构的search、insert和delete操作在平均情况下的时间复杂度比较

数据结构searchinsertdelete
数组O(n),有序数组折半查找是O(lgn)O(n)O(n)
双向链表O(n)O(1)O(1)
排序二叉树O(lgn)O(lgn)O(lgn)
哈希表(n与槽数m成正比)O(1)O(1)O(1)

习题

1、统计一个文本文件中每个单词的出现次数,然后按出现次数排序并打印输出。单词由连续的英文字母组成,不区分大小写。

2、实现一个函数求两个数组的交集:size_t intersect(const int a[], size_t nmema, const int b[], size_t nmemb, int c[], size_t nmemc);。数组元素是32位int型的。数组anmema个元素且各不相同,数组bnmemb个元素且各不相同。要求找出数组a和数组b的交集保存到数组c中,nmemc是数组c的最大长度,返回值表示交集中实际有多少个元素,如果交集中实际的元素数量超过了nmemc则返回nmemc个元素。数组a和数组b的元素数量可能会很大(比如上百万个),需要设计尽可能快的算法。