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

字数 4490 2025-12-19 05:48:47

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

题目描述

设计一个实时日志速率限制器。系统会接收源源不断的日志请求流（每条请求用一个唯一的 requestId 和发生的时间戳 timestamp 表示，时间戳单位为秒）。我们需要实现一个函数 shouldPrint(requestId, timestamp)，其功能是判断给定 requestId 对应的请求在当前 timestamp 是否允许被打印（即通过限制）。

限制规则如下：

对于同一个 requestId，如果在过去 10 秒内（包含当前秒）已经打印了超过 10 条消息，那么当前请求应该被拒绝（函数返回 false）。
否则，允许打印，记录此次请求，并返回 true。

要求高效地支持高频调用。

解题思路分析

这是一个典型的滑动窗口限流问题。我们需要为每个唯一的 requestId 维护一个时间窗口内的请求历史。当一个新的请求到达时，我们需要快速判断在 [timestamp - 9, timestamp] 这个长度为10秒的窗口内（包含当前秒，所以是过去9秒加当前秒，共10秒），该 requestId 的请求数量是否已达到上限10。

核心挑战在于如何高效地维护这个滑动窗口内的请求计数，并能在每次请求时快速清理掉窗口之外的过期请求记录。

哈希表的作用：显然，我们需要一个数据结构来映射每个 requestId 到其对应的请求历史记录。哈希表（HashMap/dict）是实现 O(1) 时间复杂度查找和插入 requestId 的完美选择。

历史记录的数据结构选择：对于每个 requestId 的历史记录，我们有几种选择：

存储所有时间戳的列表：每次检查时，需要遍历列表，移除过期的，并计算剩余数量。当请求量大且时间跨度可能很长时，列表会很长，清理和计数的成本 O(n) 可能过高。
存储一个计数器 + 队列：队列按时间顺序存放时间戳。新请求入队，检查时从队头弹出所有过期时间戳，并更新计数器。这是更优的选择，清理过期记录的摊还时间复杂度为 O(1)。
进一步优化 - 存储一个计数器 + 循环队列/时间分片：由于我们的窗口大小固定（10秒），我们可以使用一个固定大小为10的队列或数组，每个位置代表距离当前时间 0~9 秒的请求数。通过取模运算来更新。这种方法能保证严格 O(1) 的操作，且内存使用固定。

我们采用第2种（队列）和第3种（时间分片）相结合的一种清晰、高效且容易理解的实现方式。

循序渐进讲解

我们将设计一个类 Logger。

步骤 1：数据结构设计

我们需要一个哈希表 request_map。它的键是 requestId，值是一个数据结构，用于记录该 requestId 在最近10秒内各个时间点（秒）上的请求次数。

由于时间戳是整数秒，且窗口固定为10秒，我们可以为每个 requestId 维护一个长度为10的环形数组（或称为循环队列） counters。

counters[i] 表示在时间戳 current_time - i 这一秒内收到的请求数量（其中 i 从 0 到 9，i=0 表示当前秒）。
同时，我们需要记录该 requestId 最近一次更新的“基准时间戳” last_time，用于对齐时间窗口。

这样，哈希表的结构就是：requestId -> (last_time, counters)。

步骤 2：`shouldPrint` 方法流程

假设我们调用 shouldPrint(requestId, timestamp)。

获取或初始化记录：
- 从 request_map 中查找 requestId 对应的记录 (last_time, counters)。
- 如果不存在，则初始化：last_time = timestamp，counters 是一个长度为10、所有元素为0的数组。然后直接将 counters[0] 加1（表示在当前秒有一次请求），更新 last_time = timestamp，将新记录存入哈希表，并返回 true。
计算时间差并清理过期计数：
- 如果记录已存在，计算 time_passed = timestamp - last_time。
- 如果 time_passed >= 10，这意味着自上次更新以来，已经过去了至少一个完整的窗口时间。那么整个 counters 数组里记录的所有请求都过期了。我们可以直接将整个 counters 数组重置为全0。
- 如果 0 <= time_passed < 10，这意味着自上次更新后，仍在同一个10秒窗口内，或者部分重叠。我们需要将 counters 数组中代表“比 last_time 早了10秒或更久”的那些位置清零。具体操作是：
  - 从 i = 1 到 i = time_passed（包含），将 counters[i] 清零。实际上，更高效且能处理 time_passed > 10 的统一方法是：遍历 counters 数组的每个索引 i，如果 i > time_passed，说明这个位置代表的时间点（timestamp - i）已经不在当前窗口 [timestamp-9, timestamp] 内了，应该清零。但因为我们之后只会用到 i 从 0 到 min(9, time_passed) 的计数，一种实现技巧是：将数组视为一个环形缓冲区，每次根据时间差移动“当前秒”的指针，并只更新新的“当前秒”对应的位置。不过，为了清晰，我们先采用逻辑上清晰的“重置过期区间”的方法。
检查当前窗口总请求数：
- 在清理（或重置）了 counters 之后，我们计算当前窗口内的总请求数 sum(counters)。
- 如果 总和 >= 10，则拒绝本次请求，返回 false。
- 注意：由于我们清理后，counters 中只包含窗口内的计数，所以这个总和就是窗口内的请求数。
允许请求并更新记录：
- 如果总和 < 10，则允许本次请求。
- 更新 counters 中代表 timestamp 这一秒的计数。由于我们可能清理了数组，并且 timestamp 可能与 last_time 相同或不同，我们需要找到 timestamp 在 counters 数组中对应的索引。
  - 索引计算：index = timestamp % 10。这是关键技巧！ 我们用时间戳对10取模，这样每个时间戳都会映射到数组的一个固定位置。同一秒的所有请求会累加到 counters[index] 上。
  - 但是，直接使用 timestamp % 10 有个问题：不同时间周期（如第1秒和第11秒）的 timestamp 取模后都是1，但它们是不同窗口的。为了解决这个问题，我们不仅存储计数，还在每个位置存储其对应的时间戳。更常见的优化方法是：在每次访问时，如果发现 counters 中某个位置记录的时间戳与当前 timestamp 不属于同一个10秒周期（即 timestamp - stored_timestamp >= 10），则将该位置的计数清零，然后再用于当前请求的累加。我们稍后会看到这种实现。
更新 last_time：
- 将 last_time 更新为 timestamp。

步骤 3：优化实现方案

为了避免复杂的区间清零逻辑，并保证严格 O(1)，我们采用一种广泛使用的优化方案：

为每个 requestId 存储的信息简化为：一个长度为10的数组 times。

times[i] 记录了在时间戳 t 满足 t % 10 == i 时，最近一次在该索引位置（即该秒）发生请求的时间戳 t。
例如，times[3] = 153 表示，最近一次在“秒数模10等于3”的时刻（如第3秒、13秒、23秒...）发出的请求是在时间戳153。

算法流程：

计算索引 idx = timestamp % 10。
从哈希表中获取 requestId 对应的 times 数组。若不存在，则创建并初始化所有元素为 -1（表示从未使用）。
检查 times[idx] 的值：
- 如果 timestamp - times[idx] < 10，说明在最近10秒内，同一个模索引位置（意味着是同一个10秒周期内的同一秒，或者是上一个周期但仍在10秒窗口内）已经有过请求。但我们需要计算的是整个窗口内的总请求数，所以不能只看这一个位置。
- 实际上，我们需要遍历整个 times 数组（长度10，常数时间），对于每个位置 i：
  - 如果 timestamp - times[i] < 10，那么 times[i] 记录的这个请求是在当前10秒窗口内的，将其计入本次窗口的请求数。
统计完窗口内请求数 count。
如果 count >= 10，返回 false。
否则，允许请求：更新 times[idx] = timestamp（无论之前该位置记录的时间戳是什么，都用新的覆盖，因为同一秒的多次请求，我们只需要知道最近一次的时间戳，对于计数，我们是通过遍历整个数组按时间差判断的，所以覆盖旧值不影响统计过去10秒内不同秒的请求次数），然后返回 true。

这个方法非常巧妙：

times 数组本质上是一个时间戳的环形缓冲区，索引由 timestamp % 10 决定。
每次判断时，遍历这个固定大小的数组（10次操作），检查每个位置记录的时间戳是否在当前时间戳的10秒窗口内。是则计数+1。
更新时，直接将新时间戳写入对应索引位置。
它自动处理了时间窗口的滑动，无需显式地移动或清理数据，因为过期的记录（timestamp - times[i] >= 10）在遍历时不会被计入。

总结与复杂度分析

我们设计的 Logger 类包含一个哈希表 request_map，键为 requestId，值为一个长度为10的整数数组 times。

时间复杂度：shouldPrint 操作是 O(1)。虽然需要遍历长度为10的数组，但这是一个常数，与请求流规模无关。哈希表的查找和插入也是平均 O(1)。
空间复杂度：O(N * 10)，其中 N 是出现过的唯一 requestId 的数量。每个 requestId 存储一个大小为10的数组。

这种方法高效、准确地实现了固定时间窗口（滑动窗口）的速率限制，是处理此类问题的经典哈希表应用。

基于哈希的实时日志速率限制器题目描述设计一个实时日志速率限制器。系统会接收源源不断的日志请求流（每条请求用一个唯一的 requestId 和发生的时间戳 timestamp 表示，时间戳单位为秒）。我们需要实现一个函数 shouldPrint(requestId, timestamp) ，其功能是判断给定 requestId 对应的请求在当前 timestamp 是否允许被打印（即通过限制）。限制规则如下：对于同一个 requestId ，如果在过去 10 秒内（包含当前秒）已经打印了超过 10 条消息，那么当前请求应该被拒绝（函数返回 false ）。否则，允许打印，记录此次请求，并返回 true 。要求高效地支持高频调用。解题思路分析这是一个典型的滑动窗口限流问题。我们需要为每个唯一的 requestId 维护一个时间窗口内的请求历史。当一个新的请求到达时，我们需要快速判断在 [timestamp - 9, timestamp] 这个长度为10秒的窗口内（包含当前秒，所以是过去9秒加当前秒，共10秒），该 requestId 的请求数量是否已达到上限10。核心挑战在于如何高效地维护这个滑动窗口内的请求计数，并能在每次请求时快速清理掉窗口之外的过期请求记录。哈希表的作用：显然，我们需要一个数据结构来映射每个 requestId 到其对应的请求历史记录。哈希表（ HashMap / dict ）是实现 O(1) 时间复杂度查找和插入 requestId 的完美选择。历史记录的数据结构选择：对于每个 requestId 的历史记录，我们有几种选择：存储所有时间戳的列表：每次检查时，需要遍历列表，移除过期的，并计算剩余数量。当请求量大且时间跨度可能很长时，列表会很长，清理和计数的成本 O(n) 可能过高。存储一个计数器 + 队列：队列按时间顺序存放时间戳。新请求入队，检查时从队头弹出所有过期时间戳，并更新计数器。这是更优的选择，清理过期记录的摊还时间复杂度为 O(1) 。进一步优化 - 存储一个计数器 + 循环队列/时间分片：由于我们的窗口大小固定（10秒），我们可以使用一个固定大小为10的队列或数组，每个位置代表距离当前时间 0~9 秒的请求数。通过取模运算来更新。这种方法能保证严格 O(1) 的操作，且内存使用固定。我们采用第2种（队列）和第3种（时间分片）相结合的一种清晰、高效且容易理解的实现方式。循序渐进讲解我们将设计一个类 Logger 。步骤 1：数据结构设计我们需要一个哈希表 request_map 。它的键是 requestId ，值是一个数据结构，用于记录该 requestId 在最近10秒内各个时间点（秒）上的请求次数。由于时间戳是整数秒，且窗口固定为10秒，我们可以为每个 requestId 维护一个长度为10的环形数组（或称为循环队列） counters 。 counters[i] 表示在时间戳 current_time - i 这一秒内收到的请求数量（其中 i 从 0 到 9 ， i=0 表示当前秒）。同时，我们需要记录该 requestId 最近一次更新的“基准时间戳” last_time ，用于对齐时间窗口。这样，哈希表的结构就是： requestId -> (last_time, counters) 。步骤 2： shouldPrint 方法流程假设我们调用 shouldPrint(requestId, timestamp) 。获取或初始化记录：从 request_map 中查找 requestId 对应的记录 (last_time, counters) 。如果不存在，则初始化： last_time = timestamp ， counters 是一个长度为10、所有元素为0的数组。然后直接将 counters[0] 加1（表示在当前秒有一次请求），更新 last_time = timestamp ，将新记录存入哈希表，并返回 true 。计算时间差并清理过期计数：如果记录已存在，计算 time_passed = timestamp - last_time 。如果 time_passed >= 10 ，这意味着自上次更新以来，已经过去了至少一个完整的窗口时间。那么整个 counters 数组里记录的所有请求都过期了。我们可以直接将整个 counters 数组重置为全0。如果 0 <= time_passed < 10 ，这意味着自上次更新后，仍在同一个10秒窗口内，或者部分重叠。我们需要将 counters 数组中代表“比 last_time 早了10秒或更久”的那些位置清零。具体操作是：从 i = 1 到 i = time_passed （包含），将 counters[i] 清零。实际上，更高效且能处理 time_passed > 10 的统一方法是：遍历 counters 数组的每个索引 i ，如果 i > time_passed ，说明这个位置代表的时间点（ timestamp - i ）已经不在当前窗口 [timestamp-9, timestamp] 内了，应该清零。但因为我们之后只会用到 i 从 0 到 min(9, time_passed) 的计数，一种实现技巧是：将数组视为一个环形缓冲区，每次根据时间差移动“当前秒”的指针，并只更新新的“当前秒”对应的位置。不过，为了清晰，我们先采用逻辑上清晰的“重置过期区间”的方法。检查当前窗口总请求数：在清理（或重置）了 counters 之后，我们计算当前窗口内的总请求数 sum(counters) 。如果总和 >= 10 ，则拒绝本次请求，返回 false 。注意：由于我们清理后， counters 中只包含窗口内的计数，所以这个总和就是窗口内的请求数。允许请求并更新记录：如果总和 < 10 ，则允许本次请求。更新 counters 中代表 timestamp 这一秒的计数。由于我们可能清理了数组，并且 timestamp 可能与 last_time 相同或不同，我们需要找到 timestamp 在 counters 数组中对应的索引。索引计算： index = timestamp % 10 。这是关键技巧！我们用时间戳对10取模，这样每个时间戳都会映射到数组的一个固定位置。同一秒的所有请求会累加到 counters[index] 上。但是，直接使用 timestamp % 10 有个问题：不同时间周期（如第1秒和第11秒）的 timestamp 取模后都是1，但它们是不同窗口的。为了解决这个问题，我们不仅存储计数，还在每个位置存储其对应的时间戳。更常见的优化方法是：在每次访问时，如果发现 counters 中某个位置记录的时间戳与当前 timestamp 不属于同一个10秒周期（即 timestamp - stored_timestamp >= 10 ），则将该位置的计数清零，然后再用于当前请求的累加。我们稍后会看到这种实现。更新 last_time ：将 last_time 更新为 timestamp 。步骤 3：优化实现方案为了避免复杂的区间清零逻辑，并保证严格 O(1) ，我们采用一种广泛使用的优化方案：为每个 requestId 存储的信息简化为：一个长度为10的数组 times 。 times[i] 记录了在时间戳 t 满足 t % 10 == i 时，最近一次在该索引位置（即该秒）发生请求的时间戳 t 。例如， times[3] = 153 表示，最近一次在“秒数模10等于3”的时刻（如第3秒、13秒、23秒...）发出的请求是在时间戳153。算法流程：计算索引 idx = timestamp % 10 。从哈希表中获取 requestId 对应的 times 数组。若不存在，则创建并初始化所有元素为 -1 （表示从未使用）。检查 times[idx] 的值：如果 timestamp - times[idx] < 10 ，说明在最近10秒内，同一个模索引位置（意味着是同一个10秒周期内的同一秒，或者是上一个周期但仍在10秒窗口内）已经有过请求。但我们需要计算的是整个窗口内的总请求数，所以不能只看这一个位置。实际上，我们需要遍历整个 times 数组（长度10，常数时间），对于每个位置 i ：如果 timestamp - times[i] < 10 ，那么 times[i] 记录的这个请求是在当前10秒窗口内的，将其计入本次窗口的请求数。统计完窗口内请求数 count 。如果 count >= 10 ，返回 false 。否则，允许请求：更新 times[idx] = timestamp （无论之前该位置记录的时间戳是什么，都用新的覆盖，因为同一秒的多次请求，我们只需要知道最近一次的时间戳，对于计数，我们是通过遍历整个数组按时间差判断的，所以覆盖旧值不影响统计过去10秒内不同秒的请求次数），然后返回 true 。这个方法非常巧妙： times 数组本质上是一个时间戳的环形缓冲区，索引由 timestamp % 10 决定。每次判断时，遍历这个固定大小的数组（10次操作），检查每个位置记录的时间戳是否在当前时间戳的10秒窗口内。是则计数+1。更新时，直接将新时间戳写入对应索引位置。它自动处理了时间窗口的滑动，无需显式地移动或清理数据，因为过期的记录（ timestamp - times[i] >= 10 ）在遍历时不会被计入。总结与复杂度分析我们设计的 Logger 类包含一个哈希表 request_map ，键为 requestId ，值为一个长度为10的整数数组 times 。时间复杂度： shouldPrint 操作是 O(1) 。虽然需要遍历长度为10的数组，但这是一个常数，与请求流规模无关。哈希表的查找和插入也是平均 O(1) 。空间复杂度： O(N * 10) ，其中 N 是出现过的唯一 requestId 的数量。每个 requestId 存储一个大小为10的数组。这种方法高效、准确地实现了固定时间窗口（滑动窗口）的速率限制，是处理此类问题的经典哈希表应用。