博客

散列函数：

H(key) = key % 11

;

现有数据：1，13，12，34，38，33，27，22

要求：使用

线性探测法

处理冲突

step1：先将所有的数据装入哈希表汇总

1%11 = 1，没有冲突

13%11 = 2，没有冲突

12%11 = 1,下标1的位置上放置了数据1，此时


冲突


了，使用 线性探测法处理冲突，下标1上已经有数据了，所以往后查，此时下标2上也有数据了，再往下查到下标3，此时下标3上没有数据，将12放在下标3的位置中

34%11 = 1，


冲突


了，使用线性探测法，计算出地址为4

38%11 = 5，没有冲突

33 % 11 = 0，没有冲突

27 % 11 = 5，冲突，计算出地址为：6

22 % 11 = 0，冲突，计算出地址为：7

对于查找成功，只需要分别计算单个数据查找成功的次数，因为只有8个数据，所以需要计算8次：

1

因为没有冲突，只需要查找1次即可

13 没有冲突，只需要查找1次

12 冲突了，原本应该放在下标1的位置，现在放在了下标3的位置，需要查找下标1，2，3，共需要3次

34 冲突，原本放在下标1的位置，现在放在下标4的位置，需查找 4 次

38 没有冲突，查找1次

33 没有冲突，查找1次

27 冲突，原本应该放在下标5的位置，现在放在下标6的位置，需查找2次

22 冲突，原本应该放在下标0的位置，现在放在下标7的位置，需查找8次

ASL = (1+1+3+4+1+1+2+8)/8 = 21/8 = 2.625

查找失败：

对于查找失败，概率都是1/11，因此，0-10每个下标都需要计算，共计算11次，并且查找失败的时候，需要一直查找到第一个为


空


的地址才结束

key = 0，查找失败需要一直查找到 下标为 8 ，因为下标为8的地址为空，共需要9次

key = 1，查找失败需要8次

key = 2，查找失败需要7次

key = 3 ，查找失败需要6次

key = 4，查找失败需要5次

key = 5，查找失败需要4次

key = 6，查找失败需要3次

key = 7，失败需要2次

key = 8，失败需要1次

key = 9，失败需要1次

key = 10，失败需要1次

ASL = (9+8+7+6+5+4+3+2+1+1+1)/11 = 47/11