字符串哈希如何用O(1)时间判断两个子串是否相等
一个看似简单的问题 给你一个字符串"abcdefg"，现在需要判断子串s[1:4]和子串s[3:6]是否相等。你会怎么做？ 最直观的方法是逐字符比较：遍历两个子串的每个字符，逐一对比。对于长度为k的子串，这需要O(k)的时间复杂度。当子串较长或者需要进行大量比较时，这种方法的性能瓶颈就会暴露出来。 ...
数据结构与算法
HNSW：为什么这个图算法正在统治AI时代的向量检索
2016年3月，Yury Malkov和Dmitry Yashunin在arXiv上发表了一篇题为《Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs》的论文。这篇论文提出的HNSW算法，在随后的几年里成为了几乎所有主流向量数据库的核心索引——Elasticsearch、Milvus、Pinecone、Weaviate、Qdrant无一例外。 ...
Roaring Bitmaps：为什么这种压缩位图正在重塑大数据分析的存储范式
2014年，Daniel Lemire和Samy Chambi等人在arXiv上发表了一篇题为《Better bitmap performance with Roaring bitmaps》的论文。论文的核心结论令人印象深刻：相比当时主流的压缩位图方案WAH和Concise，Roaring bitmaps在交集操作上快了最多900倍，同时压缩率还提高了约2倍。这不是学术界的理论推演，而是基于真实数据集的实测结果。 ...
为什么主流语言的sort函数都选择了Timsort
1959年，Tony Hoare发明了快速排序。这个算法在教科书中被奉为圭臬，平均时间复杂度$O(n \log n)$，原地排序，缓存友好，几乎完美。然而，六十多年后的今天，当你调用Python的list.sort()、Java的Arrays.sort()或Rust的稳定排序时，底层运行的却是一个叫Timsort的算法。 ...