基于哈希的日志速率限制器

题目描述
设计一个日志速率限制器，它应该支持以下操作：

1. shouldPrintMessage(timestamp, messageId)：判断一条日志消息在给定的时间戳（以秒为单位）是否可以打印。规则如下：
   • 每条唯一的 messageId 在过去的10秒内最多只能打印一次。
   • 如果这条消息在过去的10秒内没有被打印过（或者从未打印过），那么这个方法返回 true，并记录下这次调用的时间戳。
   • 否则，返回 false。

你需要设计一个数据结构，高效地实现这个速率限制功能。

解题过程循序渐进讲解

步骤1：理解核心需求与规则
首先，我们明确问题的核心：

• 这是一个速率限制问题，限制的单位是“每条唯一消息”。
• 限制的时间窗口是“过去的10秒”。
• 需要记录每个消息最近一次成功打印的时间戳。
• 当一个新的请求到来时（包含timestamp和messageId），我们需要判断：
  • 如果这个messageId从未出现过，或者它最近一次打印的时间戳 ≤ 当前timestamp - 10，那么允许打印（返回true），并更新这个messageId的最近打印时间为当前timestamp。
  • 否则，拒绝打印（返回false）。

步骤2：数据结构的选择
我们需要一个能存储“消息ID”和其“最近一次打印时间戳”对应关系的数据结构。

• 键（Key）：messageId（通常是一个字符串）。
• 值（Value）：该消息最近一次被允许打印的时间戳（整数）。
• 操作：快速的插入、查找和更新。
  这恰好是哈希表（字典） 的典型应用场景。其平均时间复杂度为O(1)，可以满足高效的要求。

步骤3：算法逻辑设计
我们设计一个类 Logger，内部维护一个哈希表 msg_map。

• __init__：初始化一个空的哈希表。
• shouldPrintMessage(timestamp, messageId)：
  1. 检查条件：在msg_map中查找messageId。
     • 如果找不到，说明是全新消息，可以打印。
     • 如果找到了，取出其存储的时间戳 last_time。如果 timestamp - last_time >= 10，说明距离上次打印已超过10秒，可以打印。
     • 否则（即找到且时间差小于10秒），不可打印。
  2. 更新记录：只有当判定为“可以打印”时，我们才更新（或插入）msg_map[messageId] = timestamp。
  3. 返回值：根据判定结果返回 True 或 False。

步骤4：详细步骤与示例推演
假设我们按顺序调用：

1. logger.shouldPrintMessage(1, "foo")

   • msg_map 为空，找不到 “foo”。
   • 允许打印，更新 msg_map 为 {"foo": 1}。
   • 返回 True。

2. logger.shouldPrintMessage(2, "bar")

   • msg_map 为 {"foo": 1}，找不到 “bar”。
   • 允许打印，更新 msg_map 为 {"foo": 1, "bar": 2}。
   • 返回 True。

3. logger.shouldPrintMessage(3, "foo")

   • 找到 “foo”，last_time = 1。计算 3 - 1 = 2，2 < 10。
   • 不允许打印，msg_map 保持不变。
   • 返回 False。

4. logger.shouldPrintMessage(8, "bar")

   • 找到 “bar”，last_time = 2。计算 8 - 2 = 6，6 < 10。
   • 不允许打印，返回 False。

5. logger.shouldPrintMessage(10, "foo")

   • 找到 “foo”，last_time = 1。计算 10 - 1 = 9，9 < 10。
   • 不允许打印，返回 False。

6. logger.shouldPrintMessage(11, "foo")

   • 找到 “foo”，last_time = 1。计算 11 - 1 = 10。注意，题目要求是“过去的10秒内”，即时间差大于等于10秒才允许。10 >= 10 成立。
   • 允许打印，更新 msg_map 为 {"foo": 11, "bar": 2}。
   • 返回 True。

步骤5：边界情况与注意事项

• 时间窗口理解：“过去10秒”指的是开区间吗？从例子看，timestamp=11时，timestamp=1的打印已不在“过去10秒”（即(1, 11]）内，所以允许。规则等价于“两次打印的间隔至少为10秒”。
• 时间戳非递减：题目通常保证对shouldPrintMessage的调用，其timestamp参数是非递减的。这简化了问题，我们不需要清理“过期”的旧记录（因为旧的timestamp不会再被用到）。如果时间戳可能乱序，则需更复杂的设计。
• 内存管理：在极端长时间运行下，msg_map会积累所有出现过的消息ID。如果消息ID数量无限且需考虑内存，可以引入定期清理（如移除时间戳小于当前时间-10的记录）的机制，但本题简化条件下非必须。

步骤6：代码实现（Python示例）

class Logger:
    def __init__(self):
        # 初始化哈希表，用于存储 messageId -> 最近打印时间戳
        self.msg_map = {}

    def shouldPrintMessage(self, timestamp: int, messageId: str) -> bool:
        # 检查messageId是否存在，以及上次打印时间是否在10秒内
        if messageId in self.msg_map and timestamp - self.msg_map[messageId] < 10:
            # 上次打印在10秒内，拒绝本次打印
            return False
        # 允许打印，更新该messageId的时间戳
        self.msg_map[messageId] = timestamp
        return True

总结
这个算法利用哈希表实现了O(1)时间复杂度的查找和更新，核心在于为每个唯一消息ID维护其最近一次合法打印的时间戳，并通过比较当前时间戳与上次时间戳的差值来实施“固定时间窗口”的速率限制。设计简洁高效，是哈希表在状态记录和访问控制中的一个典型应用。