HashTable的相关操作

HashTable的相关操作2015-09-20前言

学过Java的人肯定对Hash这个词非常之熟悉,HashTable、HashSet、HashMap等都是对哈希表的封装或改进。这次我们来看下哈希表用C语言表示的封装实现。

哈希表

哈希表又叫散列表，是实现字典操作的一种有效数据结构。哈希表的查询效率极高，在没有冲突（后面会介绍）的情况下不需经过任何比较，一次存取便能得到所查记录，因此理想情况下，查找一个元素的平均时间为O（1）。

哈希表就是描述key—value对的映射问题的数据结构，这在Java中大家都知道，更详细的描述是：在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字与哈希表中唯一一个存储位置相对应。我们称这个对应关系f为哈希函数，这个存储结构即为哈希表。

直接寻址表

当关键字的全域U比较小时，直接寻址是一种简单而有效的技术，它的哈希函数很简单：f（key） = key，即关键字大小直接与元素所在的位置序号相等。另外，如果关键字不是自然数，我们需要通过某种手段将其转换为自然数，比如可以将字符关键字转化为其在字母表中的序号作为关键字。直接寻址法不会出现两个关键字对应到同一个地址的情况，既不会出现f（key1） = f（key2）的情况，因此不用处理冲突，这便是其优点所在。

散列表

直接寻址的缺点非常明显，如果全域U很大，则在一台标准的计算机可用内存容量中，要存储大小为U的一张表也许不太实际，而且，实际需要存储的关键字集合K可能相对U来说很小，这时散列表需要的存储空间要比直接表少很多。散列表通过散列函数f计算出关键字key在槽的位置。散列函数f将关键字域U映射到散列表T[0...m-1]的槽位上。但是这里会存在一个问题：若干个关键字可能映射到了表的同一个位置处（算法导论上名其曰“槽”），我们称这种情形为冲突。当然理想的方法是尽量避免冲突，我们可以尽可能第将关键字通过f随即地映射到散列表的每个位置上。

哈希函数

哈希函数的构造方法很多，最好的情况是：对于关键字结合中的任一个关键字，经哈希函数映射到地址集合中任何一个地址的概率相等，也就是说，关键字经过哈希函数得到一个随机的地址，以便使一组关键字的哈希地址均匀分布在整个地址空间中，从而减少冲突。同样，由于多数哈希函数都是假定关键字的全域为自然数集N={0、1、2....}，因此所给关键字如果不是自然数，就要先想办法将其转换为自然数。下面我们就来看常用的哈希函数。

直接定址法

对应前面的直接寻址表，关键字与哈希表中的地址有着一一对应关系，因此不需要处理冲突。