从O(k*n)到O(1):如何用哈希表终结多层if判断的性能困局
【前言】
本文将以哈希表重构实战为核心,完整展示如何将传统条件匹配逻辑(上千层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) 的原因了,如果东西太多了,柜子设置太多了,就可以要用另一种方式了,那就是字典树
再次感谢各位大哥大姐们捧场,阅读到此,本篇结束,如有其他疑问,评论区相见~~
相关文章:
从O(k*n)到O(1):如何用哈希表终结多层if判断的性能困局
【前言】 本文将以哈希表重构实战为核心,完整展示如何将传统条件匹配逻辑(上千层if-else判断)转化为O(1)的哈希表高效实现。通过指纹验证场景的代码级解剖,您将深入理解: 1.哈希函数设计如何规避冲突陷阱 2.链式寻址法的工程实现…...
视频采集卡接口
采集卡的正面有MIC IN、LINE IN以及AUDIO OUT三个接口, MIC IN为麦克风输入,我们如果要给采集到的视频实时配音或者是在直播的时候进行讲解,就可以在这里插入一个麦克风, LINE IN为音频线路输入,可以外接播放背景音乐…...
蓝桥杯真题 - 像素放置 - 题解
题目链接:https://www.lanqiao.cn/problems/3508/learning/ 个人评价:难度 3 星(满星:5) 前置知识:深度优先搜索 整体思路 深搜,在搜索过程中进行剪枝,剪枝有以下限制条件…...
vue基础(三)
常用指令 1. v-bind 固定绑定与动态绑定: 语法: 标准语法:v-bind:属性"动态数据" 简写语法::属性"动态数拓" <!DOCTYPE html> <html lang"en"><head><me…...
使用Python开发PPTX压缩工具
引言 在日常办公中,PPT文件往往因为图片过大而导致文件体积过大,不便于传输和存储。为了应对这一问题,我们可以使用Python的wxPython图形界面库结合python-pptx和Pillow,开发一个简单的PPTX压缩工具。本文将详细介绍如何实现这一…...
ubuntu24.04安装布置ros
最近换电脑布置机器人环境,下了24.04,但是网上的都不太合适,于是自己试着布置好了,留作有需要的人一起看看。 文章目录 目录 前言 一、确认 ROS 发行版名称 二、检查你的 Ubuntu 版本 三、安装正确的 ROS 发行版 四、对于Ubuntu24…...
SQL 秒变 ER 图 sql转er图
🚀SQL 秒变 ER 图,校园小助手神了! 学数据库的宝子们集合🙋♀️ 是不是每次碰到 SQL 转 ER 图就头皮发麻?看着密密麻麻的代码,脑子直接死机,好不容易理清一点头绪,又被复杂的表关…...
【AI知识点】如何判断数据集是否噪声过大?
【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】【AI日记】【读书与思考】【AI应用】 判断数据集是否 噪声过大 是数据分析和机器学习建模过程中至关重要的一步。噪声数据会导致模型难以学习数据的真实模式,从而影响预测效果。以下是一些常见的方法来判断数据…...
网络安全治理架构图 网络安全管理架构
网站安全攻防战 XSS攻击 防御手段: - 消毒。 因为恶意脚本中有一些特殊字符,可以通过转义的方式来进行防范 - HttpOnly 对cookie添加httpOnly属性则脚本不能修改cookie。就能防止恶意脚本篡改cookie 注入攻击 SQL注入攻击需要攻击者对数据库结构有所…...
如何写出优秀的单元测试?
写出优秀的单元测试需要考虑以下几个方面: 1. 测试用例设计 测试用例应该覆盖被测试代码的不同场景和边界情况,以尽可能发现潜在的问题。在设计测试用例时需要关注以下几点: 输入输出数据:要测试的函数或方法可能有多个输入参数…...
数据留痕的方法
在项目中,数据变更时,经常需要记录上次的数据,以便查看对比,专业术语叫做数据留痕。数据变更留痕(即记录数据的变更历史)是一个常见的需求,例如在审计、追踪数据变化或满足合规性要求的场景中。…...
机器学习数学基础:19.线性相关与线性无关
一、线性相关与线性无关的定义 (一)线性相关 想象我们有一组向量,就好比是一群有着不同“力量”和“方向”的小伙伴。给定的向量组 α ⃗ 1 , α ⃗ 2 , ⋯ , α ⃗ m \vec{\alpha}_1, \vec{\alpha}_2, \cdots, \vec{\alpha}_m α 1,α 2…...
ArgoCD实战指南:GitOps驱动下的Kubernetes自动化部署与Helm/Kustomize集成
摘要 ArgoCD 是一种 GitOps 持续交付工具,专为 Kubernetes 设计。它能够自动同步 Git 仓库中的声明性配置,并将其应用到 Kubernetes 集群中。本文将介绍 ArgoCD 的架构、安装步骤,以及如何结合 Helm 和 Kustomize 进行 Kubernetes 自动化部署。 引言 为什么选择 ArgoCD?…...
JVM虚拟机以及跨平台原理
相信大家已经了解到Java具有跨平台的特性,即“一次编译,到处运行”,例如在Windows下编写的程序,无需任何修改就可以在Linux下运行,这是C和C很难做到的。 那么,跨平台是怎样实现的呢?这就要谈及…...
【AIGC提示词系统】基于 DeepSeek R1 + ClaudeAI 易经占卜系统
上篇因为是VIP,这篇来一个免费的 提示词在最下方,喜欢的点个关注吧 引言 在人工智能与传统文化交融的今天,如何让AI系统能够传递传统易经文化的智慧,同时保持易经本身的神秘感和权威性,是一个极具挑战性的课题。本文将…...
电路笔记 : opa 运放失调电压失调电流输入偏置电流 + 反向放大器的平衡电阻 R3 = R1 // R2 以减小输出直流噪声
目录 定义影响和解决失调电压输入偏置电流平衡电阻R3推导公式: 失调电流 实际的运算放大器(Op-Amp)存在一些非理想特性,如失调电压(VIO)、失调电流(IIO)和输入偏置电流(I…...
ScrapeGraphAI颠覆传统网络爬虫技术
ScrapeGraphAI颠覆传统网络爬虫技术! 引言 在互联网时代,数据如同油田,丰富而深邃。但如何有效地提取这些数据,仍然是许多开发者面临的艰巨任务。你有没有想过,传统的网络爬虫技术是否已经过时?如今&…...
通过多层混合MTL结构提升股票市场预测的准确性,R²最高为0.98
“Boosting the Accuracy of Stock Market Prediction via Multi-Layer Hybrid MTL Structure” 论文地址:https://arxiv.org/pdf/2501.09760 摘要 本研究引入了一种创新的多层次混合多任务学习架构,致力于提升股市预测的效能。此架构融…...
java将list转成树结构
首先是实体类 public class DwdCusPtlSelectDto {//idprivate String key;//值private String value;//中文名private String title;private List<DwdCusPtlSelectDto> children;private String parentId;public void addChild(DwdCusPtlSelectDto child) {if(this.chil…...
互联网分布式ID解决方案
业界实现方案 1. 基于UUID 2. 基于DB数据库多种模式(自增主键、segment) 3. 基于Redis 4. 基于ZK、ETCD 5. 基于SnowFlake 6. 美团Leaf(DB-Segment、zkSnowFlake) 7. 百度uid-generator() 基于UUID生成唯一ID UUID生成策略 推荐阅读 DDD领域驱动与微服务架构设计设计模…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
链式法则中 复合函数的推导路径 多变量“信息传递路径”
非常好,我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题,统一使用 二重复合函数: z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y)) 来全面说明。我们会展示其全微分形式(偏导…...
