设计一个基于哈希的日志速率限制器

1. 问题描述

我们需要设计一个日志速率限制器，用于限制系统在固定时间窗口内打印相同消息的频率。具体要求如下：

• 系统会收到一系列带有时间戳的日志消息。
• 如果某条消息在最近 10 秒内没有被打印过，则打印该消息，并记录时间戳。
• 如果该消息在最近 10 秒内已经被打印过，则忽略这条消息，不打印。

我们需要实现一个类 Logger，包含一个方法 shouldPrintMessage(timestamp, message)：

• 输入：整数时间戳 timestamp（单位：秒）和字符串 message。
• 输出：布尔值，如果应该打印返回 true，否则返回 false。

示例

Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");   // 返回 true，打印 "foo"，记录时间戳 1
logger.shouldPrintMessage(2, "bar");   // 返回 true，打印 "bar"，记录时间戳 2
logger.shouldPrintMessage(3, "foo");   // 返回 false，因为 "foo" 在时间 3 时，距离上次打印 (1) 小于 10 秒
logger.shouldPrintMessage(8, "bar");   // 返回 false，距离上次打印 (2) 小于 10 秒
logger.shouldPrintMessage(10, "foo");  // 返回 false，距离上次打印 (1) 等于 9 秒，仍小于 10
logger.shouldPrintMessage(11, "foo");  // 返回 true，距离上次打印 (1) 等于 10 秒，可以打印

2. 解题思路分析

这个问题本质上是为每个消息维护最近一次成功打印的时间戳，并在新请求到达时判断时间差是否 ≥ 10 秒。

为什么适合用哈希表？

• 需要根据 message 快速查找它上一次打印的时间。
• 键（key）是消息内容，值（value）是时间戳。
• 操作是 O(1) 的查找与更新，哈希表最合适。

关键点：

1. 如果消息从未出现过，或者上次打印时间与当前时间差 ≥ 10 秒，则应该打印，并更新时间戳。
2. 否则，不打印，也不更新时间戳（保持上次打印时间不变）。

3. 详细实现步骤

步骤 1：设计数据结构

我们只需要一个哈希表（字典/映射）：

• lastPrinted: Dict[str, int]，键为消息字符串，值为最后一次打印的时间戳。

初始化时，哈希表为空。

步骤 2：实现 shouldPrintMessage 逻辑

对于一次调用 shouldPrintMessage(timestamp, message)：

1. 如果 message 不在 lastPrinted 中，说明从未打印过，可以打印。将 (message, timestamp) 存入哈希表，返回 true。
2. 如果 message 在 lastPrinted 中，取出上次时间 lastTime。
   • 如果 timestamp - lastTime >= 10，说明可以再次打印。更新哈希表中该消息的时间戳为 timestamp，返回 true。
   • 否则，返回 false，不更新哈希表。

步骤 3：边界情况考虑

• 时间戳是递增的（通常日志按时间顺序调用），但即使时间戳非递增，我们的逻辑依然成立，因为我们只比较当前时间与上次记录时间。
• 如果时间差正好等于 10 秒，是允许打印的（符合“最近 10 秒内”的否定条件）。
• 消息字符串可能很长，但哈希表可以处理。

步骤 4：时间复杂度与空间复杂度

• 时间复杂度：每次调用 O(1)（哈希表查找和插入平均 O(1)）。
• 空间复杂度：O(n)，n 是不同消息的数量。

4. 代码实现示例（Python）

class Logger:

    def __init__(self):
        # 哈希表：message -> lastPrintedTimestamp
        self.lastPrinted = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message not in self.lastPrinted:
            # 第一次出现，打印并记录
            self.lastPrinted[message] = timestamp
            return True
        else:
            lastTime = self.lastPrinted[message]
            if timestamp - lastTime >= 10:
                # 超过10秒，可以再次打印，更新时间戳
                self.lastPrinted[message] = timestamp
                return True
            else:
                # 10秒内打印过，不打印，不更新时间戳
                return False

5. 运行示例演示

用前面例子跟踪哈希表变化：

Logger初始化: lastPrinted = {}

调用 shouldPrintMessage(1, "foo"):
  "foo" 不在表中 → 打印，记录 lastPrinted["foo"] = 1，返回 true。

调用 shouldPrintMessage(2, "bar"):
  "bar" 不在表中 → 打印，记录 lastPrinted["bar"] = 2，返回 true。

调用 shouldPrintMessage(3, "foo"):
  "foo" 在表中，lastTime = 1，时间差 3-1=2 < 10 → 不打印，返回 false。

调用 shouldPrintMessage(8, "bar"):
  lastTime = 2，时间差 8-2=6 < 10 → 返回 false。

调用 shouldPrintMessage(10, "foo"):
  lastTime = 1，时间差 10-1=9 < 10 → 返回 false。

调用 shouldPrintMessage(11, "foo"):
  lastTime = 1，时间差 11-1=10 >= 10 → 打印，更新 lastPrinted["foo"] = 11，返回 true。

6. 扩展思考

1. 内存优化：如果消息很多且时间不断推进，旧消息可能永远不再使用，可以考虑定期清理 10 秒前的记录，避免哈希表无限增长。但本题没有要求清理，通常假设调用次数有限。
2. 并发情况：如果多线程调用，需要加锁保护哈希表。
3. 变种问题：如果是滑动窗口内限制 N 条消息（不限相同消息），则需要用队列+哈希表来维护窗口内的所有消息。

这个设计简单而高效，完美利用了哈希表的 O(1) 查询与更新特性，是速率限制类问题的典型解法。