叉排序树and哈希查找.pptVIP

* 处理冲突的方法 开放定址法 方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中。 Hi = (H(key)+di) MOD m，i=1,2,……k(k?m-1) 其中：H(key)——哈希函数 m——哈希表表长 di——增量序列 * 分类 线性探测再散列：di=1,2,3,……m-1 H1 =H(key) Hj =(Hj-1+1) MOD m j=2,3,… 二次探测再散列：di=12,-12,22,-22,32,……±k2(k?m/2) H1=H(key) H2j=(H1+j2) MOD m H2j+1=(H1-j2) MOD m j=1,2,3,… 伪随机探测再散：di=伪随机数序列 H1=H(key) Hj= (H1+R) MOD m * 例 表长为11的哈希表中已填有关键字为17，60，29的记录， H(key)=key MOD 11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中 0 1 2 3 4 5 6 7 8 9 10 60 17 29 (1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突 38 (2) H(38)=38 MOD 11=5 冲突 H1=(5+12) MOD 11=6 冲突 H2=(5-12) MOD 11=4 不冲突 38 (3) H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则： H1=(5+9) MOD 11=3 不冲突 38 * 再哈希法 方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址。 Hi=Rhi(key) i=1,2,……k 其中：Rhi——不同的哈希函数 特点：计算时间增加 链地址法 方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针 * 例： 已知一组关键字 (19，14，23，1，68，20，84，27，55，11，10，79) 哈希函数为： H(key)=key MOD 13 用链地址法处理冲突 0 1 2 3 4 5 6 7 8 9 10 11 12 14 ^ 1 27 79 68 55 19 84 20 23 10 11 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ * 哈希查找过程及分析 哈希查找过程 给定k值 计算H(k) 此地址为空 关键字==k 查找失败 查找成功 按处理冲突 方法计算Hi Y N Y N * 哈希查找分析 哈希查找过程仍是一个给定值与关键字进行比较的过程 评价哈希查找效率仍要用ASL 哈希查找过程与给定值进行比较的关键字的个数取决于： 哈希函数 处理冲突的方法 哈希表的装填因子?=表中填入的记录数/哈希表长度 例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等 (1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m H(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5 H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7