4、缓存数据结构：哈希表与链表在缓存中的角色，LRU（最近最少使用）淘汰策略实现
好，我们进入第四章。这一章要聊的是缓存最核心的骨架——数据结构。说白了，LVGL 的图片缓存到底是怎么把图片存起来、找出来、再踢出去的？全靠哈希表和链表这对黄金搭档。
我记得刚接触嵌入式缓存时，有人跟我说“用数组存图片就行”。嗯，小项目确实能跑，但一旦图片数量上来，查找慢、淘汰乱，系统直接卡成幻灯片。后来我意识到，没有好的数据结构，缓存就是个摆设。
4.1 为什么需要哈希表 + 链表？
先问个问题：缓存需要哪两个核心能力？
- 快速查找：用户要一张图片，你得在 O(1) 时间内找到它。
- 快速淘汰：缓存满了，你得在 O(1) 时间内踢掉最不常用的那张。
数组能做到 O(1) 查找吗？可以，但你要知道下标。链表能做到 O(1) 淘汰吗？可以，但你要知道节点位置。单独用哪个都不完美。所以 LVGL 把两者结合了——哈希表负责查找，双向链表负责淘汰顺序。
核心思想：哈希表存“键值对”的映射，链表存“使用顺序”的队列。两者通过节点指针关联，互不干扰又协同工作。
4.2 哈希表：O(1) 查找的基石
LVGL 的缓存哈希表，本质上是一个固定大小的数组，每个元素是一个链表头（处理哈希冲突用）。
我项目中遇到过一个问题：哈希表太小，冲突严重，查找退化成 O(n)。后来我把表大小设为缓存条目数的 1.5 倍，冲突率才降下来。
4.2.1 哈希函数
LVGL 用图片的 src 指针作为 key。哈希函数很简单：
// 简化版哈希计算
uint32_t lv_img_cache_hash(const void * src) {
uint32_t hash = (uint32_t)(uintptr_t)src;
hash ^= (hash >> 16);
hash *= 0x85ebca6b;
hash ^= (hash >> 13);
return hash & (cache->table_size - 1);
}嗯，这里要注意：table_size 必须是 2 的幂，这样取模可以用位运算加速。我在 STM32F4 上实测过，位运算比取模快 3 倍以上。
4.2.2 冲突处理
LVGL 采用链地址法。每个哈希桶里挂一个单向链表，冲突的节点都挂上去。
| 哈希桶索引 | 链表节点（按插入顺序） |
|---|---|
| 0 | img_A -> img_D |
| 1 | img_B |
| 2 | （空） |
| 3 | img_C -> img_E -> img_F |
查找时，先算哈希找到桶，再遍历桶内链表比较 src 指针。因为冲突少，链表通常很短，查找还是接近 O(1)。
我的习惯：调试时打印每个桶的链表长度。如果某个桶超过 5 个节点，就该考虑扩容哈希表了。
4.3 双向链表：LRU 淘汰的舞台
哈希表只管“找”，不管“谁该被淘汰”。淘汰逻辑全靠双向链表。
LVGL 维护一个全局的双向链表，所有缓存节点按最近使用时间排序：
- 链表头：最近被访问的图片（最热）
- 链表尾：最久没被访问的图片（最冷）
4.3.1 为什么是双向链表？
因为淘汰时，我们需要 O(1) 删除尾部节点。单向链表删除尾部需要遍历到倒数第二个节点，O(n)。双向链表直接通过 prev 指针找到前驱，一步到位。
// 双向链表节点结构（简化）
typedef struct _lv_img_cache_entry_t {
const void * src; // 图片源指针
lv_img_dsc_t * dec_dsc; // 解码后的图片数据
struct _lv_img_cache_entry_t * prev; // 前驱
struct _lv_img_cache_entry_t * next; // 后继
uint32_t last_access_time; // 最后访问时间戳
} lv_img_cache_entry_t;4.4 LRU 淘汰策略实现
LRU（Least Recently Used）的核心假设：如果一张图片很久没被用过，那它以后被用到的概率也很低。这个假设在 UI 场景下非常准——用户翻页后，上一页的图片基本不会再看了。
4.4.1 访问命中时
当用户请求的图片在缓存中：
- 通过哈希表找到节点
- 把节点从链表中当前位置移除
- 把节点插入到链表头部
- 更新
last_access_time
这个过程叫“提升到头部”。我习惯叫它“热数据上浮”。
4.4.2 缓存未命中且已满时
当缓存满了，需要腾空间：
- 取链表尾部节点（最久未使用）
- 从哈希表中删除该节点的映射
- 从链表中删除该节点
- 释放图片数据内存
- 把新图片节点插入链表头部，并加入哈希表
我曾经踩过的坑：在中断服务函数里直接操作 LRU 链表。双向链表操作不是原子的，中断嵌套会导致链表指针错乱。后来我加了互斥锁，或者把缓存操作放到任务级代码中执行。
4.5 完整流程图
下面这张图展示了 LVGL 图片缓存的完整数据流：
4.6 性能对比：哈希表 vs 链表 vs 数组
| 操作 | 哈希表 | 双向链表 | 数组 |
|---|---|---|---|
| 查找 | O(1) 平均 | O(n) | O(n) 或 O(log n) 排序后 |
| 插入头部 | O(1) | O(1) | O(n) 需移动元素 |
| 删除尾部 | O(1) 需先找到 | O(1) | O(1) 但需标记 |
| 删除任意节点 | O(1) 已知节点 | O(1) 已知节点 | O(n) |
| 内存开销 | 中等（桶数组+链表） | 低（仅节点指针） | 最低 |
你看，哈希表和链表正好互补。哈希表查得快但不管顺序，链表管顺序但查得慢。合在一起，各司其职。
实际调优建议：LVGL 默认缓存条目数是 8 或 16。如果你的 UI 有 20 张以上图片轮播，建议调大 LV_IMG_CACHE_DEF_SIZE。我一般设为图片总数的 1.2 倍，留点余量。
4.7 避坑指南
最后分享几个我踩过的坑：
- 哈希表与链表不同步：删除节点时，一定要先从哈希表移除映射，再从链表摘除节点。顺序反了会导致哈希表指向已释放内存。
- 时间戳溢出：
last_access_time用 32 位无符号整数，系统运行几个月后会溢出。我改用相对时间戳（系统启动后的毫秒数），并定期重置。 - 多任务并发：LVGL 默认是单线程，但如果你在 RTOS 中多个任务访问缓存，必须加锁。我习惯用
lv_mutex_lock包裹整个查找+提升操作。