数据结构-计中文课件

1、1 第8章 哈希表查找表 是由同一类型的数据元素（或记录）构成的集合。2对查找表经常进行的操作：4) 从查找表中删去某个数据元素。1) 查询某个“特定的”数据元素是否在查找表中；2) 检索某个“特定的”数据元素的各种属性；3) 在查找表中插入一个数据元素；3静态查找表 仅作查询和检索操作的查找表动态查找表 有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入查找表；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。4查找 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）； 若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录

2、的信息，或指示该记录在查找表中的位置； 否则称“查找不成功”，查找结果：给出“空记录”或“空指针”5关键字 是根据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）； 若此关键字可以识别唯一的一个记录，则称之谓“主关键字”； 若此关键字能识别若干记录，则称之谓“次关键字”。6如何查找？ 然而，查找表本身是一种很松散的结构，因此，为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。 取决于查找表的结构。如何查找？ Array（数组存储） :顺序查找法 O ( n )二分法查找 O ( log n ) 前提：按关键字有序，

3、排序O(nlogn)。 Linked List（链表） :顺序查找法 O ( n ) Binary Search Tree（二叉搜索树）-1维数据:Insertion O( log n )Deletion O( log n )Find O( log n ) KD-Tree-K维数据:Insertion O( log n )Deletion O( log n )Find O( log n )8一、哈希表是什么？二、哈希函数的构造方法三、处理冲突的方法四、哈希表的查找主要内容9 一、哈希表是什么？以上两节讨论的表示查找表的各种结构，有一个共同点：记录在表中的位置和它的关键字之间不存在一个确定的关系

4、，因此，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。10 用这类方法表示的查找表，其平均查找长度都不为零，不同表示方法的差别仅在于：和给定值进行比较的关键字的顺序不同。11 对于频繁使用的查找表，希望ASL=0。只有一个办法：预先知道所查关键字在表中的位置，也就是说，记录在表中位置和其关键字之间存在一种确定的关系。12 例如： 为每年招收的1000名新生建立一张查找表，其关键字为xx000 xx999（前两位为年份）。则可以下标为000999的顺序表表示之。由于关键字和记录在表中的序号相同，则不需要经过比较即可确定待查关键字。13但是，

5、对于动态查找表而言：1) 表长不确定；2) 在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。 因此，一般情况，需建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。14 简单地说，哈希表是基于哈希函数建立的一种查找表。Hash Tables01 s1 ht 0 ht 1 ht b1 b bucketss slots For each identifier x, we define a hash function f ( x ) = position of x in ht (i.e. the index of the bucke

6、t that contains x ) T := total number of distinct possible values for x n := total number of identifiers in ht identifier density := n / T loading density := n / (s b) A collision occurs when we hash two nonidentical identifiers into the same bucket, i.e. f ( i1 ) = f ( i2 ) when i1 i2 . An overflow

7、 occurs when we hash a new identifier into a full bucket.Collision and overflow happen simultaneously if s = 1.Example Mapping n = 10 C library functions into a hash table ht with b = 26 buckets and s = 2.Slot 1Slot 0012345625Loading density = ?10 / 52 = 0.19To map the letters a z to 0 25, we may de

8、fine f ( x ) = ? x 0 aacosacosdefinedefinefloatfloatexpexpcharcharatanatanceilceilfloorfloorclockctimeWithout overflow, Tsearch = Tinsert = Tdelete = O( 1 )17从这个例子可见，1) 哈希函数是一个映象，即： 将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；182) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：keykey2，而f(key1)=f(key2)并且，改

9、进哈希函数只能减少冲突，而不能避免冲突。 因此，在设计哈希函数时，一方面要考虑选择一个“好”的哈希函数；另一方面要选择一种处理冲突的方法。19 二、哈希函数的构造方法 对数字的关键字可有下列哈希函数的构造方法， 若是非数字关键字，则需先对其进行数字化处理。20 取关键字的某个线性函数值为哈希地址。即： H(key)=key或H(key) akey+b直接定址法21数字分析法Example Given size of a hash table = 100010.x1 = 1 2 3 4 5 6 10 x2 = 1 4 5 3 1 8 10 x3 = 1 2 2 1 6 2 10 x4 = 1 4

10、 9 2 8 0 10 The range of address is 0, 999 f ( x ) = x2100 + x410 + x522平方取中法Given x, first compute x2. Then fm = r bits in the middle of x2.Example A x = 0100 x2 = 0010000 fm(A) = 010J x = 1200 x2 = 1440000 fm(J) = 440Q3 x = 2163 x2 = 4745651 fm(Q3) = 745Note:中间的各位通常与关键字的所有各位相关。因此，不同的关键字产生不同的哈希地址的概

11、率高。 (2) 所取中间位的数目依赖于表的长度，如果取r位，则表长应为2r。23折叠法Example x = 6 2 3 2 0 3 2 4 1 1 1 2 2 0移位叠加6 2 32 0 32 4 11 1 2 2 01 1 9 9 fF ( x ) = 1 9 9间界叠加6 2 32 0 32 4 11 1 2 2 03 0 22 1 11 3 9 7 fF ( x ) = 3 9 724除留余数法 fD = x % M. Hence the table size is M.关键是M的选择Suggestion: 一般情况下，可以选M为质数或不包含小于20的质因素的合数。25 实际造表时，采

12、用何种构造哈希函数的方法取决于建表的关键字集合的情况（包括关键字的范围和形态），总的原则是使产生冲突的可能性降到尽可能地小。26 三、处理冲突的方法 处理冲突的实际含义是：为产生冲突的地址寻找下一个哈希地址。271、开放定址法 为产生冲突的地址H(key)求得一个地址序列： H0,H1,H2,.,Hs 1sm-1其中H0=H(key) Hi=(H(key)+di)mod m i=1,2,.s，m为哈希表的表长28增量di有三种取法： 1) 线性探测再散列 di=ci 最简单的情况 c=12) 二次探测再散列 di=12,-12,22,-22,.,或 di=12,22,32,.,3) 随机探测再

13、散列 di是一组伪随机数列或者di=iH(key)292.链地址法 将所有哈希地址相同的记录都链接在同一链表中。30四、哈希表的查找 查找过程和造表过程一致。假设采用开放定址处理冲空，则查找过程为：对于给定值K，计算哈希地址HiH(K) 若ri.key=NULLKEY则查找不成功 若ri.key=K 则查找成功 否则，求下一地址Hi，直至ri.key=NULLKEY(查找不成功)或ri.key=K(查找成功)为止。31决定哈希表查找的ASL的因素：1) 选用的哈希函数；2) 选用的处理冲突的方法；3) 哈希表饱和的程度，装载因子=n/m值的大小。 一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的