2 篇文档带有标签「data structures」

布隆过滤器是一种数据结构，用于以远高于其他一般算法的空间和时间效率来检索一个元素是否在一个集合中。使用布隆过滤器获得的结果，可能为假阳性匹配，但不可能为假阴性匹配。元素可以添到集合中，但不能删除；添到集合中的元素越多，误报的可能性越大。

跳跃表本质上是一个允许对其进行二分搜索的链表。它实现这一点的方法是添加额外的节点，使你能够“跳过”链接列表的部分。对于给定一个正反随机数来创建额外的节点，跳跃表具有O(logn)复杂度的查询、插入和删除。