哈希算法题目：设计一个基于哈希的日志速率限制器 题目描述 设计一个日志速率限制器，要求实现以下功能： shouldPrintMessage(timestamp, message) ：判断给定时间戳和消息是否应该被打印 如果消息在过去10秒内没有被打印过，则返回true并记录该消息 如果消息在过去10秒内已被打印过，则返回false且不记录 解题思路 使用哈希表存储消息和最后一次打印时间戳 当新消息到达时，检查哈希表中是否存在该消息的记录 通过比较当前时间戳与上次打印时间戳的差值判断是否超过10秒 根据判断结果更新哈希表并返回布尔值 具体实现步骤 步骤1：数据结构设计 使用字典（哈希表）存储键值对： message -> last_print_timestamp 键：消息字符串（唯一标识） 值：该消息最后一次被成功打印的时间戳（整数） 步骤2：判断逻辑实现 查询阶段： 在哈希表中查找传入的message是否存在 如果不存在，说明该消息从未被打印过，可以直接打印 如果存在，获取上次打印时间last_ time 时间判断阶段： 计算时间差： time_diff = timestamp - last_time 如果time_ diff >= 10秒：允许打印，更新哈希表 如果time_ diff < 10秒：拒绝打印，保持哈希表不变 步骤3：边界情况处理 时间戳单调递增：题目假设时间戳是递增的，无需处理时间回退 内存管理：当系统运行时间很长时，可定期清理过期记录（超过10秒未使用的消息） 示例演示 假设初始状态哈希表为空： shouldPrintMessage(1, "foo") → 哈希表无"foo"记录 → 返回true → 更新哈希表{"foo":1} shouldPrintMessage(2, "bar") → 无"bar"记录 → 返回true → 更新{"foo":1, "bar":2} shouldPrintMessage(3, "foo") → 存在记录，时间差=3-1=2 <10 → 返回false shouldPrintMessage(11, "foo") → 时间差=11-1=10≥10 → 返回true → 更新{"foo":11, "bar":2} 算法特点 时间复杂度：O(1) 的查询和更新操作 空间复杂度：O(n) 其中n为不同消息的数量 核心优势：通过哈希表实现快速历史记录查询，避免遍历检查