哈希算法题目：设计一个基于哈希的分布式限流器

题目描述：
设计一个分布式限流器，用于限制在特定时间窗口内某个操作（如API调用）的最大次数。系统需要支持以下操作：

• allow(key, timestamp)：判断在给定时间戳时，key对应的操作是否被允许（即是否未超过限制）

要求实现基于固定时间窗口的限流算法，每个key在固定时间窗口（如1秒）内最多允许N次操作。

解题过程：

1. 问题分析
   限流器的核心需求是统计每个key在最近的时间窗口内的操作次数。在分布式环境中，我们需要一个可以水平扩展的解决方案。

2. 哈希函数选择

• 使用一致性哈希将key分布到不同的节点
• 每个节点负责一部分key的限流统计
• 哈希函数需要保证均匀分布，避免热点问题

3. 数据结构设计

class RateLimiter:
    def __init__(self, max_requests, window_size):
        self.max_requests = max_requests  # 时间窗口内最大请求数
        self.window_size = window_size    # 时间窗口大小（秒）
        self.requests = {}                 # key: 存储时间戳列表的字典

4. 核心算法实现

def allow(self, key, timestamp):
    # 清理过期的时间戳
    self._cleanup(key, timestamp)
    
    # 检查是否超过限制
    if len(self.requests.get(key, [])) >= self.max_requests:
        return False
    
    # 添加当前时间戳
    if key not in self.requests:
        self.requests[key] = []
    self.requests[key].append(timestamp)
    return True

def _cleanup(self, key, current_time):
    if key not in self.requests:
        return
    
    # 移除超出时间窗口的时间戳
    cutoff_time = current_time - self.window_size
    self.requests[key] = [ts for ts in self.requests[key] if ts > cutoff_time]

5. 分布式扩展
   为了实现分布式限流，我们需要：

• 使用一致性哈希将key路由到对应的节点
• 每个节点独立维护自己负责的key的限流状态
• 通过虚拟节点解决数据分布不均匀的问题

6. 优化考虑

• 使用环形缓冲区替代列表，减少内存分配
• 实现时间窗口的滑动更新，避免边界问题
• 添加持久化机制，防止节点重启后数据丢失

7. 完整实现示例

class DistributedRateLimiter:
    def __init__(self, max_requests, window_size, nodes):
        self.max_requests = max_requests
        self.window_size = window_size
        self.consistent_hash = ConsistentHash(nodes)
        self.node_states = {node: RateLimiter(max_requests, window_size) for node in nodes}
    
    def allow(self, key, timestamp):
        node = self.consistent_hash.get_node(key)
        return self.node_states[node].allow(key, timestamp)

这个设计确保了在分布式环境下，相同key的请求会被路由到同一个节点，从而保证限流的准确性。