哈希算法题目：设计一个基于哈希的分布式实时监控系统（支持滑动窗口统计和异常检测）

题目描述：
设计一个分布式实时监控系统，用于收集来自多个服务器的指标数据（如CPU使用率、内存使用率等）。系统需要支持以下功能：

1. 添加数据点：接收带时间戳的指标数据
2. 滑动窗口统计：计算最近N分钟内的平均值、最大值、最小值
3. 异常检测：基于历史数据识别异常值
4. 分布式扩展：支持水平扩展处理海量数据

解题过程：

步骤1：设计数据存储结构
使用哈希表存储时间窗口内的数据，键为时间戳（按分钟取整），值为该时间段的统计信息。

class TimeWindow:
    def __init__(self, window_size=10):  # 10分钟窗口
        self.window_size = window_size
        self.data = {}  # 哈希表：timestamp -> Statistics
        self.current_stats = Statistics()
    
class Statistics:
    def __init__(self):
        self.count = 0
        self.sum = 0
        self.max = float('-inf')
        self.min = float('inf')
        self.values = []  # 存储原始值用于异常检测

步骤2：实现滑动窗口机制
使用循环时间窗口，自动淘汰过期数据。

class SlidingWindowMonitor:
    def __init__(self, window_size=10):
        self.window_size = window_size
        self.windows = {}  # 哈希表：metric_name -> TimeWindow
        
    def add_data_point(self, metric_name, timestamp, value):
        # 按分钟取整作为时间键
        time_key = timestamp // 60 * 60
        
        if metric_name not in self.windows:
            self.windows[metric_name] = TimeWindow(self.window_size)
        
        window = self.windows[metric_name]
        self._update_window(window, time_key, value)
        self._clean_old_data(window, time_key)
    
    def _update_window(self, window, time_key, value):
        if time_key not in window.data:
            window.data[time_key] = Statistics()
        
        stats = window.data[time_key]
        stats.count += 1
        stats.sum += value
        stats.max = max(stats.max, value)
        stats.min = min(stats.min, value)
        stats.values.append(value)

步骤3：实现数据清理和滑动
维护窗口大小，自动移除过期数据点。

def _clean_old_data(self, window, current_time_key):
    # 计算最早允许的时间戳
    earliest_allowed = current_time_key - (self.window_size - 1) * 60
    
    # 移除过期数据
    expired_keys = []
    for time_key in window.data:
        if time_key < earliest_allowed:
            expired_keys.append(time_key)
    
    for key in expired_keys:
        del window.data[key]

步骤4：实现统计查询功能
计算滑动窗口内的各种统计指标。

def get_window_stats(self, metric_name, current_time):
    if metric_name not in self.windows:
        return None
    
    window = self.windows[metric_name]
    time_key = current_time // 60 * 60
    self._clean_old_data(window, time_key)
    
    total_count = 0
    total_sum = 0
    window_max = float('-inf')
    window_min = float('inf')
    all_values = []
    
    for stats in window.data.values():
        total_count += stats.count
        total_sum += stats.sum
        window_max = max(window_max, stats.max)
        window_min = min(window_min, stats.min)
        all_values.extend(stats.values)
    
    return {
        'average': total_sum / total_count if total_count > 0 else 0,
        'max': window_max,
        'min': window_min,
        'count': total_count
    }

步骤5：实现基于Z-score的异常检测
使用统计学方法识别异常值。

def detect_anomalies(self, metric_name, current_time, threshold=2.0):
    stats = self.get_window_stats(metric_name, current_time)
    if not stats or stats['count'] < 2:
        return []
    
    # 计算均值和标准差
    mean = stats['average']
    variance = sum((x - mean) ** 2 for x in stats['values']) / len(stats['values'])
    std_dev = variance ** 0.5
    
    # 识别异常值（Z-score > threshold）
    anomalies = []
    for value in stats['values']:
        z_score = abs(value - mean) / std_dev if std_dev > 0 else 0
        if z_score > threshold:
            anomalies.append({
                'value': value,
                'z_score': z_score,
                'timestamp': current_time
            })
    
    return anomalies

步骤6：分布式扩展设计
使用一致性哈希将数据分布到多个节点。

class DistributedMonitor:
    def __init__(self, nodes, virtual_nodes=3):
        self.hash_ring = ConsistentHashRing(virtual_nodes)
        for node in nodes:
            self.hash_ring.add_node(node)
        self.monitors = {node: SlidingWindowMonitor() for node in nodes}
    
    def add_data_point(self, metric_name, timestamp, value):
        # 根据指标名称选择节点
        node = self.hash_ring.get_node(metric_name)
        self.monitors[node].add_data_point(metric_name, timestamp, value)

步骤7：优化性能
使用增量计算优化统计计算。

class OptimizedTimeWindow:
    def __init__(self, window_size=10):
        self.window_size = window_size
        self.data = OrderedDict()  # 保持插入顺序
        self.running_stats = {
            'total_sum': 0,
            'total_count': 0,
            'max_value': float('-inf'),
            'min_value': float('inf')
        }
    
    def add_data_point(self, time_key, value):
        # 更新运行统计（增量计算）
        self.running_stats['total_sum'] += value
        self.running_stats['total_count'] += 1
        self.running_stats['max_value'] = max(self.running_stats['max_value'], value)
        self.running_stats['min_value'] = min(self.running_stats['min_value'], value)
        
        # 添加新数据点
        if time_key not in self.data:
            self.data[time_key] = []
        self.data[time_key].append(value)

这个设计方案展示了如何结合哈希表和滑动窗口算法来构建一个高效的分布式监控系统，具备良好的扩展性和实时性。