Hash表之ASL和不成功ASL的计算 (平均查找长度) |
您所在的位置:网站首页 › 哈希表二次探测再散列法解题过程 › Hash表之ASL和不成功ASL的计算 (平均查找长度) |
一、线性探测再散列法 Hash表: 元素的值(value)和在数组中索引位置(index)有一个确定关系 Index = Hash(key) ==> y = f(x) Index有可能相同,怎么处理冲突? 在“处理冲突”上可能会有不同的方法。 示例 : 将关键字序列(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 按关键字序列顺序依次向哈希表中填入,发生冲突后按照“线性探测”探测到第一个空位置填入。
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,进行第二次比较:14=14 ,则查找成功,查找长度为2。
所以总的查找成功的平均查找长度= (1+1+1+1+3+3+2)/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,到第一个关键字为空的地址9,因此查找不成功的次数为5. 地址6,到第一个关键字为空的地址9,因此查找不成功的次数为4. 于是得到如下数据:
二、平方探测再散列(二次探测再散列):
线性探测再散列
二次探测再散列
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |