2 篇博文 含有标签「data structures」

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

用例

• LevelDB MemTable
• Redis 有序集合(Redis SortedSet)
• 倒排索引(Lucene inverted index)

布隆过滤器(Bloom filter)是一种数据结构，用于以远高于其他一般算法的空间和时间效率来检索一个元素是否在一个集合中。

使用布隆过滤器获得的结果，可能为假阳性匹配，但是不可能为假阴性匹配。换句话说，查询返回的结果是“==要么在可能不在，要么不在肯定不在==”。元素可以添加到集合中，但不能删除（尽管这可以通过额外的“计数”布隆过滤器来解决）；添加到集合中的元素越多，误报的可能性越大。

用例

• Cassandra使用布隆过滤器来确定SSTable是否有特定行的数据。
• HBase布隆过滤器是一种测试StoreFile是否包含特定行或者行列单元格的有效机制。
• 使用布隆过滤器，网站的反作弊系统可以有效地拒绝被禁止使用的用户。
• 谷歌的Chrome浏览器曾使用布隆过滤器来识别恶意链接。