当前位置：首页 > news >正文

算法-哈希查找

news 2026/7/14 21:39:59

哈希查找 (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。
开始遍历链表：第一个节点是 44，44 != 34，继续往下找。
第二个节点是 34，34 == 34，匹配成功！
查找结束：返回查找成功。