从搬盘子到缓存管理：用 Java 理解汉诺塔、令牌桶、HashCode 与 LFU

作者逆境不可逃技术永无止境希望我的内容可以帮助到你有些编程知识直接看定义和代码会觉得抽象但换一个生活场景就容易理解了。比如如何借助空位搬动一摞盘子景区怎样控制游客进入的速度图书馆怎样根据书名快速找到书书桌放满了应该把哪本书收进柜子这些问题分别可以帮助我们理解汉诺塔、令牌桶、哈希和 LFU 缓存。它们并不都属于同一种算法汉诺塔体现递归思想令牌桶用于限流HashCode 负责哈希计算LFU 则是一种缓存淘汰策略。下面从这些场景出发用 Java 实现它们。一、汉诺塔怎样搬动一摞大小不同的盘子1. 从搬盘子开始假设桌上有 A、B、C 三个位置。A 上放着一摞盘子大盘在下面小盘在上面。现在需要把所有盘子搬到 C但必须遵守每次只能拿最上面的一个盘子。大盘不能放到小盘上面。可以借用 B 暂存盘子。如果只有一个盘子直接从 A 搬到 C 就行。如果有三个盘子怎样才能搬动最下面的最大盘必须先把上面两个盘子移开。因此整个过程可以拆成三步把上面两个盘子从 A 搬到 B。把最大盘从 A 搬到 C。把 B 上的两个盘子搬到 C。2. 递归是怎么出现的把“三个盘子”换成n个道理仍然成立先搬走上面的n - 1个再搬最大的最后把那n - 1个搬到目标位置。而“搬动n - 1个盘子”又是相同的问题只是规模更小。这就是递归用规模更小的同类问题解决当前问题。3. Java 实现下面使用列表表示柱子列表末尾就是柱子顶部。import java.util.List; class Solution { public void hanota(ListInteger A, ListInteger B, ListInteger C) { move(A.size(), A, B, C); } // 将 n 个盘子从 from 移到 tohelp 用于暂存 private void move(int n, ListInteger from, ListInteger help, ListInteger to) { // 没有盘子需要移动 if (n 0) { return; } // 先把上面的 n - 1 个盘子搬到辅助位置 move(n - 1, from, to, help); // 再搬动最大的盘子 to.add(from.remove(from.size() - 1)); // 最后把辅助位置的盘子搬到目标位置 move(n - 1, help, from, to); } }4. 为什么参数会交换位置方法的参数含义始终是move(数量, 起点, 辅助位置, 终点);例如move(n - 1, from, to, help);这一次的目标是把盘子搬到help所以它放在最后一个参数的位置而原来的to暂时充当辅助位置。位置本身没有改变改变的是它们在当前任务中的角色。在三根柱子的规则下移动n个盘子至少需要2^n - 1次。假设柱顶操作为常数时间算法时间复杂度为O(2^n)递归栈空间为O(n)。二、令牌桶景区如何控制游客进入速度1. 给每个游客发一张通行证假设景区入口有一个盒子里面放着通行证盒子最多装 10 张。每秒补充 2 张。每位游客进入时必须取走一张。没有通行证就暂时不能进入。这就是令牌桶的基本思路。在程序中游客对应请求通行证对应令牌。2. 为什么既需要容量又需要补充速度如果景区一段时间没人来盒子里就能积累通行证但最多只有 10 张。此时突然来了 10 位游客他们可以立即进入。通行证用完以后就要等待新的通行证生成持续放行的长期平均速度受到每秒 2 张的限制。因此桶容量决定能够应对多大的瞬时突发流量。补充速度决定长期平均放行速度。3. 不必真的不断往桶里放令牌程序可以在每次请求到达时计算距离上次补充过去了多久新增令牌数 经过的秒数 × 每秒生成速度例如每秒生成 2 个令牌过去了 0.5 秒就应该增加 1 个令牌。补充后的数量不能超过容量当前令牌数 min(桶容量, 原有令牌数 新增令牌数)这样就不需要专门启动一个线程不断执行补充操作。4. Java 实现public class TokenBucket { // 桶最多保存多少个令牌 private final int capacity; // 每秒生成多少个令牌 private final double refillRate; // 当前令牌数保留小数部分以积累补充进度 private double tokens; // 上一次计算的时间 private long lastRefillTime; public TokenBucket(int capacity, double refillRate) { if (capacity 0 || !Double.isFinite(refillRate) || refillRate 0) { throw new IllegalArgumentException( 容量和生成速度必须合法且大于 0 ); } this.capacity capacity; this.refillRate refillRate; this.tokens capacity; this.lastRefillTime System.nanoTime(); } // 尝试拿走一个令牌失败时立即返回 false public synchronized boolean tryAcquire() { long now System.nanoTime(); // 将经过的纳秒数换算成秒 double seconds (now - lastRefillTime) / 1_000_000_000.0; // 根据时间补充令牌但不能超过容量 tokens Math.min( capacity, tokens seconds * refillRate ); lastRefillTime now; if (tokens 1) { return false; } // 放行一个请求扣除一个令牌 tokens--; return true; } }5. 代码中的几个细节double tokens用于保留不足一个令牌的进度。例如每秒生成 1 个令牌过去 0.3 秒就积累了 0.3 个令牌。System.nanoTime()用于计算时间间隔其返回值不能直接当作日期时间使用。synchronized则保证“补充、判断、扣除”作为一个整体执行避免两个线程同时看到只剩一个令牌却都通过检查。这段代码适合同一个进程内共享一个桶的情况。多个服务实例如果各自创建桶也就各自拥有一份额度需要全局限流时还需要共享状态和原子更新机制。三、HashCode怎样根据书名快速找到书1. 给书名计算一个编号假设图书馆有很多书柜。每次找书都从头翻一遍效率很低。我们可以先根据书名计算一个整数再根据这个整数确定要去哪个柜子查找。哈希计算就像一个“编号计算器”输入对象的信息计算出一个整数。但这个编号并不保证唯一不同书名也可能算出同一个编号。Java 的hashCode()返回的就是这样的哈希值。不同类可以采用不同的计算方式下面以字符串为例。2. String 如何计算哈希值字符串哈希的核心规则是hash 31 * hash 当前字符;下面是说明计算规则的简化实现省略了 JDK 中的缓存等优化public class StringHashDemo { public static int stringHash(String s) { int hash 0; for (int i 0; i s.length(); i) { // 让之前的字符和当前字符共同参与计算 hash 31 * hash s.charAt(i); } return hash; } }以abc为例当前字符计算过程结果a0 × 31 9797b97 × 31 983105c3105 × 31 9996354展开后就是a × 31² b × 31 c这样字符内容和排列顺序都会影响结果。计算可能发生int溢出Java 会保留结果的低 32 位这是该计算规则的一部分。3. 为什么使用 3131 是一个较小的奇质数是字符串哈希中常用的乘数选择。同时31 × x 32 × x - x所以也可以写成(x 5) - x编译器可以进行相关优化平时直接写31 * x即可。不过选择 31 并不意味着能消除哈希冲突。4. 有了编号HashMap 为什么还要再处理一次HashMap 会对对象的原始哈希值做一次高低位混合。其常见逻辑可以拆开理解为static int spreadHash(Object key) { if (key null) { return 0; } int h key.hashCode(); // 将高 16 位的信息混合到低 16 位 return h ^ (h 16); }这是因为 HashMap 定位数组桶时使用类似下面的计算int index (table.length - 1) hash;当数组长度为 16 时下标只取决于哈希值的低 4 位。可以类比成图书馆分配书柜时只看编号的末尾几位。如果许多编号末尾相同即使前面不同也会挤到同一个柜子。通过h ^ (h 16)高位信息也能影响低位有助于缓解部分碰撞情况。5. 编号相同不代表是同一本书例如Aa.hashCode() // 2112 BB.hashCode() // 2112两个字符串内容不同但哈希值相同。因此在 HashMap 中哈希值帮助缩小查找范围后续还需要比较 key 是否相等。必须满足的规则是equals()相等的对象hashCode()必须相同hashCode()相同的对象不一定相等。四、LFU书桌满了应该收走哪本书1. 把书桌理解成缓存假设书柜很大但书桌只能放两本书。经常看的书放在桌上拿起来方便其他书放在柜子里需要时再取。这就像缓存书桌空间有限但访问方便。书柜能存更多内容但取用成本较高。想在桌上放一本新书可能需要先收走一本旧书。LFU 的策略是优先收走使用次数最少的书次数相同时收走最久没有使用的那本。2. 看一个例子假设缓存容量为 2操作当前频率结果put(1, 10)key11 次放入第一条数据put(2, 20)key11 次key21 次缓存已满get(1)key12 次key21 次key1 频率增加put(3, 30)key12 次key31 次淘汰 key2下面采用的规则是新数据频率为 1成功读取和更新已有数据都会让频率加一。3. 怎样快速找到该淘汰的数据需要三个核心结构结构作用cache根据 key 快速找到节点groups按频率分组并记录组内的新旧顺序minFreq记录当前最小频率可以把不同频率理解成不同的房间频率为 1 的数据在 1 号房间频率为 2 的在 2 号房间。每次访问就把数据搬到下一间房的队尾。淘汰时找到编号最小的房间移除队首的数据。4. Java 实现import java.util.HashMap; import java.util.LinkedHashSet; import java.util.Map; class LFUCache { private static class Node { int key; int value; int freq 1; // 新节点的频率从 1 开始 Node(int key, int value) { this.key key; this.value value; } } private final int capacity; // key - 节点 private final MapInteger, Node cache new HashMap(); // 频率 - 按访问先后排列的 key private final MapInteger, LinkedHashSetInteger groups new HashMap(); private int minFreq 0; public LFUCache(int capacity) { this.capacity capacity; } public int get(int key) { Node node cache.get(key); if (node null) { return -1; } // 访问成功频率加一 increaseFreq(node); return node.value; } public void put(int key, int value) { if (capacity 0) { return; } Node node cache.get(key); // 更新已有节点也算一次使用 if (node ! null) { node.value value; increaseFreq(node); return; } // 缓存已满淘汰最低频率组中最久没使用的 key if (cache.size() capacity) { LinkedHashSetInteger keys groups.get(minFreq); int removedKey keys.iterator().next(); keys.remove(removedKey); cache.remove(removedKey); if (keys.isEmpty()) { groups.remove(minFreq); } } // 新节点加入频率为 1 的分组 cache.put(key, new Node(key, value)); groups.computeIfAbsent( 1, k - new LinkedHashSet() ).add(key); minFreq 1; } private void increaseFreq(Node node) { int oldFreq node.freq; // 从旧频率组移除 LinkedHashSetInteger oldKeys groups.get(oldFreq); oldKeys.remove(node.key); if (oldKeys.isEmpty()) { groups.remove(oldFreq); // 当前节点即将进入 oldFreq 1 if (minFreq oldFreq) { minFreq; } } // 进入新频率组末尾表示刚刚使用过 node.freq; groups.computeIfAbsent( node.freq, k - new LinkedHashSet() ).add(node.key); } }5. 为什么使用 LinkedHashSet它既不允许重复 key又保留插入顺序。每个节点被访问后都会离开旧分组进入新分组的末尾。因此同一频率组中排在最前面的就是最久没有使用的节点。keys.iterator().next();可以直接取出这个节点的 key。6. 为什么最小频率可以直接加一假设最小频率为 2而且这个组只剩一个节点。访问该节点后频率为 2 的组变空。当前节点的频率变成 3。缓存中原本就没有频率小于 2 的节点。因此新的最小频率一定是 3可以直接执行minFreq。这个结论依赖于“节点频率恰好增加一”不能套用到任意删除操作中。在哈希操作平均为常数时间的前提下这个实现的get()和put()都是平均O(1)空间复杂度为O(capacity)。7. LFU 也有不擅长的情况回到书桌的例子一本书以前看了很多次但最近已经不再需要它仍然可能因为累计次数很高而留在桌上。这说明 LFU 更重视历史使用频率对兴趣突然变化的反应可能较慢。实际选择缓存策略时还要考虑访问模式不能只看一种规则是否容易实现。五、生活场景背后的编程思想场景对应知识核心思想借助空位搬盘子汉诺塔把大问题拆成规模更小的同类问题使用通行证控制入场令牌桶将经过的时间转换成可用额度根据书名计算检索编号HashCode通过哈希值缩小查找范围从书桌收走不常看的书LFU根据使用频率管理有限空间这些类比能帮助我们理解设计动机但真正写代码时还需要明确规则盘子能怎样移动、令牌如何补充、哈希冲突怎样处理、频率相同时淘汰谁。规则一旦明确变量和数据结构的作用也就更容易理解了。