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

从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判断的性能困局

【前言】   本文将以哈希表重构实战为核心&#xff0c;完整展示如何将传统条件匹配逻辑(上千层if-else判断)转化为O(1)的哈希表高效实现。通过指纹验证场景的代码级解剖&#xff0c;您将深入理解&#xff1a;   1.哈希函数设计如何规避冲突陷阱   2.链式寻址法的工程实现…...

视频采集卡接口

采集卡的正面有MIC IN、LINE IN以及AUDIO OUT三个接口&#xff0c; MIC IN为麦克风输入&#xff0c;我们如果要给采集到的视频实时配音或者是在直播的时候进行讲解&#xff0c;就可以在这里插入一个麦克风&#xff0c; LINE IN为音频线路输入&#xff0c;可以外接播放背景音乐…...

蓝桥杯真题 - 像素放置 - 题解

题目链接&#xff1a;https://www.lanqiao.cn/problems/3508/learning/ 个人评价&#xff1a;难度 3 星&#xff08;满星&#xff1a;5&#xff09; 前置知识&#xff1a;深度优先搜索 整体思路 深搜&#xff0c;在搜索过程中进行剪枝&#xff0c;剪枝有以下限制条件&#xf…...

vue基础(三)

常用指令 1. v-bind 固定绑定与动态绑定&#xff1a; 语法&#xff1a; 标准语法&#xff1a;v-bind:属性"动态数据" 简写语法&#xff1a;:属性"动态数拓" <!DOCTYPE html> <html lang"en"><head><me…...

使用Python开发PPTX压缩工具

引言 在日常办公中&#xff0c;PPT文件往往因为图片过大而导致文件体积过大&#xff0c;不便于传输和存储。为了应对这一问题&#xff0c;我们可以使用Python的wxPython图形界面库结合python-pptx和Pillow&#xff0c;开发一个简单的PPTX压缩工具。本文将详细介绍如何实现这一…...

ubuntu24.04安装布置ros

最近换电脑布置机器人环境&#xff0c;下了24.04&#xff0c;但是网上的都不太合适&#xff0c;于是自己试着布置好了&#xff0c;留作有需要的人一起看看。 文章目录 目录 前言 一、确认 ROS 发行版名称 二、检查你的 Ubuntu 版本 三、安装正确的 ROS 发行版 四、对于Ubuntu24…...

SQL 秒变 ER 图 sql转er图

&#x1f680;SQL 秒变 ER 图&#xff0c;校园小助手神了&#xff01; 学数据库的宝子们集合&#x1f64b;‍♀️ 是不是每次碰到 SQL 转 ER 图就头皮发麻&#xff1f;看着密密麻麻的代码&#xff0c;脑子直接死机&#xff0c;好不容易理清一点头绪&#xff0c;又被复杂的表关…...

【AI知识点】如何判断数据集是否噪声过大?

【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】【AI日记】【读书与思考】【AI应用】 判断数据集是否 噪声过大 是数据分析和机器学习建模过程中至关重要的一步。噪声数据会导致模型难以学习数据的真实模式&#xff0c;从而影响预测效果。以下是一些常见的方法来判断数据…...

网络安全治理架构图 网络安全管理架构

网站安全攻防战 XSS攻击 防御手段&#xff1a; - 消毒。 因为恶意脚本中有一些特殊字符&#xff0c;可以通过转义的方式来进行防范 - HttpOnly 对cookie添加httpOnly属性则脚本不能修改cookie。就能防止恶意脚本篡改cookie 注入攻击 SQL注入攻击需要攻击者对数据库结构有所…...

如何写出优秀的单元测试?

写出优秀的单元测试需要考虑以下几个方面&#xff1a; 1. 测试用例设计 测试用例应该覆盖被测试代码的不同场景和边界情况&#xff0c;以尽可能发现潜在的问题。在设计测试用例时需要关注以下几点&#xff1a; 输入输出数据&#xff1a;要测试的函数或方法可能有多个输入参数…...

数据留痕的方法

在项目中&#xff0c;数据变更时&#xff0c;经常需要记录上次的数据&#xff0c;以便查看对比&#xff0c;专业术语叫做数据留痕。数据变更留痕&#xff08;即记录数据的变更历史&#xff09;是一个常见的需求&#xff0c;例如在审计、追踪数据变化或满足合规性要求的场景中。…...

机器学习数学基础:19.线性相关与线性无关

一、线性相关与线性无关的定义 &#xff08;一&#xff09;线性相关 想象我们有一组向量&#xff0c;就好比是一群有着不同“力量”和“方向”的小伙伴。给定的向量组 α ⃗ 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具有跨平台的特性&#xff0c;即“一次编译&#xff0c;到处运行”&#xff0c;例如在Windows下编写的程序&#xff0c;无需任何修改就可以在Linux下运行&#xff0c;这是C和C很难做到的。 那么&#xff0c;跨平台是怎样实现的呢&#xff1f;这就要谈及…...

【AIGC提示词系统】基于 DeepSeek R1 + ClaudeAI 易经占卜系统

上篇因为是VIP&#xff0c;这篇来一个免费的 提示词在最下方&#xff0c;喜欢的点个关注吧 引言 在人工智能与传统文化交融的今天&#xff0c;如何让AI系统能够传递传统易经文化的智慧&#xff0c;同时保持易经本身的神秘感和权威性&#xff0c;是一个极具挑战性的课题。本文将…...

电路笔记 : opa 运放失调电压失调电流输入偏置电流 + 反向放大器的平衡电阻 R3 = R1 // R2 以减小输出直流噪声

目录 定义影响和解决失调电压输入偏置电流平衡电阻R3推导公式&#xff1a; 失调电流 实际的运算放大器&#xff08;Op-Amp&#xff09;存在一些非理想特性&#xff0c;如失调电压&#xff08;VIO&#xff09;、失调电流&#xff08;IIO&#xff09;和输入偏置电流&#xff08;I…...

ScrapeGraphAI颠覆传统网络爬虫技术

ScrapeGraphAI颠覆传统网络爬虫技术&#xff01; 引言 在互联网时代&#xff0c;数据如同油田&#xff0c;丰富而深邃。但如何有效地提取这些数据&#xff0c;仍然是许多开发者面临的艰巨任务。你有没有想过&#xff0c;传统的网络爬虫技术是否已经过时&#xff1f;如今&…...

通过多层混合MTL结构提升股票市场预测的准确性,R²最高为0.98

“Boosting the Accuracy of Stock Market Prediction via Multi-Layer Hybrid MTL Structure” 论文地址&#xff1a;https://arxiv.org/pdf/2501.09760 ​​​​​​​ 摘要 本研究引入了一种创新的多层次混合多任务学习架构&#xff0c;致力于提升股市预测的效能。此架构融…...

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领域驱动与微服务架构设计设计模…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...