/*哈希查找
*哈希函数的构造方法常用的有5种。分别是：
*数字分析法
*平方取中法
*分段叠加
*伪随机数
*除留取余法
*这里面除留取余法比较常用
*避免哈希冲突常用的方法有4种：
*开放定址法（线性探测再散列、二次探测再散列）
*链地址法
*再哈希法
*建立公共溢出区
其中，线性探测再散列比较常用*/
这是一道2009年武汉科技大学的考研题，但是按照要求却做不出来，因为对7取模最多只有7个空间，不可能放进8个数，所以怀疑这道题是不是出错了，但这是考研题，应该不会出错吧。所以各位大神，你们怎么看？
以下是这道题的代码实现，可以看到27放不进哈希表中，因为哈希表已满！
#include <stdio.h>
#include <time.h>
#define Max 7
#define Length 10
#define N 8 int hashtable[Length]; int func(int value)
{
return value % Max; } void create_hash(int key)
{
int pos, t;
pos = func(key);
printf(" %d MOD %d = %d\n", key, Max, pos);
t = pos;
while(hashtable[t] != -)
{
printf("(%d+1) MOD %d = %d\n", t, Max, (t+) % Max);
t = (t+) % Max; if(pos == t)
{ printf("Hash table is full!\n");
return;
} }
hashtable[t] = key; } main()
{
int flag[N] = {, , , , , , , };
int i, j, t;
for(i = ; i < Length; i++)
hashtable[i] = -; i = ;
while(i != N)
{
t = flag[i]; create_hash(t);
printf(" ------------------------------------------------------------\n");
printf(" | 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 |\n");
printf(" ------------------------------------------------------------\n");
printf("%2d: ", t);
for(j = ; j < Length; j++)
printf("| %2d |", hashtable[j]); printf("\n");
printf(" ------------------------------------------------------------\n"); i++; } }
运行结果：
问题解决了！感谢可爱又靠谱的老师和帮我转发消息的baby！
之前的理解有误，以为不论是第一次代入函数计算还是处理冲突都是对函数给定的值取余，正确的是哈希函数对函数给定的值取余，处理冲突对表长取余。代码更正如下：
/*哈希查找
*哈希函数的构造方法常用的有5种。分别是：
*数字分析法
*平方取中法
*分段叠加
*伪随机数
*除留取余法
*这里面除留取余法比较常用
*避免哈希冲突常用的方法有4种：
*开放定址法（线性探测再散列、二次探测再散列）
*链地址法
*再哈希法
*建立公共溢出区
其中，线性探测再散列比较常用*/
#include <stdio.h>
#include <time.h>
#define Max 7
#define Length 10
#define N 8 int hashtable[Length]; int func(int value)
{
return value % Max; } void create_hash(int key)
{
int pos, t;
pos = func(key);
printf(" %d MOD %d = %d\n", key, Max, pos);
t = pos;
while(hashtable[t] != -)
{
printf("(%d+1) MOD %d = %d\n", t, Length, (t+) % Length);
t = (t+) % Length; if(pos == t)
{ printf("Hash table is full!\n");
return;
} }
hashtable[t] = key; } main()
{
int flag[N] = {, , , , , , , };
int i, j, t;
for(i = ; i < Length; i++)
hashtable[i] = -; i = ;
while(i != N)
{
t = flag[i]; create_hash(t);
printf(" ------------------------------------------------------------\n");
printf(" | 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 |\n");
printf(" ------------------------------------------------------------\n");
printf("%2d: ", t);
for(j = ; j < Length; j++)
printf("| %2d |", hashtable[j]); printf("\n");
printf(" ------------------------------------------------------------\n"); i++; } }
运行结果：
