Tag: 数据结构
All the articles with the tag "数据结构".
-
字母异位词分组——HashMap处理集合分组的经典模式
利用规范表示作为 HashMap 的 key，将字母异位词归为等价类，揭示分组问题的通用模式。
-
LRU缓存——HashMap+双向链表实现O(1)淘汰
HashMap 快速查找+双向链表维护访问顺序，实现 O(1)级 LRU 缓存淘汰，虚拟头尾节点简化边界操作
-
页面置换算法——从OPT到LRU到Clock的演进
从 OPT 的理论下界到 Clock 的工程实现，Clock 算法用硬件访问位和环形指针以 O(1)复杂度近似 LRU 效果。
-
布隆过滤器的双重哈希技巧
通过一次 MurmurHash3 调用的高低 32 位做线性组合，模拟 k 个独立哈希函数的效果。
-
布隆过滤器 vs 布谷鸟过滤器——为什么布隆过滤器不支持删除？
布隆过滤器位数组共享导致不可删除，布谷鸟过滤器用 XOR 可逆指纹实现双向定位与删除。
-
Redis 淘汰策略详解：LRU 与 LFU
对比 Redis 八种内存淘汰策略，重点剖析近似 LRU 随机采样算法与 LFU 对数计数器+时间衰减的精妙设计，以及三者关键参数调优指南。
-
HashMap的哈希扰动与扩容机制
HashMap 用 h^(h>>>16) 扰动让高位参与桶定位，扩容时 hash&oldCap 一次位运算决定节点去留，尾插法消除 JDK7 死循环。
-
ConcurrentHashMap——从JDK7分段锁到JDK8桶级锁
JDK 8 ConcurrentHashMap 以桶头节点 synchronized + CAS 空桶替代 JDK 7 分段锁，多线程协助扩容，ForwardingNode 让读操作对扩容透明。