从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领域驱动与微服务架构设计设计模…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
