算法-哈希查找

哈希查找 (Hash Search)像“查字典”一样不需要从头到尾挨个翻找。而是根据关键字(Key)直接套用一个“公式”(哈希函数)瞬间算出它应该在哪一页(存储地址)。如果算出来的位置刚好是你要找的词就成功了如果那个位置被别的词占了(哈希冲突)就按照既定规则往后顺延或者顺着链表找直到找到为止。核心代码#include stdio.h #include stdlib.h #define TABLE_SIZE 10 // 哈希表节点结构(链地址法) typedef struct Node { int key; struct Node *next; } Node; // 哈希表结构 typedef struct HashTable { Node *buckets[TABLE_SIZE]; } HashTable; // 初始化哈希表 void initHashTable(HashTable *table) { for (int i 0; i TABLE_SIZE; i) { table-buckets[i] NULL; } } // 插入元素 void insert(HashTable *table, int key) { int index key % TABLE_SIZE; // 使用除留余数法计算哈希地址 Node *newNode (Node *)malloc(sizeof(Node)); newNode-key key; newNode-next table-buckets[index]; // 头插法 table-buckets[index] newNode; } // 哈希查找函数 int search(HashTable *table, int key) { int index key % TABLE_SIZE; // 1. 计算哈希地址 Node *current table-buckets[index]; // 2. 定位到对应的桶(链表) // 3. 遍历链表查找目标 while (current ! NULL) { if (current-key key) { return 1; // 查找成功 } current current-next; } return 0; // 遍历结束未找到查找失败 } int main() { HashTable table; initHashTable(table); int keys[] {12, 22, 34, 44, 55}; for (int i 0; i 5; i) { insert(table, keys[i]); } int target 34; if (search(table, target)) { printf(成功找到目标值 %d\n, target); } else { printf(未找到目标值 %d\n, target); } return 0; }示例演示将 {12, 22, 34, 44, 55} 存入哈希表(哈希函数为 key % 10)然后查找目标值 34。第 1 步计算哈希地址目标通过公式瞬间定位目标所在的“桶”。取出目标关键字34。套用哈希函数34 % 10 4。定位直接访问哈希表下标为 4 的桶(链表)。第 2 步处理冲突与遍历查找目标在目标桶的链表中确认元素是否存在。访问下标为 4 的桶发现里面挂载了两个元素(因为 44 % 10 也等于 4发生了哈希冲突)。链表内容为44 - 34 - NULL。开始遍历链表第一个节点是 4444 ! 34继续往下找。第二个节点是 3434 34匹配成功查找结束返回查找成功。复杂度时间复杂度平均情况是\(O(1)\)(理想状态下无冲突一次定位即可找到)最坏情况是\(O(n)\)(所有元素都发生冲突挤在同一条链表里退化为顺序查找)。空间复杂度是\(O(n)\)(需要额外的空间来存储哈希表及链表节点)。要不要我出几道软考风格的哈希查找代码填空题帮你巩固一下