Question

关于哈希表的一道习题，望大神解答~？

设哈希表的地址范围为0~17，哈希函数为：H(key) = key % 16。用线性探测法处理冲突，输入关键字序列：(10，24，32，17，31，30，46，47，40，63，49)，构造哈希表。求哈希表示意图。
我就是搞不明白哈希地址地址下标最大为17，而求余操作最大为15，求出的哈希表的16和17位有元素吗？就像本题，到放入46的时候，是放在16位置还是放在2位置？

Answer 1

呵呵，这也是我曾经最搞不懂的地方呀，这个就是出题人给出来的一系列的条件而已，不要过多的考虑为什么，取不到怎么办。这个就是要明确3点：1、哈希函数，2、冲突处理方式，3、哈希表地址范围。一般情况就是哈希函数的取余值的大小与哈希表地址范围一致，但也会出现题目中的这种不一致的情况，而这里的不一致有时候是有理由的，不如这里采用线性探测再散列的方式处理冲突，是取di=1,2,3,4,....m-1的，当这里的15位置被占用时，就是要取在下一个位置了，直到达到散列地址的最大值。

另外看了一下你贴出来的图片，明白了你的问题在哪里。你要明确一点：在书本上的开放定址法的公式是怎么样的：H(key)=(H(key)+di)%m，i为1,2,3,...,m-1
比如46，第一次的H(key)值为15，已经被占用，那么再次计算时H(key)=（15+1）%m，要注意了，这里的m是18还是16？？？？？定义上的m值是指的哈希表的长度，而不是哈希函数中的16。所以你的上面的是正确的。这也是曾经困扰我很长时间的问题呀，再次遇到了，解答一下，不要嫌啰嗦。OVER。