用除留余数法构造哈希函数并用线性探测再散列法解决冲突

### 创建哈希函数

为了创建一个基于除留余数法的哈希函数，通常会选择一个质数作为哈希表的长度 \( m \)，这是因为当模数为质数时可以更好地分布键值。对于给定的键值 key ，哈希函数定义如下：

\[ h(key) = key \% m \]

其中 \( \% \) 表示取模运算符[^1]。

### 处理冲突：线性探测再散列

在线性探测中，如果计算得到的位置已经被占用，则按照固定的步长顺序寻找下一个可用位置。具体来说，在发生碰撞的情况下，算法会依次检查 \( (h(key)+i)\%m \) 的槽位，这里 \( i=0,1,...,m-1 \)[^2]。

一旦发现空闲位置就将新元素放置于此处；若遍历一圈回到起点仍未找到空间则说明哈希表已满。

下面是一个简单的 C 语言实现例子展示如何利用上述原理构建哈希表并处理冲突:

#include <stdio.h>
#define TABLE_SIZE 11 // 定义哈希表大小为11，这是一个素数

int hash_table[TABLE_SIZE]; 

// 初始化哈希表为空(-1表示未被使用)
void init_hash() {
    int i;
    for(i = 0; i < TABLE_SIZE; ++i){
        hash_table[i]=-1;
    }
}

// 插入数据到哈希表中
void insert(int value) {
    int index = value % TABLE_SIZE;

    while(hash_table[index]!=-1 && hash_table[index]!=value){ // 如果当前位置已被占或不是相同数值
        printf("Collision occurred at position %d\n",index);
        index=(index+1)%TABLE_SIZE; // 进行线性探查
        
        if(index==value%TABLE_SIZE){ // 当再次循环回原来起始点时停止操作
            printf("Table is full.\n");
            return ;
        }    
    }

    hash_table[index]=value;
    printf("%d inserted successfully at position %d\n",value,index);
}

此段代码展示了初始化哈希表 `init_hash` 函数以及插入元素至哈希表内的逻辑 `insert` 。每当遇到冲突时就会执行线性探测直至找到合适的位置或者确认表格已经满了为止[^3]。