什么是概率数据结构？
我已经阅读过像bloom过滤器和跳过列表这样的数据结构。
概率数据结构的共同特征是什么？它们用于什么？
可能有很多不同的（和好的）答案，但在我的愚见中，概率数据结构的共同特征是它们给你提供了一个近似的，不准确的答案。
这里有多少物品？ 约有1523425个概率为99％
更新：快速搜索链接到正确的文章的问题：
https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/
概率数据结构不能给你一个明确的答案，相反他们提供了一个合理的答案近似值和一种近似估计的方法。 它们对于大数据和流应用程序非常有用，因为它们可以显着减少所需的内存量（与给出确切答案的数据结构相比）。
在大多数情况下，这些数据结构使用散列函数来随机化项目。 因为他们忽略了碰撞，他们保持大小不变，但这也是他们无法给你确切数值的原因。 他们带来的好处：
常用的概率数据结构是：
在维基百科上有一个概率数据结构列表供您参考：https：//en.wikipedia.org/wiki/Category:Probabilistic_data_structures
关于“概率数据结构”是什么有不同的定义。 恕我直言，概率数据结构意味着数据结构使用一些随机算法或在内部利用某些概率特性，但是他们不必从数据结构用户的角度出现概率性或非确定性行为。
有很多“概率数据结构”具有概率性行为，如其他答案提到的布隆过滤器和HyperLogLog。
与此同时，还有其他“概率数据结构”具有确定的行为（从用户的角度来看），例如跳过列表。 对于跳过列表，用户可以将其类似地用作平衡二叉搜索树，但在内部用一些概率相关的概念来实现。 根据跳过列表的作者William Pugh：
跳过列表是一种概率数据结构 ，似乎可能取代平衡树作为许多应用程序的实现方法。 跳过列表算法具有与平衡树相同的渐近期望时间界限，并且更简单，更快速并且使用更少的空间。
上一篇: What are probabilistic data structures?
下一篇: Java tree data