加拿大计划网站怎么做,昆明网站快速优化排名,大型门户网站制作流程,山西自助建站系统怎么用Hash表的“查找成功的ASL”和“查找不成功的ASL” ASL指的是 平均查找时间
关键字序列#xff1a;#xff08;7、8、30、11、18、9、14#xff09;
散列函数#xff1a; H(Key) (key x 3) MOD 7
装载因子#xff1a; 0.7
处理冲突#xff1a;线性探测再散列法
查…Hash表的“查找成功的ASL”和“查找不成功的ASL” ASL指的是 平均查找时间
关键字序列7、8、30、11、18、9、14
散列函数 H(Key) (key x 3) MOD 7
装载因子 0.7
处理冲突线性探测再散列法
查找成功的ASL计算方法 以下求解过程是按照“计算机统考的计算方法”不同的老师、教材在“处理冲突”上可能会有不同的方法所以最主要的是掌握原理即可对于考研的朋友最好掌握统考真题的解题方法。
题目 例子2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题第一题
将关键字序列7、8、30、11、18、9、14散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为 H(key) (keyx3) MOD 7处理冲突采用线性探测再散列法要求装填载因子为0.7。 (1) 请画出所构造的散列表 (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 1.散列表 α 表中填入的记录数/哈希表长度 哈希表长度 7/0.7 10 H(7) (7x3) MOD 7 0 H(8) (8x3) MOD 7 3 H(30) (30x3) MOD 7 6 H(11) (11x3) MOD 7 5 H(18) (18x3) MOD 7 5 H(9) (9x3) MOD 7 6 H(14) (14x3) MOD 7 0 按关键字序列顺序依次向哈希表中填入发生冲突后按照“线性探测”探测到第一个空位置填入。
因为现在的数据是7个填充因子是0.7。所以数组大小7/0.710即写出来的散列表大小为10下标从0~9。 第一个元素7带入散列函数计算得0。 第二个元素8带入散列函数计算得3。 第三个元素30带入散列函数计算得6。 第四个元素11带入散列函数计算得5。 第五个元素18带入散列函数计算得5此时和11冲突使用线性探测法得7。 第六个元素9带入散列函数计算得6此时和30冲突使用线性探测法得8。 第七个元素14带入散列函数计算得0此时和7冲突使用线性探测法得1。 所以散列表 地址 0 1 2 3 4 5 6 7 8 9 key 7 14 8 11 30 18 9 2.查找长度 2.1 查找成功的平均查找长度 待查找的数字肯定在散列表中才会查找成功 查找数字A的长度 需要和散列表中的数比较的次数 步骤 比如 查找数字8 则 H(8) (8x3) MOD 7 3 哈希表中地址3处的数字为8进行了第一次比较8 8则查找成功查找长度为1 比如查找数字14 则 H(14) (14x3) MOD 7 0 哈希表中地址0处的数字为7进行第一次比较7≠14 哈希表中地址1处的数字为14进行第二次比较1414 则查找成功查找长度为2。 由此可得到如下数据【2016年12月26日修改多谢一楼的朋友指正】 0 1 2 3 4 5 6 7 8 9 7 14 8 11 30 18 9 1 2 1 1 1 3 3 所以总的查找成功的平均查找长度 1111332/7 12/7 2.2查找不成功的平均查找长度 待查找的数字肯定不在散列表中 【解题的关键之处】根据哈希函数地址为MOD7因此任何一个数经散列函数计算以后的初始地址只可能在0~6的位置 查找0~6位置查找失败的查找次数为 地址0到第一个关键字为空的地址2需要比较3次因此查找不成功的次数为3. 地址1到第一个关键字为空的地址2需要比较2次因此查找不成功的次数为2. 地址2到第一个关键字为空的地址2需要比较1次因此查找不成功的次数为1. 地址3到第一个关键字为空的地址4需要比较2次因此查找不成功的次数为2. 地址4到第一个关键字为空的地址4需要比较1次因此查找不成功的次数为1. 地址5到第一个关键字为空的地址2(比较到地址6再循环回去)需要比较5次因此查找不成功的次数为5. 地址6到第一个关键字为空的地址2(比较到地址6再循环回去)需要比较4次因此查找不成功的次数为4. 于是得到如下数据 0 1 2 3 4 5 6 7 8 9 7 14 8 11 30 18 9 3 2 1 2 1 5 4 则查找不成功的平均查找长度 3212154/7 18/7
二.hash算法原理详解
一.概念
哈希表就是一种以 键-值(key-indexed) 存储数据的结构我们只要输入待查找的值即key即可查找到其对应的值。
哈希的思路很简单如果所有的键都是整数那么就可以使用一个简单的无序数组来实现将键作为索引值即为其对应的值这样就可以快速访问任意键的值。这是对于简单的键的情况我们将其扩展到可以处理更加复杂的类型的键。
使用哈希查找有两个步骤:
1. 使用哈希函数将被查找的键转换为数组的索引。在理想的情况下不同的键会被转换为不同的索引值但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突
2. 处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法本文后面会介绍拉链法和线性探测法。
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)如果没有时间限制那么我们可以使用无序数组并进行顺序查找这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。 在Hash表中记录在表中的位置和其关键字之间存在着一种确定的关系。这样我们就能预先知道所查关键字在表中的位置从而直接通过下标找到记录。使ASL趋近与0. 1) 哈希(Hash)函数是一个映象即 将关键字的集合映射到某个地址集合上它的设置很灵活只要这个地 址集合的大小不超出允许范围即可 2) 由于哈希函数是一个压缩映象因此在一般情况下很容易产生“冲突”现象即 key1key2而 f (key1) f(key2)。 3). 只能尽量减少冲突而不能完全避免冲突这是因为通常关键字集合比较大其元素包括所有可能的关键字 而地址集合的元素仅为哈希表中的地址值 在构造这种特殊的“查找表” 时除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外还需要找到一 种“处理冲突” 的方法。 二.Hash构造函数的方法 1.直接定址法 直接定址法是以数据元素关键字k本身或它的线性函数作为它的哈希地址即Hkk 或 Hka×kb (其中a,b为常数) 例1有一个人口统计表记录了从1岁到100岁的人口数目其中年龄作为关键字哈希函数取关键字本身如图(1)
地址
A1
A2
……
A99
A100
年龄
1
2
……
99
100
人数
980
800
……
495
107
可以看到当需要查找某一年龄的人数时直接查找相应的项即可。如查找99岁的老人数则直接读出第99项即可。 地址
A0
A1
……
A99
A100
年龄
1980
1981
……
1999
2000
人数
980
800
……
495
107 如果我们要统计的是80后出生的人口数如上表所示那么我们队出生年份这个关键字可以用年份减去1980来作为地址此时f(key)key-1980
这种哈希函数简单并且对于不同的关键字不会产生冲突但可以看出这是一种较为特殊的哈希函数实际生活中关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费因此这种方法适应性并不强。[2]↑ 此法仅适合于地址集合的大小 关键字集合的大小其中a和b为常数。 2.数字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)分析关键字集中的全体并从中提取分布均匀的若干位或它们的组合作为地址。
数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时可以通过对关键字的各位进行分析丢掉分布不均匀的位作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。 例2要构造一个数据元素个数n80,哈希长度m100的哈希表。不失一般性我们这里只给出其中8个关键字进行分析8个关键字如下所示
K161317602 K261326875 K362739628 K461343634
K562706815 K662774638 K761381262 K861394220
分析上述8个关键字可知关键字从左到右的第1、2、3、6位取值比较集中不宜作为哈希地址剩余的第4、5、7、8位取值较均匀可选取其中的两位作为哈希地址。设选取最后两位作为哈希地址则这8个关键字的哈希地址分别为275283415386220。 此法适于:能预先估计出全体关键字的每一位上各种数字出现的频度。 3.折叠法 将关键字分割成若干部分然后取它们的叠加和为哈希地址。两种叠加处理的方法移位叠加:将分 割后的几部分低位对齐相加边界叠加:从一端沿分割界来回折叠然后对齐相加。
所谓折叠法是将关键字分割成位数相同的几部分最后一部分的位数可以不同然后取这几部分的叠加和舍去进位这方法称为折叠法。这种方法适用于关键字位数较多而且关键字中每一位上数字分布大致均匀的情况。 折叠法中数位折叠又分为移位叠加和边界叠加两种方法移位叠加是将分割后是每一部分的最低位对齐然后相加边界叠加是从一端向另一端沿分割界来回折叠然后对齐相加。
例4当哈希表长为1000时关键字key110108331119891允许的地址空间为三位十进制数则这两种叠加情况如图 移位叠加 边界叠加 8 9 1 8 9 1 1 1 9 9 1 1 3 3 1 3 3 1 1 0 8 8 0 1 1 1 0 1 1 0 (1) 5 5 9 (3)0 4 4 图2由折叠法求哈希地址 用移位叠加得到的哈希地址是559而用边界叠加所得到的哈希地址是44。如果关键字不是数值而是字符串则可先转化为数。转化的办法可以用ASCⅡ字符或字符的次序值。 此法适于关键字的数字位数特别多。 4.平方取中法 这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方然后根据可使用空间的大小选取平方数是中间几位为哈希地址。
哈希函数 H(key)“key2的中间几位”因为这种方法的原理是通过取平方扩大差别平方值的中间几位和这个数的每一位都相关则对不同的关键字得到的哈希函数值不易产生冲突由此产生的哈希地址也较为均匀。
例5若设哈希表长为1000则可取关键字平方值的中间三位如图所示
关键字
关键字的平方
哈希函数值
1234
1522756
227
2143
4592449
924
4132
17073424
734
3214
10329796
297 下面给出平方取中法的哈希函数 //平方取中法哈希函数结设关键字值32位的整数 //哈希函数将返回key * key的中间10位 Int Hash (int key) { //计算key的平方 Key * key ; //去掉低11位 Key11; // 返回低10位即key * key的中间10位 Return key %1024; } 此法适于:关键字中的每一位都有某些数字重复出现频度很高的现象 5.减去法
减去法是数据的键值减去一个特定的数值以求得数据存储的位置。
例7公司有一百个员工而员工的编号介于1001到1100减去法就是员工编号减去1000后即为数据的位置。编号1001员工的数据在数据中的第一笔。编号1002员工的数据在数据中的第二笔…依次类推。从而获得有关员工的所有信息因为编号1000以前并没有数据所有员工编号都从1001开始编号。 6.基数转换法 将十进制数X看作其他进制比如十三进制再按照十三进制数转换成十进制数提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数并且两个基数应该是互素的。 例Hash(80127429)(80127429)138*1370*1361*1352*1347*1334*1322*1319(502432641)10如果取中间三位作为哈希值得Hash80127429432 为了获得良好的哈希函数可以将几种方法联合起来使用比如先变基再折叠或平方取中等等只要散列均匀就可以随意拼凑。 7.除留余数法
假设哈希表长为mp为小于等于m的最大素数则哈希函数为
hkk % p 其中%为模p取余运算。
例如已知待散列元素为18756043549046表长m10p7则有 h(18)18 % 74 h(75)75 % 75 h(60)60 % 74 h(43)43 % 71 h(54)54 % 75 h(90)90 % 76 h(46)46 % 74
此时冲突较多。为减少冲突可取较大的m值和p值如mp13结果如下 h(18)18 % 135 h(75)75 % 1310 h(60)60 % 138 h(43)43 % 134 h(54)54 % 132 h(90)90 % 1312 h(46)46 % 137
此时没有冲突如图8.25所示。 0 1 2 3 4 5 6 7 8 9 10 11 12 54 43
18 46
60 75 90 除留余数法求哈希地址 理论研究表明除留余数法的模p取不大于表长且最接近表长m素数时效果最好且p最好取1.1n1.7n之间的一个素数n为存在的数据元素个数 8.随机数法 设定哈希函数为:H(key) Random(key)其中Random 为伪随机函数 此法适于对长度不等的关键字构造哈希函数。 实际造表时采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)以及哈希表 长度哈希地址范围总的原则是使产生冲突的可能性降到尽可能地小。 9随机乘数法 亦称为“乘余取整法”。随机乘数法使用一个随机实数f,0≤f1,乘积f*k的分数部分在01之间用这个分数部分的值与n哈希表的长度相乘乘积的整数部分就是对应的哈希值显然这个哈希值落在0n-1之间。其表达公式为Hash(k)「n*(f*k%1)」其中“f*k%1”表示f*k 的小数部分即f*k%1f*k-「f*k」 例10对下列关键字值集合采用随机乘数法计算哈希值随机数f0.103149002 哈希表长度n100得图 k
f*k
n*((f*k)的小数部分)
Hash(k)
319426
32948.47311
47.78411
47
718309
74092.85648
86.50448
86
629443
64926.41727
42.14427
42
919697
84865.82769
83.59669
83 此方法的优点是对n的选择不很关键。通常若地址空间为p位就是选n2p.Knuth对常数f的取法做了仔细的研究他认为f取任何值都可以但某些值效果更好。如f-1/20.6180329...比较理想。 10字符串数值哈希法 在很都情况下关键字是字符串因此这样对字符串设计Hash函数是一个需要讨论的问题。下列函数是取字符串前10个字符来设计的哈希函数
Int Hash _ char (char *X)
{ int I ,sum i0; while (i 10 X[i]) Sum X[i]; sum%N; //N是记录的条数 }
这种函数把字符串的前10个字符的ASCⅡ值之和对N取摸作为Hash地址只要N较小Hash地址将较均匀分布[0N]区间内因此这个函数还是可用的。对于N很大的情形可使用下列函数
int ELFhash (char *key )
{ Unsigned long h0,g;
whie (*key)
{
h(h4) *key;
key;
gh 0 xF0000000L;
if (g) h^g24;
h g;
}
hh % N
return h;
} 这个函数称为ELFHash(Exextable and Linking Format ,ELF,可执行链接格式)函数。它把一个字符串的绝对长度作为输入并通过一种方式把字符的十进制值结合起来对长字符串和短字符串都有效这种方式产生的位置不可能不均匀分布。 11.旋转法 旋转法是将数据的键值中进行旋转。旋转法通常并不直接使用在哈希函数上而是搭配其他哈希函数使用。 例11某学校同一个系的新生小于100人的学号前5位数是相同的只有最后2位数不同我们将最后一位数旋转放置到第一位其余的往右移。
新生学号
旋转过程
旋转后的新键值
5062101
5062101
1506210
5062102
5062102
2506210
5062103
5062103
3506210
5062104
5062104
4506210
5062105
5062105
5506210 如图 运用这种方法可以只输入一个数值从而快速地查到有关学生的信息。 在实际应用中应根据具体情况灵活采用不同的方法并用实际数据测试它的性能以便做出正确判定。通常应考虑以下五个因素
l 计算哈希函数所需时间 简单。
l 关键字的长度。
l 哈希表大小。
l 关键字分布情况。
l 记录查找频率 三.Hash处理冲突方法 通过构造性能良好的哈希函数可以减少冲突但一般不可能完全避免冲突因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突两种情况下解决冲突的方法应该一致。下面以创建哈希表为例说明解决冲突的方法。常用的解决冲突方法有以下四种 通过构造性能良好的哈希函数可以减少冲突但一般不可能完全避免冲突因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突两种情况下解决冲突的方法应该一致。下面以创建哈希表为例说明解决冲突的方法。常用的解决冲突方法有以下四种
1. 开放定址法
这种方法也称再散列法其基本思想是当关键字key的哈希地址pHkey出现冲突时以p为基础产生另一个哈希地址p1如果p1仍然冲突再以p为基础产生另一个哈希地址p2…直到找出一个不冲突的哈希地址pi 将相应元素存入其中。这种方法有一个通用的再散列函数形式 HiHkeydi% m i12…n 其中Hkey为哈希函数m 为表长di称为增量序列。增量序列的取值方式不同相应的再散列方式也不同。主要有以下三种
l 线性探测再散列 dii123…m-1
这种方法的特点是冲突发生时顺序查看表中下一单元直到找出一个空单元或查遍全表。
l 二次探测再散列 di12-1222-22…k2-k2 ( km/2 ) 这种方法的特点是冲突发生时在表的左右进行跳跃式探测比较灵活。
l 伪随机探测再散列 di伪随机数序列。
具体实现时应建立一个伪随机数发生器如i(ip) % m并给定一个随机数做起点。
例如已知哈希表长度m11哈希函数为Hkey key % 11则H473H264H605假设下一个关键字为69则H693与47冲突。如果用线性探测再散列处理冲突下一个哈希地址为H13 1% 11 4仍然冲突再找下一个哈希地址为H23 2% 11 5还是冲突继续找下一个哈希地址为H33 3% 11 6此时不再冲突将69填入5号单元参图8.26 (a)。如果用二次探测再散列处理冲突下一个哈希地址为H13 12% 11 4仍然冲突再找下一个哈希地址为H23 - 12% 11 2此时不再冲突将69填入2号单元参图8.26 (b)。如果用伪随机探测再散列处理冲突且伪随机数序列为259……..则下一个哈希地址为H13 2% 11 5仍然冲突再找下一个哈希地址为H23 5% 11 8此时不再冲突将69填入8号单元参图8.26 (c)。 0 1 2 3 4 5 6 7 8 9 10 47
26
60
69 a 用线性探测再散列处理冲突 0 1 2 3 4 5 6 7 8 9 10 69
47
26
60 b 用二次探测再散列处理冲突 0 1 2 3 4 5 6 7 8 9 10 47
26
60 69 c 用伪随机探测再散列处理冲突 图8.26开放地址法处理冲突
从上述例子可以看出线性探测再散列容易产生“二次聚集”即在处理同义词的冲突时又导致非同义词的冲突。例如当表中i, i1 ,i2三个单元已满时下一个哈希地址为i, 或i1 ,或i2或i3的元素都将填入i3这同一个单元而这四个元素并非同义词。线性探测再散列的优点是只要哈希表不满就一定能找到一个不冲突的哈希地址而二次探测再散列和伪随机探测再散列则不一定。 2. 再哈希法 这种方法是同时构造多个不同的哈希函数 HiRH1key i12…k
当哈希地址HiRH1key发生冲突时再计算HiRH2key……直到冲突不再产生。这种方法不易产生聚集但增加了计算时间。
3. 链地址法 这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表并将单链表的头指针存在哈希表的第i个单元中因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
例如已知一组关键字324036531646712742244964哈希表长度为13哈希函数为Hkey key % 13则用链地址法处理冲突的结果如图 图链地址法处理冲突时的哈希表
本例的平均查找长度 ASL(1*72*43*1)1.5
4.建立公共溢出区 这种方法的基本思想是将哈希表分为基本表和溢出表两部分凡是和基本表发生冲突的元素一律填入溢出表 参考资料
大话数据结
算法导论 --------------------- 作者creator123123 原文https://blog.csdn.net/creator123123/article/details/81572288
