跳到主要内容

2 篇博文 含有标签「数据结构」

查看所有标签

布隆过滤器

· 阅读需 2 分钟

布隆过滤器是一种数据结构,用于以时间和空间高效的方式检测一个元素是否在一个集合中。

可能会出现假阳性匹配,但不会出现假阴性——换句话说,查询返回“可能在集合中”或“绝对不在集合中”。元素可以添加到集合中,但不能移除(尽管可以通过“计数”布隆过滤器来解决这个问题);添加到集合中的元素越多,假阳性的概率就越大。

使用案例

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

跳表

· 阅读需 1 分钟

跳表本质上是一种链表,允许您在其上进行二分查找。它通过添加额外的节点来实现这一点,使您能够‘跳过’链表的某些部分。通过随机投掷硬币来创建额外节点,跳表的搜索、插入和删除操作的时间复杂度应为 O(logn)。

用例

  • LevelDB MemTable
  • Redis SortedSet
  • Lucene 倒排索引