【前言】
本文将以哈希表重构实战为核心，完整展示如何将传统条件匹配逻辑(上千层if-else判断)转化为O(1)的哈希表高效实现。通过指纹验证场景的代码级解剖，您将深入理解：
1.哈希函数设计如何规避冲突陷阱
2.链式寻址法的工程实现细节
若有出错之处，望各位大哥大姐指出(●’◡’●)
Ⅰ 背景
最近，拿到一个场景，有一个研判规则中，需要一次匹配上千个以上规则的规则，一开始采用的是多层if判断，但是这种在高频事件中，明显性能遭不住，而且在研判速度上远远达不到预期
最初代码如下
bool is_finger(char finger[]){
if (strlen(finger) == yyy){
return 0;
}
if (strlen(finger) == xxx){
return 0;
}
//………………还有几千个规则研判
}
【目标】将程序的时间复杂度O(k*n)，降至O(1)
【实现】可以采用两种，一是哈希表，二是字典树
Ⅱ C程序优化实践
说那么多，没啥用，直接实操，冲冲冲
先定义下变量和结构体
#define HASH_SIZE 1024 // 哈希表大小，应该是质数以减少冲突
typedef struct HashNode {
char* key;
struct HashNode* next; // 处理冲突用的链表
} HashNode;
typedef struct {
HashNode* table[HASH_SIZE];
} HashMap;
初始化哈希表
// 哈希函数
unsigned int hash(const char* str) {
unsigned int hash = 5381;
int c;
while ((c = *str++)) {
hash = ((hash << 5) + hash) + c; // hash * 33 + c
}
return hash % HASH_SIZE;
}
// 初始化哈希表
HashMap* init_fingerprint_map() {
HashMap* map = (HashMap*)malloc(sizeof(HashMap));
memset(map->table, 0, sizeof(HashNode*) * HASH_SIZE);
// 需要过滤的指纹列表
const char* fingerprints[] = {
"En", "nTf.n", "kno:n", "n)on", "fknn",
"kn", "n&n", "nn", "n&nn", "Ton",
};
// 插入所有指纹
for (int i = 0; i < sizeof(fingerprints)/sizeof(char*); i++) {
unsigned int index = hash(fingerprints[i]);
HashNode* node = (HashNode*)malloc(sizeof(HashNode));
node->key = strdup(fingerprints[i]);
node->next = map->table[index];
map->table[index] = node;
}
return map;
}
关键实现，哈希查找
// 查找函数 - O(1) 平均时间复杂度
bool is_fingerprint(HashMap* map, const char* fingerprint) {
unsigned int index = hash(fingerprint);
HashNode* current = map->table[index];
// 在链表中查找
while (current != NULL) {
if (strcmp(current->key, fingerprint) == 0) {
return false; // 找到匹配项，返回false
}
current = current->next;
}
return true; // 未找到匹配项
}
记得要释放内存
// 释放哈希表内存
void free_hashmap(HashMap* map) {
for (int i = 0; i < HASH_SIZE; i++) {
HashNode* current = map->table[i];
while (current != NULL) {
HashNode* temp = current;
current = current->next;
free(temp->key);
free(temp);
}
}
free(map);
}
完整代码
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#define HASH_SIZE 1024 // 哈希表大小，应该是质数以减少冲突
typedef struct HashNode {
char* key;
struct HashNode* next; // 处理冲突用的链表
} HashNode;
typedef struct {
HashNode* table[HASH_SIZE];
} HashMap;
// 哈希函数
unsigned int hash(const char* str) {
unsigned int hash = 5381;
int c;
while ((c = *str++)) {
hash = ((hash << 5) + hash) + c; // hash * 33 + c
}
return hash % HASH_SIZE;
}
// 初始化哈希表
HashMap* init_fingerprint_map() {
HashMap* map = (HashMap*)malloc(sizeof(HashMap));
memset(map->table, 0, sizeof(HashNode*) * HASH_SIZE);
// 需要过滤的指纹列表
const char* fingerprints[] = {
"En", "nTf.n", "kno:n", "n)on", "fknn",
"kn", "n&n", "nn", "n&nn", "Ton",
};
// 插入所有指纹
for (int i = 0; i < sizeof(fingerprints)/sizeof(char*); i++) {
unsigned int index = hash(fingerprints[i]);
HashNode* node = (HashNode*)malloc(sizeof(HashNode));
node->key = strdup(fingerprints[i]);
node->next = map->table[index];
map->table[index] = node;
}
return map;
}
// 查找函数 - O(1) 平均时间复杂度
bool is_fingerprint(HashMap* map, const char* fingerprint) {
unsigned int index = hash(fingerprint);
HashNode* current = map->table[index];
// 在链表中查找
while (current != NULL) {
if (strcmp(current->key, fingerprint) == 0) {
return false; // 找到匹配项，返回false
}
current = current->next;
}
return true; // 未找到匹配项
}
// 释放哈希表内存
void free_hashmap(HashMap* map) {
for (int i = 0; i < HASH_SIZE; i++) {
HashNode* current = map->table[i];
while (current != NULL) {
HashNode* temp = current;
current = current->next;
free(temp->key);
free(temp);
}
}
free(map);
}
int main() {
// 初始化（只需要一次）
HashMap* map = init_fingerprint_map();
// 快速查找并打印结果
bool result1 = is_fingerprint(map, "En");
printf("Test 'En': %s\n", result1 ? "true" : "false");
bool result2 = is_fingerprint(map, "kn");
printf("Test 'kn': %s\n", result2 ? "true" : "false");
bool result3 = is_fingerprint(map, "other");
printf("Test 'other': %s\n", result3 ? "true" : "false");
// 清理资源
free_hashmap(map);
return 0;
}
Ⅲ 深度解析哈希表为啥能O(1)
1. 先了解下什么是哈希表？
想象你有一个带编号的储物柜（这就是哈希表）：
- 哈希函数就像一个规则，告诉你把东西放在哪个柜子里
- 比如：把字符串 “hello” 放到 3 号柜子
回到一开始说的"为什么说查找是 O(1)"!
当你要找 “hello” 时：
- 用哈希函数算出位置：3
- 我们直接去 3 号柜子找
这样子，是不是就不需要查看其他柜子了，直接O(1)，起飞芜湖~~
2. 哈希冲突到底是什么
了解了什么是哈希表，那开始熟悉下哈希冲突
假设现在：
- “hello” -> 3号柜子
- “world” -> 也是3号柜子
处理冲突的方式:储物柜用链子连接
好了，了解了基本逻辑，基本可以上C代码
// 假设我们有一个小型哈希表，存储常见编程语言
#define HASH_SIZE 8 // 8个储物柜
// 存储数据
hash("Python") -> 3
hash("Java") -> 3 // 冲突！
hash("Go") -> 5
储物柜：
0 1 2 3 4 5 6 7
[ ] [ ] [ ] [Python]-> [Java] [Go] [ ] [ ]
// 查找"Java"的过程
1. hash("Java") = 3 // 计算位置
2. 检查3号柜子的 Python // 不是
3. 检查下一个 Java // 找到了！
3.哈希表为什么快
- 想象一个真实的哈希表
#define HASH_SIZE 1024 // 1024个储物柜
// 如果存100个数据
// 平均每个柜子只会有 100/1024 ≈ 0.1 个数据
// 也就是说，大多数柜子是空的！
联想实际场景：图书馆找书
- 不需要从第一本找到最后一本
- 直接根据编号去对应书架
- 即使这个位置有几本书，也只需要看很少几本
这样子，就是不是很清晰了，其实哈希表，就是拿着key，拿到索引，然后去对应柜子找东西
按照这个思路，来解读下刚刚写的哈希查找代码
bool is_fingerprint(HashMap* map, const char* fingerprint) {
// 1. 计算应该去哪个储物柜
unsigned int index = hash(fingerprint);
// 2. 去到那个储物柜
HashNode* current = map->table[index];
// 3. 如果这个储物柜有多个物品，挨个检查
while (current != NULL) {
// 4. 检查是不是要找的东西
if (strcmp(current->key, fingerprint) == 0) {
return false; // 找到了！
}
current = current->next; // 看下一个
}
return true; // 没找到
}
值得注意的是：这里的循环是很少执行，因为柜子的东西不会太多，甚至有些规则还是空的
- 哈希表很大（比如1024个位置）
- 数据相对较少（比如100个）
- 哈希函数会尽量均匀分布
- 所以每个位置平均不到1个数据
所以虽然代码里有 while 循环，但实际上：
- 直接定位到具体位置（像图书馆找书架）
- 即使需要循环，也只需要看很少的几个
所以说哈希表，这就是为什么说它是 O(1) 的原因了，如果东西太多了，柜子设置太多了，就可以要用另一种方式了，那就是字典树
再次感谢各位大哥大姐们捧场，阅读到此，本篇结束，如有其他疑问，评论区相见~~
