哈希表pdf.pdf

哈希表 哈希表（Hash Table ）是一种高效的数据结构。其最大的优点，就是把数据的存储和查找消耗的时间大大降 低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下， 用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。 哈希表又叫做散列表，分为开散列 和 闭散列 。考虑到竞赛时多数人通常避免使用动态存储结构，本文 中的哈希表仅指 闭散列 ，关于其他方面读者可参阅其他书籍。 2.1 基本原理 大家都知道，在所有的线性数据结构中，数组的定位速度最快，因为它可通过数组下标直接定位到相应的数组 空间，就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决数据的快速定位问 题。我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使 得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简 单的理解为，按照关键字为每一个元素分类 ，然后将这个元素存储在相应类所对应的地方。 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了 相同的函数值，这样就产生了冲突 ，换句话说，就是把不同的元素分在了相同的类之中。后面我们将看到 一种解决冲突 的简便做法。 总的来说，直接定址与解决冲突是哈希表的两大特点。 2.2 函数构造 构造函数的常用方法（下面为了叙述简洁，设h(k) 表示关键字为k 的元素所对应的函数值）： a) 除余法： 选择一个适当的正整数p ，令h(k ) = k mod p 这里，p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。 b) 数字选择法： 如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组 成的新的值作为关键字或者直接作为函数值。 2.3 冲突处理 线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为S ，则当h(k) 已经存储了元素的时候， 依次探查(h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元， 这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。 2.4 支持运算 哈希表支持的运算主要有：初始化(makenull) 、哈希函数值的运算(h(x)) 、插入元素(insert) 、查找元 素(member) 。 设插入的元素的关键字为x ，A 为存储的数组。 初始化比较容易，例如 const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素 p=9997; // 表的大小 procedure makenull; var i:integer; begin for i:=0 to p-1 do A[i]:=empty; End; 哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子： function h(x:longint):Integer; begin h:= x mod p; end; 我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此 加入一个定位的函数locate function locate(x:longint):integer; var orig,i:integer; begin orig:=h(x); i:=0; while (iS)and(A[(orig+i)mod S]x)and(A[(orig+i)mod S]empty) do inc(i); // 当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元 //素存储的单元，要么表已经满了 locate:=(orig+i) mod S; end; 插入元素 procedure insert(x:longint); var posi:integer; begin posi:=locate(x); //定位函数的返回值 if A[posi]=empty then A[posi]:=x else error; //error 即为发生了错误，当然这是可以避免的 end; 查找元素是否已经在表中 procedure member(x:longint):boolean; var posi:integer; begin posi:=locate(x); if A[posi]=x then member:=true else member:=fa