数据结构-哈希表

1、、散列表、散列函数的构造方法、处理冲突的方法、散列表的检索、散列表的检索分析、总结和作业、教室练习、a0a1a2a3a4a5a6a8a10、例1:中有考试成绩，统计了各分段的人数。 对成绩Grade执行： Agrade/10，散列表是指23: ord (char )=ASC (char ) ASC (a ) 1，散列表是指将1000名学生的信息存储在数组A0A999中，例子：是每年募集的1000个所谓散列表，是指number(substring，3，3 )生成检索表：使用规定的关键字key计算f(key )数组的下标，检索表：使用数组存储n个关键字，所谓数组的下标0n-1 计算数组后缀创建检索

2、表：赋予grade来计算f(grade )数组的下标，例子4 :合计学生成绩的各分数段的人数，什么是散列表，检索时：赋予grade来计算f(grade )数组的下标，Hash函数： f(grade )。 前、Sun、Li、Wu、Chen、Han Ye、Dei、示例5 :对于以下九个关键字，散列函数f(key)=(Ord (第一个字符)- Ord(A) 1)/2，什么是散列表，Chen、Zao、Qian、su 由此可见，如何添加问题：关键字，散列表是指：1)散列函数将关键字集合映射为一个地址集合，该集合的设置是灵活的，并且该地址集合的大小不超过可允许的范围由于对于不同的关键字可以获得相同的散列地

3、址，即key1 key2，f(key1)=f(key2 )，所以容易发生“冲突”现象，所以很难找到“3”不冲突的散列函数。 通常，只能选择适当的散列函数以尽量减少冲突。 因此，要构建这样一个特殊的“查找表”，必须选择一个“好”(尽可能少的冲突)散列函数，还必须找到“处理冲突”的方法。 另外，散列表的定义基于所设定的散列函数H(key )与所选择的处理的冲突的方法，在有限的地址连续的地址集(区间)映射一系列的关键字，并以在地址集中有关键字的“对象”为对应地记录在表中此外，过程被称为散列表或散列，所获得的存储位置是散列地址或散列地址。 散列函数的构造方法、数字关键字有以下的构造方法： 如果是数字以

4、外的关键字，首先需要数字化。 1 .直接寻址法、3 .平方法、5 .馀数法、4 .折叠法、6 .随机数法、2 .数字分析法、散列函数为关键字的线性函数H(key)=key或h(key)=aakeyb，1 .直接寻址法、散列函数的构造方法2 .数字分析法假定关键字集合中的各关键字是由s位的数字构成(u1、u2、us )，对关键字集合整体进行分析，从中提取分布均匀的多位或它们的组合作为住址。 该方法仅适用于能够预先估计整体关键字的各位上各种数字出现的频度的方法。 散列函数的结构方法有80个记录，关键字是8位十进制，散列地址是2位十进制，仅分析： 8就3、4，2、7、5的数字分布几乎随机，所以将任意

5、的两位或两位和其它两位的叠加作为散列地址求“关键字的平方值”的目的是“扩大差”，平方值中间的各位可以受到整个关键字的大家的影响。 3 .平均方法适用于：关键字的所有位中几个数字重复出现的频率高的现象。散列函数的构造方法、4 .将折叠法、关键字分割为多个部分，并取它们的叠加和散列地址。 有两种复盖处理方法：移位复盖和接口复盖。的双曲馀弦值。 适用于：的关键字位数非常多，而且每个位数的关键字数字分布几乎均匀的情况。 散列函数的构造方法，该示例中的关键字是0442205864，散列地址的位数是4，5，8，4，2，0，4，1，0，8，H(key)=0088，移位叠加，5，8，4，0，2，4，6，9，h

6、 (key 其中，pm (表长度)和p应该不包含m以下的素数或20以下的质因数。 在散列函数的构造方法中，如果关键字组：39、18、24、33、21为p=9，则相应的散列函数值为：3、0、6、3，为什么要限制p？如果p包含质因数3，则为所有质因数3 另外，散列函数的构建方法、6 .随机数法、散列函数被设定为： H(key)=Random(key )。 Random是随机函数，通常用于为不同长度的关键字构建散列函数。散列函数的结构方法，实际上在构建散列表的情况下1 .采用哪个结构散列函数，是在构建表的关键字集合的情况下(包括关键字的范围和形式)2.整体的原则是尽可能地减小冲突的可能性。 3 .如

7、果在制作散列表的过程中发生了冲突，该怎么处理这些冲突呢？ 冲突的处理方法，冲突：在从关键字获得的散列地址位于j(0jn-1 )的位置处记录，冲突的处理：查找发生冲突的地址的下一个空散列地址，1 .开放地址法，2 .重散列法，3 .链接地址法，冲突处理冲突的方法，1 .开放地址法为发生冲突的地址H(key )求出H0，H1，H2，Hs 1 s m-1的地址序列。 h0=h (key ) hi=(h (key ) di ) mod mi=1，2， sm是散列表长，有处理冲突的方法、1 .线性探测再散列法、2 .二次探测再散列法3 .随机检测再散列法、增量di三种方法、处理冲突的方法、1 .开放地址

8、法、增量di三种方法- :1 )线性检测再散列d 2、3、m-1，处理冲突的方法，诸如：关键字集合19、01、23、14、55、68 11、82、36，散列函数H(key)=key MOD 11，并且使用线性探测再散列法来设定散列表、19、19、01、01、23、23、14、14、55、55、68、68、11、82、11、11、82、36、11、2、3、6、5、处理冲突的方法、1 .开放寻址法、增量di中-22，处理冲突的方法，例如：关键字集合19，01，23，14，55，68，11，82，36，19，19，01，01，23，23，23，14，14，55，68，11，82，55 另外，设定散列

9、函数H(key)=key MOD 11 (表长度=11 )，用二次探测器再散列法构筑散列表。11212143、用于处理冲突的方法、1 .开放地址法、以及用于增量di的三种方法-3 )用一组随机序列或di=iH2(key ) (也称为双散列函数检测)随机地检测再散列di 要求：注意：增量di必须具有“完整性”，随机检测时的m和di没有公因子。 平方探索时的表长m必须是4j 3的素数(:11、19、23等)，用于处理冲突的方法，H2(key )是另设的散列函数，其函数值必须与m互为素数。 如果m为素数，则H2(key )可以是1到m-1之间的任意数。 如果m是2的平方，则H2(key )必须是1到

10、m-1之间的任意奇数。 另外，冲突的处理方法，例如，在m=11的情况下，H2 (key )=(3key ) mo D10，19，01，23，14，55，68，11，82，36，1111111212，冲突的处理方法，2 .重新散列法，hi=rhi (key缺点：计算时间增加了。 处理冲突的方法、3 .链接地址法、所有关键字都是同义词的记录存储在同一线性链表中。 定义指针类型向量Chain ChainHashm的散列地址I中的所有记录都被插入到ChainHashi的链表中。用于处理：关键字集合19、01、23、14、55、68、11、82、36等冲突的方法用链地址法构建散列表。 散列函数为H(ke

11、y)=key MOD 7，19，01，23，14，55，68，11，82，36，ASL=(61 22 31)/9=13/9，处理冲突的方法，4 .共同的溢出区域，散列函数的值区域0， 只要不发生冲突，就将m-1向量HashTable0.m-1对每个基本表组件记录向量OverTable0.v为溢出表的关键字和基本表HashTable的关键字同义的记录记录写入溢出表中、散列表的搜索算法、搜索过程和表创建过程是一致的。 如果使用开放地址处理了冲突，那么查找过程为：1 .计算给定值k的散列地址i=H(K )，如果ri=NULL，则查找失败，如果ri.key=K，则查找成功，并且4 .如果散列表的检索算

12、法，int hashsize=997， 类型结构元素* elem； int count； /当前数据元素数int sizeindex； /当前容量HashTable； # define success1# define unsuccess0# define duplicate=空密钥/下一个探测地址p，if (EQ(K，h.elemp.key ) )返回成功； /检索成功，返回要检索的数据元素的位置p，else return UNSUCCESS检索失败的散列表维护算法，Status InsertHash (HashTable，if (SearchHash (H，h，if ) ) /表中已经有与

13、e具有相同关键字的元素，else if (chashsizeh.size index/2 )/冲突次数c未达到上限，(阈值c可调) H.elemp=e； h .计数； 返回确认； else recreate hashtable (h ) return unsuccess； /从散列表的重建、散列表的检索分析、检索过程来看： 1、由于冲突的发生，散列表的检索过程还是一定值和关键字的比较过程。 2、散列表检索的平均检索长度实际上不为0。散列表的检索分析，1 )选定散列函数2 )处理选定纠纷的方法3 )散列表的饱和程度、装载系数=n/m的值的大小(n记录数，m表的长度)、决定散列表检索的ASL的要素：散列表的检索分析，一般是选择因此，哈希表中的ASL是处理碰撞方法和装载因子的函数。 例如，上述示例中的线性探测处理冲突、ASL=、链地址法处理冲突、ASL=、22/9、13/9、哈希表搜索分析、线性探测重散列可以证明搜索成功时具有以下结果：随机探测重散列、链地址这意味着当使用散列表构建查找表时，可以选择适当的装