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

每日一题——LRU缓存机制的C语言实现详解

LRU缓存机制的C语言实现详解

    • 参考
    • 1. 数据结构设计
      • 双向链表节点
      • 哈希表节点
      • 哈希表
      • LRU缓存结构
    • 2. 初始化哈希表和双向链表
      • 哈希函数
      • 初始化哈希表
      • 初始化双向链表
      • 创建LRU缓存
    • 3. 更新双向链表
    • 4. 实现Get操作
    • 5. 实现Put操作
      • 更新节点值
      • 删除最久未使用节点
      • 插入或更新节点
    • 6. 释放缓存
      • 释放双向链表
      • 释放哈希表
      • 释放LRU缓存
    • 7. 完整代码及测试
      • 测试用例
      • 输出结果
    • 总结

参考

建议先参考下面的视频

在这里插入图片描述

1. 数据结构设计

双向链表节点

typedef struct DulNode {int key;           // 缓存项的键int value;         // 缓存项的值struct DulNode* pre;  // 前驱节点指针struct DulNode* next; // 后继节点指针
} DulNode;
  • 作用:维护缓存项的使用顺序,最近访问的节点靠近链表头部,未使用的节点靠近尾部。

哈希表节点

typedef struct HashTableNode {DulNode* node;          // 指向双向链表中的节点struct HashTableNode* next; // 处理哈希冲突的链表指针
} HashTableNode;
  • 作用:通过哈希表快速定位缓存项,键为key,值为对应的双向链表节点。

哈希表

typedef struct HashTable {int capacity;         // 哈希表容量(桶数量)hash_cal_f hash_func; // 哈希函数指针HashTableNode** bucket; // 桶数组(存储链表头节点)
} HashTable;
  • 作用:以O(1)时间复杂度查找键是否存在,结合双向链表实现LRU策略。

LRU缓存结构

typedef struct {int cur_node;       // 当前缓存中的节点数HashTable* hash_table; // 哈希表DulNode* head;      // 双向链表头节点(哨兵)DulNode* tail;      // 双向链表尾节点(哨兵)
} Solution;
  • 作用:整合哈希表和双向链表,封装LRU缓存的核心操作。

2. 初始化哈希表和双向链表

哈希函数

int hash_cal(int capacity, int val) {return val % capacity; // 简单取模哈希
}
  • 设计意图:将键值映射到哈希表的桶索引,均匀分布以减少冲突。

初始化哈希表

void InitHashTable(Solution* lruCache, int capacity) {HashTable* hash_table = malloc(sizeof(HashTable));hash_table->capacity = capacity;hash_table->hash_func = hash_cal;hash_table->bucket = calloc(capacity, sizeof(HashTableNode*));lruCache->hash_table = hash_table;
}
  • 关键点:动态分配桶数组并初始化为NULL,避免野指针问题。

初始化双向链表

void InitDoubleList(Solution* lruCache) {// 创建头尾哨兵节点并连接成环lruCache->head = (DulNode*)malloc(sizeof(DulNode));lruCache->tail = (DulNode*)malloc(sizeof(DulNode));lruCache->head->pre = lruCache->tail;lruCache->head->next = lruCache->tail;lruCache->tail->pre = lruCache->head;lruCache->tail->next = lruCache->head;
}
  • 设计优势:哨兵节点简化链表操作,无需处理头尾边界条件。

创建LRU缓存

Solution* SolutionCreate(int capacity) {Solution* lruCache = malloc(sizeof(Solution));lruCache->cur_node = 0;InitHashTable(lruCache, capacity);InitDoubleList(lruCache);return lruCache;
}
  • 流程:分配内存后,初始化哈希表和双向链表。

3. 更新双向链表

void DulLinkLinkUpdateNode(DulNode* head, DulNode* node) {if (node->pre == head) return; // 已在头部无需处理// 摘除节点node->pre->next = node->next;node->next->pre = node->pre;// 插入到头部node->pre = head;node->next = head->next;head->next->pre = node;head->next = node;
}
  • 作用:将节点移动到链表头部,表示最近被访问。

4. 实现Get操作

int SolutionGet(Solution* obj, int key) {if (obj->cur_node == 0) return -1;int h_index = obj->hash_table->hash_func(obj->hash_table->capacity, key);HashTableNode* hash_node = obj->hash_table->bucket[h_index];// 遍历哈希冲突链表while (hash_node && hash_node->node->key != key) hash_node = hash_node->next;if (hash_node) {DulLinkLinkUpdateNode(obj->head, hash_node->node); // 更新链表return hash_node->node->value;}return -1;
}
  • 时间复杂度:O(1)(哈希表平均情况)。

5. 实现Put操作

更新节点值

void LRUCacheUpdateNode(Solution* obj, int key, int value) {// 查找并更新值,随后移动节点到头部int h_index = obj->hash_table->hash_func(obj->hash_table->capacity, key);HashTableNode* hash_node = obj->hash_table->bucket[h_index];while (hash_node && hash_node->node->key != key) hash_node = hash_node->next;if (hash_node) {hash_node->node->value = value;DulLinkLinkUpdateNode(obj->head, hash_node->node);}
}

删除最久未使用节点

void LRUCacheDelLastNode(Solution* obj) {DulNode* del_node = obj->tail->pre; // 尾节点的前驱为LRU节点// 从哈希表中删除int h_index = obj->hash_table->hash_func(obj->hash_table->capacity, del_node->key);HashTableNode *pre = NULL, *cur = obj->hash_table->bucket[h_index];while (cur && cur->node->key != del_node->key) {pre = cur;cur = cur->next;}if (cur) {if (pre) pre->next = cur->next;else obj->hash_table->bucket[h_index] = cur->next;free(cur);}// 从链表中删除del_node->pre->next = del_node->next;del_node->next->pre = del_node->pre;free(del_node);obj->cur_node--;
}

插入或更新节点

void SolutionPut(Solution* obj, int key, int value) {if (obj->cur_node >= obj->hash_table->capacity)LRUCacheDelLastNode(obj); // 缓存满时删除LRU节点if (SolutionGet(obj, key) != -1) { // Key存在则更新LRUCacheUpdateNode(obj, key, value);return;}// 创建新节点并插入链表头部DulNode* new_dul_node = malloc(sizeof(DulNode));new_dul_node->key = key;new_dul_node->value = value;new_dul_node->pre = obj->head;new_dul_node->next = obj->head->next;obj->head->next->pre = new_dul_node;obj->head->next = new_dul_node;// 插入哈希表HashTableNode* new_hash_node = malloc(sizeof(HashTableNode));new_hash_node->node = new_dul_node;int h_index = obj->hash_table->hash_func(obj->hash_table->capacity, key);new_hash_node->next = obj->hash_table->bucket[h_index];obj->hash_table->bucket[h_index] = new_hash_node; // 头插法obj->cur_node++;
}

6. 释放缓存

释放双向链表

void DulLinkLinkFree(DulNode* head) {DulNode* cur = head->next;while (cur != head) {DulNode* tmp = cur;cur = cur->next;free(tmp);}free(head->pre); // 释放尾节点free(head);
}

释放哈希表

void HashTableNodeFree(Solution* obj) {for (int i = 0; i < obj->hash_table->capacity; i++) {HashTableNode* cur = obj->hash_table->bucket[i];while (cur) {HashTableNode* tmp = cur;cur = cur->next;free(tmp);}}free(obj->hash_table->bucket);
}

释放LRU缓存

void SolutionFree(Solution* obj) {DulLinkLinkFree(obj->head);HashTableNodeFree(obj);free(obj->hash_table);free(obj);
}

7. 完整代码及测试

测试用例

int main() {Solution* cache = SolutionCreate(2);SolutionPut(cache, 1, 1);SolutionPut(cache, 2, 2);printf("Get(1) -> %d\n", SolutionGet(cache, 1)); // 1SolutionPut(cache, 3, 3); // 淘汰2printf("Get(2) -> %d\n", SolutionGet(cache, 2)); // -1SolutionFree(cache);return 0;
}

输出结果

Get(1) -> 1
Get(2) -> -1

总结

  • 核心机制:通过双向链表维护访问顺序,哈希表实现快速查找。
  • 时间复杂度GetPut操作均摊时间复杂度为O(1)。
  • 优化点:哈希表采用链地址法处理冲突,双向链表使用哨兵节点简化操作。
  • 适用场景:高频访问的缓存系统,需快速淘汰最久未使用数据。
    反正以我的能力远远不能解决问题。还是只能勉强把代码看懂。这题还是很难得,感觉没有一天时间,完全搞不定。放弃了,放弃了。

相关文章:

每日一题——LRU缓存机制的C语言实现详解

LRU缓存机制的C语言实现详解 参考1. 数据结构设计双向链表节点哈希表节点哈希表LRU缓存结构 2. 初始化哈希表和双向链表哈希函数初始化哈希表初始化双向链表创建LRU缓存 3. 更新双向链表4. 实现Get操作5. 实现Put操作更新节点值删除最久未使用节点插入或更新节点 6. 释放缓存释…...

Leetcode3162:优质数对的总数 I

题目描述&#xff1a; 给你两个整数数组 nums1 和 nums2&#xff0c;长度分别为 n 和 m。同时给你一个正整数 k。 如果 nums1[i] 可以除尽 nums2[j] * k&#xff0c;则称数对 (i, j) 为 优质数对&#xff08;0 < i < n - 1, 0 < j < m - 1&#xff09;。 返回 优…...

docker安装etcd:docker离线安装etcd、docker在线安装etcd、etcd镜像下载、etcd配置详解、etcd常用命令、安装常见问题总结

官方网站 官方网址&#xff1a;etcd 二进制包下载&#xff1a;Install | etcd GitHub社区项目&#xff1a;etcd-io GitHub GitHub社区项目版本历史&#xff1a;Releases etcd-io/etcd GitHub 一、镜像下载 1、在线下载 在一台能连外网的linux上执行docker镜像拉取命令…...

Apache SeaTunnel 构建实时数据同步管道(最新版)

文章作者 王海林 白鲸开源 数据集成引擎研发 Apache SeaTunnel Committer & PMC Member&#xff0c;Apache SkyWalking Committer&#xff0c;多年平台研发经验&#xff0c;目前专注于数据集成领域。 导读 在当今数字化快速发展的时代&#xff0c;数据已然成为企业决策…...

递归、搜索与回溯第二讲:二叉树中的深搜 穷举vs暴搜vs深搜vs回溯vs剪枝

递归、搜索与回溯第二讲&#xff1a;二叉树中的深搜 && 穷举vs暴搜vs深搜vs回溯vs剪枝 1.计算布尔二叉树的值2.求根节点到叶结点数字之和3.二叉树剪枝4.验证二叉搜索树5.二叉搜索树中第K小的元素6.二叉树的所有路径7.全排列8.子集 1.计算布尔二叉树的值 2.求根节点到叶…...

Hbase分布式——储存机制

说明&#xff1a; 客户端调用&#xff0c;到达zk。然后到大HMaster&#xff08;主节点可以有多个但是只有和active在一起的才有效。&#xff09;。然后找到一个HRegionServer&#xff08;从节点可以有多个&#xff09;去做保存操作。 每一个HRegionServer上管理着表的HRegion…...

Word表格中如何只单独调整某一单元格宽度

大家好&#xff0c;我是小鱼。 在日常制作Word表格时&#xff0c;表格中不同单元格有时需要设置不同的宽度&#xff0c;但是很多小伙伴会发现想单独调整某一个单元格宽度时&#xff0c;发现其它单元格宽度也会发生变化。那么&#xff0c;到底怎么才能单独调整某一单元格宽度呢…...

Build错误:Cannot determine build data storage root for project 和 无法加载主类的解决办法的经验分享

Build错误&#xff1a;Cannot determine build data storage root for project 解决方案与经验分享 1. 引言 查看错误信息 “Cannot determine build data storage root for project”的含义&#xff1a; 这是一个关于构建项目时遇到的常见错误。错误信息表明构建工具无法确定…...

【Springboot知识】Logback从1.2.x升级到1.3.x需要注意哪些点?

文章目录 **1. 确认依赖版本**示例依赖配置&#xff08;Maven&#xff09;&#xff1a; **2. 处理 StaticLoggerBinder 的移除**解决方案&#xff1a; **3. 修改日志配置文件**示例 logback.xml 配置&#xff1a; **4. 检查兼容性问题**Spring Boot 2.x 的兼容性解决方案&#…...

大语言加持的闭环端到端自动驾驶模型 学习笔记纯干货

LMDrive&#xff1a;大语言模型辅助闭环端到端 LMDrive&#xff1a;大语言模型辅助闭环端到端 背景框架输入部分&#xff1a;导航指令&#xff1a;视觉数据&#xff1a;提示指令&#xff08;可选&#xff09;&#xff1a;处理部分&#xff1a;输出部分&#xff1a; 视觉编码器…...

初阶数据结构(C语言实现)——2算法的时间复杂度和空间复杂度

目录 本节目标1. 算法效率1.1 如何衡量一个算法的好坏1.2 算法的复杂度 2.时间复杂度2.1 时间复杂度的概念2.1.1 入门习题2.1.2 进阶习题 2.2 常见时间复杂度 3. 空间复杂度3.1 常见空间复杂度 本节目标 算法效率时间复杂度空间复杂度常见时间复杂度以及复杂度oj练习 1. 算法…...

MySQL知识

1.Navicat客户端连接 打开navicat&#xff0c;点击连接&#xff0c;点击MySQL 输入连接名与密码&#xff0c;如果连接的mysql是windows下的mysql主机号就填写localhost 填写好后点击测试连接 点击确定&#xff0c;mysql连接navicat成功 2.MySQL数据定义语言(DDL) DDL用于数据库…...

【前端定位线上问题的多种方案(不依赖 Sentry)】

前端定位线上问题的多种方案&#xff08;不依赖 Sentry&#xff09; &#x1f6e0;️ 一、构建时注入调试信息 &#x1f527; 1. 注入版本信息与 Git 提交哈希 Webpack 配置&#xff1a; // webpack.config.js const webpack require(webpack); const gitRevision require(…...

怎么修改node_modules里的文件,怎么使用patch-package修改node_modules的文件,怎么修改第三方库原文件。

在开发中会遇到需要node_modules里第三方库有bug&#xff0c;然后需要修改node_modules文件的情况 使用patch-package包可以修改node_modules里的文件 patch-package npm 官网&#xff1a;patch-package - npm 安装 npm i patch-package 修改文件后 npx patch-package s…...

muduo网络库2

Muduo网络库&#xff1a;底层实质上为Linux的epoll pthread线程池&#xff0c;且依赖boost库。 muduo的网络设计核心为一个线程一个事件循环&#xff0c;有一个main Reactor负载accept连接&#xff0c;然后把连接分发到某个sub Reactor(采用轮询的方式来选择sub Reactor)&…...

什么是DrawCall?DrawCall为什么会影响游戏运行效率?如何减少DrawCall?

目录 1 什么是DrawCall&#xff1f; 2 DrawCall为什么会影响游戏运行效率&#xff1f; 3 如何减少 DrawCall&#xff1f;&#xff08;结合性能分析工具&#xff09; 1 什么是DrawCall&#xff1f; DrawCall&#xff08;绘制调用&#xff09; 是 GPU 的一个指令&#xff0c…...

LabVIEW电能质量分析软件

随着电力系统的复杂性增加&#xff0c;电能质量问题日益突出&#xff0c;传统的电能质量检测装置多采用DSP技术&#xff0c;不仅开发周期长、功能单一&#xff0c;而且在多功能集成方面存在局限性。基于LabVIEW虚拟仪器开发平台的电能质量分析软件利用FFT、STFT、WT、HHT等多种…...

【十二】Golang 映射

&#x1f4a2;欢迎来到张胤尘的开源技术站 &#x1f4a5;开源如江河&#xff0c;汇聚众志成。代码似星辰&#xff0c;照亮行征程。开源精神长&#xff0c;传承永不忘。携手共前行&#xff0c;未来更辉煌&#x1f4a5; 文章目录 映射映射的定义映射初始化make 函数使用字面量 源…...

PHP商协会管理系统小程序源码

&#x1f4ca; 商协会管理系统 &#x1f4bb; 这是一款基于ThinkPHPUniapp框架&#xff0c;经过深度定制与匠心打造的商协会系统&#xff0c;被誉为商协会领域数字化运营管理的新锐之星。它以“智慧化会员体系、智敏化内容运营、智能化活动构建”为三大核心动力源&#xff0c;…...

React进阶之React核心源码解析(三)

React核心源码解析 diff多节点比较diff两轮遍历比较第一轮比较第二轮比较Update 状态更新Concurrent Modediff 多节点比较diff isArray方法比较 节点更新// 更新前 <ul><li key="0" className="before">0<li><li key=...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...