HyperLogLog：用1.5KB内存估算十亿级基数的概率魔法
引言：一个看似不可能的问题 假设你正在运营一个日活用户超过十亿的社交平台，产品经理问你：“今天有多少独立用户访问了我们的网站？“这个问题听起来简单，但当你真正思考如何回答时，会发现它蕴含着深刻的计算机科学难题。 ...
数据结构
链表算法为何让无数开发者头疼从指针陷阱到快慢指针的完整LeetCode通关指南
1955年，Allen Newell、Cliff Shaw和Herbert A. Simon在RAND Corporation和卡内基梅隆大学开发Information Processing Language（IPL）时，创造了链表这一数据结构。这个发明最初是为了支持早期人工智能程序——Logic Theory Machine和General Problem Solver。有趣的是，链表在诞生之初就是为解决复杂问题而生，而今天它却成了面试中最基础却又最容易出错的考题之一。 ...
线段树：如何在O(log n)时间内完成任意区间查询与更新
假设你正在开发一个实时数据分析平台，需要频繁执行两类操作：查询某个时间段内的数据总和，以及更新某个时间点的数值。如果用普通数组，查询需要 $O(n)$ 时间遍历整个区间；如果用前缀和数组，查询确实降到了 $O(1)$，但每次更新又需要 $O(n)$ 时间重新计算前缀。当数据量达到百万级别、操作频率达到每秒数千次时，这两种方案都无法满足性能要求。 ...
并查集：从社交网络连通性到LeetCode通关的完整指南
假设你正在开发一个社交网络应用，需要实时回答"用户A和用户B是否在同一个社交圈内"这类查询——用户之间可以通过好友关系不断形成更大的圈子。每添加一个好友关系，圈子就可能合并；每查询一次，就需要判断两个用户是否已经连通。如果用传统的图遍历方法，每次查询都可能需要遍历整个图，当用户量达到百万级别时，系统会变得极其缓慢。 ...
Roaring Bitmaps：为什么这种压缩位图正在重塑大数据分析的存储范式
2014年，Daniel Lemire和Samy Chambi等人在arXiv上发表了一篇题为《Better bitmap performance with Roaring bitmaps》的论文。论文的核心结论令人印象深刻：相比当时主流的压缩位图方案WAH和Concise，Roaring bitmaps在交集操作上快了最多900倍，同时压缩率还提高了约2倍。这不是学术界的理论推演，而是基于真实数据集的实测结果。 ...
时间轮如何以O(1)复杂度处理百万级延迟任务
一个电商平台在双十一期间需要处理数百万个订单超时取消任务。每个订单创建后30分钟未支付就需要自动取消，释放库存。最直观的实现方式是在数据库中存储订单的创建时间，然后启动一个定时任务每隔几秒扫描一次，找出所有超时的订单。 ...
打开一个500MB的文件需要多久：从字符串到Piece Tree的文本编辑器数据结构进化史
2018年之前，Visual Studio Code用户经常报告一个奇怪的问题：打开某些文件会导致内存溢出崩溃。罪魁祸首是一个35 MB的文件——听起来不大，但它有1370万行。VSCode为每一行创建一个对象，每个对象占用40-60字节，结果光是行数组就消耗了约600 MB内存，是原文件大小的近20倍。 ...