除留余数法构造哈希表

除留余数法（也称为取模法或哈希函数）是构造哈希表常用的一种方法，它是将关键字（数据元素）通过一个哈希函数转换为哈希地址，然后将数据存储在对应索引位置的过程。这种方法的基本步骤如下： 1. **哈希函数设计**：选择一个合适的哈希函数，它接受一个输入（如键值）并返回一个范围在哈希表大小内的整数。通常会使用关键字对某个固定常数取模，以便得到有限的哈希地址空间。 2. **计算哈希地址**：对于给定的键值，通过哈希函数计算出一个哈希地址。这个地址用来决定数据在表中的存储位置。 3. **处理冲突**：由于哈希表的大小有限，不同键值可能会计算出相同的哈希地址（碰撞），这时就需要冲突解决策略。常见的有开放寻址法（如线性探测）和链地址法。 线性探测法是一种解决哈希表冲突的方法，当遇到碰撞时，它会在当前地址基础上加一个递增的步长，继续寻找下一个空闲位置，直到找到或填满整个哈希表。这种方法简单易实现，但随着冲突的增加，查找时间可能会变长，因为它依赖于探测序列的长度。 相关问题-- 1. 除留余数法在处理哈希冲突时有何优缺点？ 2. 线性探测法的具体查找过程是怎样的？ 3. 在哪些情况下，线性探测法可能不如链地址法有效？

以下是C语言版数据结构实现哈希表的构造和查找算法，使用除留余数法构造哈希表，用链地址法解决冲突： ```c #include <stdio.h> #include <stdlib.h> #define MAXSIZE 13 //哈希表长度 //定义哈希表节点 typedef struct HashNode { int key; struct HashNode *next; } HashNode; //定义哈希表 typedef struct HashTable { HashNode *head[MAXSIZE]; } HashTable; //哈希函数 int HashFunction(int key) { return key % MAXSIZE; } //初始化哈希表 void HashInit(HashTable *hashTable) { for (int i = 0; i < MAXSIZE; i++) { hashTable->head[i] = NULL; } } //插入节点 void HashInsert(HashTable *hashTable, int key) { int index = HashFunction(key); HashNode *node = (HashNode *)malloc(sizeof(HashNode)); node->key = key; node->next = NULL; if (hashTable->head[index] == NULL) { hashTable->head[index] = node; } else { HashNode *p = hashTable->head[index]; while (p->next != NULL) { p = p->next; } p->next = node; } } //查找节点 HashNode *HashSearch(HashTable *hashTable, int key) { int index = HashFunction(key); HashNode *p = hashTable->head[index]; while (p != NULL && p->key != key) { p = p->next; } return p; } //打印哈希表 void PrintHashTable(HashTable *hashTable) { for (int i = 0; i < MAXSIZE; i++) { printf("hashTable[%d]: ", i); HashNode *p = hashTable->head[i]; while (p != NULL) { printf("%d ", p->key); p = p->next; } printf("\n"); } } int main() { HashTable hashTable; HashInit(&hashTable); int keys[] = {12, 3, 23, 14, 7, 8, 9, 10, 11, 5, 6, 16, 21}; int n = sizeof(keys) / sizeof(keys[0]); for (int i = 0; i < n; i++) { HashInsert(&hashTable, keys[i]); } PrintHashTable(&hashTable); int key = 7; HashNode *node = HashSearch(&hashTable, key); if (node != NULL) { printf("Find key %d\n", key); } else { printf("Not find key %d\n", key); } return 0; } ```