第八章_Hash表技术.ppt

第8章 哈希表（Hash)技术 8.1 Hash表的基本概念 如果将数据元素的存储位置与它的关键字之 间建立一个确定的关系H，使每个关键字和一 个唯一的存储位置对应，在查找时，只需要根 据对应关系计算出给定的关键字值k对应的值 H(k)，就可以得到记录的存储位置，这就是本 节将要介绍的哈希表查找方法的基本思想。 设表的长度为n。如果存在一个函数i=i(k)， 对于表中的任意一个元素的关键字k，满足以 下条件：(1)1≤i≤n；(2)对于任意的元素关键字k1≠k2，恒存在 i(k1)≠i(k2). 则称此表为直接查找表。其中函数i＝i(k)称为 关键字k的映像函数。由此定义可知，对直接查 找表的查找，只需根据i＝i(k)计算出待查关键 字项目在表中的序号即可。 要在直接查找表中取出关键字k的元素，也只需做以下两步：1)计算关键字k的映象函数i＝i(k)；2)检查表中第i项：若第i项为空，则说明表中没有关键字为k的元素；否则取出第i项中的元素即可。 在直接查找表中，不允许存在元素的冲突。但在实际 应用中，这一条件一般很难满足，即往往出现这样的 情况：对于两个不同的关键字k1≠k2，有i(k1)=i(k2) ，称k1、k2这两个元素发生了冲突（collision)，即 两个不同的元素需要存放在同一个存储单元中。 将关键字序列 (09，31，26，19，01，13，02，11，27， 16，05，21)依次填入长度为n＝12的表中。映像函数为 i＝INT(k/3)＋1。 设表的长度为n。如果存在一个函数i＝i(k)，对于表 中的任意一个元素的关键字k，满足1≤i≤n，则称此表为 Hash表。其中函数值i＝i(k)称为关键字k的Hash码（或 Hash地址或散列地址）。 一个好的哈希函数应使函数值均匀的分布在存储 空间的有效地址范围内，以尽可能减少冲突。 Hash函数的构造方法： 取关键字或关键字的某个线性函数值为哈希地 址。即： H(key)=key H(key)=a*key+b 其中，a,b为常数（这种哈希函数叫做自身函数） 将关键字的编码除以表的长度，最后所得的余数 作为Hash码，即i＝mod(k，n)。k为关键字，n为Hash 表的长度，mod为模余运算符（规定：当mod(k,n)=0 时，取I=n）。本方法构造的Hash码，其匀称性比较 好，但是以一次除法为代价，在除法较快的机器上可 以使用。 选择一个随机函数，取关键字的随机函数值为它的哈希地 址，基H(key)=random(key),其中radnom为随机函数。通常， 当关键字长度不等时采用此法构造哈希函数较恰当。 计算哈希函数所需时间 关键字的长度 哈希表的大小 关键字的分布情况 数据元素的查找频率 8.2 几种常用的Hash表 将关键字k及有关信息填入线性Hash表的步骤： 1)计算关键字k的Hash码i＝i(k)。 2)检查表中第i项的内容： 若第i项为空，则将关键字k及有关信息填入该项； 若第i项不空，则令i＝mod(i＋1，n)，转2)继续检查。 只要Hash表尚未填满，最终总可以找到一个空项，将关键 字k及有关信息填入到Hash表中。 要在线性Hash表中取出关键字k的元素，其步骤如下： 将关键字序列(09，31，26，19，01，13，02，11 ，27，16，05，21)依次填入长度为n＝12的线性 Hash表中。设Hash码为i＝INT(k/3)＋1。 2)在线性Hash表的填入过程中，处理冲突时会带 来新的冲突（不顾后效）。 当Hash表的长度n设计成n=2k时 1)计算关键字k的Hash码i0＝i(k)。且令i＝i0。 2)伪随机数序列初始化，令j＝1（即将取随机数指针指向伪 随机数序列中的第1个随机数）。 3)检查表中第i项的内容： 若第i项为空，则将关键字k及有关信息填入该项；若第i 项不空，则令i＝mod(i0＋RN(j)，n)，并令j＝j＋1（即将 取随机数指针指向下一个随机数），转3)继续检查。其中 RN(j)表示伪随机数序列RN中的第j个随机数。 将关键字序列(09，31，26，19，01，13，02，11 ，27，16，05，21)依次填入长度为n＝24＝16的随 机Hash表中。设Hash码为i＝INT(k/3)＋1。 伪随机数序列为：1，6，15，12，13，2，11，8， 9，14，7，4，5，10，3，0。 要在随机Hash表中取出关键字k的元素的步骤： 1)计算关键字k的Hash码i0＝i(k)。且令i＝i0。 2)伪随机数序列初始化，令j＝1（即将