哈希表

给定一个长度为100万的数组，需要回答10万次查询——每次查询要求计算某个区间的元素之和。最直观的做法是：对每个查询，遍历从左端点到右端点的所有元素进行累加。假设平均区间长度为50万，总操作次数约为500亿次，在现代CPU上需要运行数秒甚至更久。 ...

1953年1月，IBM研究员Hans Peter Luhn在一篇内部备忘录中提出了一个看似简单的想法：把数据放进"桶"里以加速查找。他当时的目的是解决一个日益紧迫的问题——科学文献的数量正以指数级增长，人工索引已经跟不上节奏。Luhn可能没想到，这个为了信息检索而设计的"桶"方案，会在七十年后成为计算机科学中最核心的数据结构之一。 ...

title: “哈希碰撞攻击：为何一条HTTP请求能让服务器CPU飙升到100%” date: “2026-03-05T16:55:02+08:00” description: “深入解析哈希碰撞DoS攻击的技术原理：从2003年Crosby和Wallach的开创性论文到2011年横扫主流语言的安全危机，揭示确定性哈希函数如何将O(1)操作变成O(n²)灾难，以及SipHash如何成为现代语言的标准防线。” draft: false categories: [“安全漏洞”, “数据结构”, “Web安全”] tags: [“哈希碰撞”, “HashDoS”, “算法复杂度攻击”, “SipHash”, “哈希表”, “拒绝服务攻击”, “Web安全”] 2003年8月，莱斯大学的Scott Crosby和Dan Wallach在第12届USENIX安全会议上发表了一篇题为《Denial of Service via Algorithmic Complexity Attacks》的论文。他们在演讲中展示了如何用不到拨号调制解调器的带宽，让一台专用入侵检测系统服务器在六分钟内开始丢弃71%的流量。 ...