哈希表查找成功和不成功的算法

1、哈希表查找不成功怎么计算？解答：先建好表，然后可以算出每个位置不成功时的比较次数之和，再除以表空问个数！例如：散列函数为hash(x)=x MOD 13 ,用线性探测，建立了哈希表之后，如何求查找不成功时的平均查找长度！ ？地址：01 23456789 10 1112数据：391228154244625-36-38成功次数：1 312211911不成功次数：9 87654321 12 110查找成功时的平均查找长度：ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2查找不成功时的平均查找长度：ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54说明：

2、第n个位置不成功时的比较次数为，第 n个位置到第1个没有数据位置的距离。至少要查询多少次才能确认没有这个值。(1) 查询hash(x)=0,至少要查询9次遇到表值为空的时候，才能确认查询失 败。(2) 查询hash(x)=1,至少要查询8次遇到表值为空的时候，才能确认查询失 败。(3) 查询hash(x)=2,至少要查询7次遇到表值为空的时候，才能确认查询失 败。(4) 查询hash(x)=3,至少要查询6次遇到表值为空的时候，才能确认查询失 败。(5) 查询hash(x)=4,至少要查询5次遇到表值为空的时候，才能确认查询失 败。(6) 查询hash(x)=5,至少要查询4次遇到表值为空的时

3、候，才能确认查询失 败。(7) 查询hash(x)=6,至少要查询3次遇到表值为空的时候，才能确认查询失 败。(8) 查询hash(x)=7,至少要查询2次遇到表值为空的时候，才能确认查询失 败。(9) 查询hash(x)=8,至少要查询1次遇到表值为空的时候，才能确认查询失 败。(10) 查询hash(x)=9,至少要查询1次遇到表值为空的时候，才能确认查询失 败。(11) 查询hash(x)=10,至少要查询2次遇到表值为空的时候，才能确认查询失 败。(12) 查询hash(x)=11,至少要查询1次遇到表值为空的时候，才能确认查询失 败。(13) 查询hash(x)=12,至少要查询10

4、次遇到表值为空(循环查询顺序表)的时 候，才能确认查询失败。下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联 考计算机学科专业基础综合试题中一个考哈希表的题。Question1:将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存 储空间是一个下标从0开始的一维数组，散歹U函数为：H(key) = (keyx3) MOD7 , 处理冲突采用线性探测再散列法，要求装填(载)因子为 0.7。(1) 请画出所构造的散列表。(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。Ans：(1).首先明确一个概念装载因子，装载因子是指所有关

5、键子填充哈希表后饱和的 程度，它等丁 关键字总数/哈希表的长度。根据题意，我们可以确定哈希表的长 度为L = 7/0.7 = 10;因此此题需要构建的哈希表是下标为 09的一维数组。根据散列函数可以得到如下散列函数值表。H(Key) = (keyx3) MOD 7, 例如 key=7 时，H=(7x3 ) %7 = 21%7=0 其他 关键字同理。Key 7 8 30 11 18 9 14H(Key) 0 3 6 5 5 6 0(表1)采用线性探测再散列法处理冲突，所构造的散列表为：地址 0 1 2 3 4 5 6 7 8 9关键字 7 14 8 11 30 18 9(表2)下面对散列表的构造

6、方式加以说明，注意表 1中的关键字7和14, 30和9, 11 和18,这三组关键子的H(Key)值相同，这在构建散列表时就会产生冲突，因为 他们的地址相同，所以要通过一定的冲突处理方法来解决这个问题。依题，采用线性探测再散列法处理冲突。下面详细介绍如何构建散列表：第一个key 7 ,它的地址是0,因此放到散歹0表的数组下表为 0的位置， 这个位置上没有关键字，因此没有冲突可以直接填入；第二个key 8 ,它的地址是3,因此放到散列表的数组下表为 3的位置， 这个位置上没有关键字，因此没有冲突可以直接填入；第三个key 30,它的地址是6,因此放到散歹0表的数组下表为 6的位置, 这个位置上没

7、有关键字，因此没有冲突可以直接填入；第四个key 11,它的地址是5,因此放到散歹0表的数组下表为 5的位置, 这个位置上没有关键字，因此没有冲突可以直接填入；第五个key 18,它的地址是5,因此放到散歹0表的数组下表为 5的位置, 但这个位置上已经有关键字11,遇到了冲突，此时我们根据线性探测再散列法 来处理这个冲突，探测下一个位置6, 6这个位置上已经存在关键字 30则继续增 加步长1,因此现在的新地址应为7,位置7上没有关键字，放入即可，至U此冲 突已经解决；第六个key 9 ,它的地址是6,因此放到散列表的数组下表为 6的位置， 但这个位置上已经有关键字 30,遇到了冲突，探测下一个

8、位置 7, 7这个位置上 已经存在关键字18则继续增加步长1,因此现在的新地址应为8,位置8上没有 关键字，放入即可；第七个key 14,它的地址是0,因此放到散歹0表的数组下表为 0的位置, 但这个位置上已经有关键字7,遇到了冲突，探测下一个位置 1,位置1上没有 关键字，放入即可；到这一步所有关键字均已填入，散列表已经构造完成，如表2所示。（2）等概率情况下查找成功平均查找长度：这一问可以根据第一问的构造过程求解：key7 一次就填入了表中，因此查找次数为 1,同理8, 30 , 11查找次 数均为1; key18进行了 3次放入操作，探测位置分别是 5, 6, 7 ,因此查找 次数为3;

9、 key9也是3次；key14进行了两次探测，因此查找次数为 2。次数表 如表3所小Key 7 8 30 11 18 9 14Count 1 1 1 1 3 3 2（表3）所以 ASLsuccess= （1+1+1+1+3+3+2 / 7 = 12/7 。等概率情况下查找不成功的平均查找长度：接下来讨论不成功的情况，看表2,计算查找不成功的次数就直接找关 键字到第一个地址上关键字为空的距离即可，但根据哈希函数地址为MOD7因此初始只可能在06的位置。等概率情况下，查找06位置查找失败的查找次数 为：看地址0,到第一个关键字为空的地址 2的距离为3,因此查找不成功的次数 为3.地址1,到第一个关

10、键为空的地址2的距离为2,因此查找不成功的次 数为2.地址2,到第一个关键为空的地址2的距离为1,因此查找不成功的次数为1.地址3,到第一个关键为空的地址 4的距离为2,因此查找不成功的次 数为2.地址4,到第一个关键为空的地址 4的距离为1,因此查找不成功的次 数为1.地址5,到第一个关键为空的地址2（注意不是地址9,因为初始只可能 在06之间，因此循环回去）的距离为5,因此查找不成功的次数为5.地址6,到第一个关键为空的地址2（注意不是地址9,因为初始只可能 在06之间，因此循环回去）的距离为4,因此查找不成功的次数为4.因此查找不成功的次数表如下表所小Key 7 8 30 11 18 9

11、 14Count 3 2 1 2 1 5 4（表4）所以 ASLunsuccess= （3+2+1+2+1+5+4 / 7 = 18/7 。哈希表链地址法平均查找长度十二月 28th, 2010 Mr.li 1796 chaining DS HashTable哈希函数为：H（key）=key mod 11关键字为：1 13 12 34 38 33 27 221mod11=1所以数据1是届丁地址113mod11=2所以数据13是届丁地址212mod11=1所以数据12也是届丁地址1 （这个数据是数据1指针的另一个新数 据）34mod11=1所以数据34是届丁地址1 （这个数据是数据12指针的另一

12、个新数 据）38mod11=5所以数据38是届丁地址533mod11= 0所以数据33是届丁地址027mod11=5所以数据27是届丁地址5,（这个数据是数据38指针的另一个新 数据）22mod11= 0所以数据22是届丁地址0,（这个数据是数据33指针的另一个新 数据）链地址法处理冲突构造所得的哈希表如下:0 -> 22 -> 33A1 -> 1 -> 12 -> 34A2 -> 13A3A4A5 -> 27 -> 38A6八7A8A9A10A查找成功时： ASL= (1X 4+2 X 3+3 X 1) /8=13/8其中红色标记为查找次数。也

13、就是说，需查找1次找到的有4个，其它以此类推查找不成功时：ASL=(3+4+2+1+1+3+1+1+1+1+1)/11=19/11以第一个3为例，其对应于0地址位，确定查找不成功需比较3次，其它以此类 推.链式处理冲突怎么求不成功的平均查找长度1 34 6723 584 26 48 815 9367 6889 75这个貌似不同的教材有不同的计算结果，不过运算方法是相同的。第一列的数据时需要比较一次的，包括34、58、26等以及2、6、8这三个位置。其中除了这三个位置外是查找成功比较一次，而这三个位置是查账不成功的。另外，3、5、7、9这几个位置是需要比较两次才知道查找不成功的；同理，1位置查找

14、不成功比较 3次，4位置比较4次。所以有 ASL=(1X3+2X4+3X1+4X1)/9=18/9下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机 学科专业基础综合试题中一个考哈希表的题。Question1:将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为： H(key) = (keyx3) MOD 7处理冲突采用 线性探测再散列法，要求装填(载)因子为 0.7。(1)请画出所构造的散列表。(2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。Ans：(1).首先明确一个概

15、念装载因子，装载因子是指所有关键子填充哈希表后饱和的程度，它等于关键字总数/哈希表的长度。根据题意，我们可以确定哈希表的长度为L = 7/0.7 =10;因此此题需要构建的哈希表是下标为09的一维数组。根据散列函数可以得到如下散列函数值表。H(Key) = (keyx3) MOD 7, 例如 key=7 时，H=(7x3 ) %7 = 21%7=0,其他关键字同理。Key 7 8 30 11 18 9 14H(Key) 0 3 6 5 5 6 0(表1)采用线性探测再散列法处理冲突，所构造的散列表为：地址 0 1 2 3 4 5 6 7 8 9关键字 7 14 8 11 30 18 9 （表2

16、）下面对散列表的构造方式加以说明，注意表1中的关键字7和14, 30和9, 11和18,三组关键子的H(Key)值相同，这在构建散列表时就会产生冲突，因为他们的地址相同，所 以要通过一定的冲突处理方法来解决这个问题。依题，采用线性探测再散列法处理冲突。面详细介绍如何构建散列表：0的位置，这个位置3的位置，这个位置上6的位置，这个位置5的位置，这个位置5的位置，但这个位第一个key乙它的地址是0,因此放到散列表的数组下表为 没有关键字，因此没有冲突可以直接填入；第二个key 8,它的地址是3,因此放到散列表的数组下表为 没有关键字，因此没有冲突可以直接填入；第三个key 30，它的地址是6,因此

17、放到散列表的数组下表为 上没有关键字，因此没有冲突可以直接填入；第四个key 11 ,它的地址是5,因此放到散列表的数组下表为 上没有关键字，因此没有冲突可以直接填入；第五个key 18，它的地址是5,因此放到散列表的数组下表为置上已经有关键字11,遇到了冲突，此时我们根据线性探测再散列法来处理这个冲突，探 测下一个位置6, 6这个位置上已经存在关键字30则继续增加步长1,因此现在的新地址应为乙位置7上没有关键字，放入即可，到此冲突已经解决；第六个key 9,它的地址是6,因此放到散列表的数组下表为6的位置，但这个位置上已经有关键字 30,遇到了冲突，探测下一个位置7, 7这个位置上已经存在关

18、键字18则继续增加步长1,因此现在的新地址应为 8,位置8上没有关键字，放入即可；第七个key 14，它的地址是 0,因此放到散列表的数组下表为0的位置，但这个位置上已经有关键字 乙遇到了冲突，探测下一个位置1,位置1上没有关键字，放入即可；到这一步所有关键字均已填入，散列表已经构造完成，如表 2所示。(2)等概率情况下查找成功平均查找长度：这一问可以根据第一问的构造过程求解：key7一次就填入了表中，因此查找次数为 1,同理8, 30 , 11查找次数均为1;key18进行了 3次放入操作，探测位置分别是 5, 6, 7 ,因此查找次数为 3; key9也是3 次；key14进行了两次探测，因此查找次数为 2