我读过关于"概率"数据结构的文章，如布隆过滤器和跳过列表。
概率数据结构的共同特征是什么，它们的用途是什么？
可能有很多不同(和好的(答案，但以我的拙见，概率数据结构的共同特征是它们为您提供近似的，而不是精确的答案。
这里有多少件物品？大约1523425概率为99%
更新：快速搜索产生了指向有关该问题的体面文章的链接：
https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/
如果你对概率数据结构感兴趣，你可能想读我最近出版的书">大数据应用的概率数据结构和算法"(ISBN：9783748190486，可在亚马逊上找到(，我在书中解释了许多这样的节省空间的数据结构和快速算法，它们在现代大数据应用程序中非常有用。
在本书中，您可以找到最先进的算法和数据结构，这些算法和数据结构有助于处理大数据处理中的常见问题，例如
- 成员资格查询(布隆过滤器、计数布隆过滤器、商过滤器、布谷鸟过滤器(。
- 基数(线性计数、概率计数、LogLog、HyperLogLog、HyperLogLog++(。 频率
- (多数算法、频率、计数草图、计数最小草图(。
- 排名(随机抽样、q 摘要、t 摘要(。
- 相似性(LSH，MinHash，SimHash(。
您可以在 https://pdsa.gakhov.com 获得免费预览和有关该书的所有相关信息
概率数据结构不能给你一个明确的答案，相反，它们为你提供了一个合理的近似答案和一个近似这个估计的方法。它们对于大数据和流应用程序非常有用，因为它们可以显着减少所需的内存量(与为您提供确切答案的数据结构相比(。
在大多数情况下，这些数据结构使用哈希函数来随机化项目。因为它们忽略了冲突，所以它们保持大小不变，但这也是它们无法为您提供确切值的原因。它们带来的优势：
- 它们使用少量内存(您可以控制多少(
- 它们可以很容易地并行化(哈希是独立的(
- 它们具有恒定的查询时间(甚至不像字典中那样的摊销常量(
常用的概率数据结构包括：
- 布隆过滤器
- 计数-最小草图
- 超日志日志
维基百科中有一个概率数据结构列表供您参考：https://en.wikipedia.org/wiki/Category:Probabilistic_data_structures
关于什么是"概率数据结构"有不同的定义。恕我直言，概率数据结构意味着数据结构使用某种随机算法或在内部利用某些概率特征，但从数据结构用户的角度来看，它们不必以概率或不确定的方式行事。
-
有许多"概率数据结构"具有概率行为，例如提到的布隆过滤器和HyperLogLog通过其他答案。
-
同时，还有其他"概率数据结构"具有确定的行为(从用户的角度来看(，例如跳过列表。对于跳过列表，用户可以将其用作平衡的二叉搜索树，但在内部以一些概率相关的想法实现。根据跳过列表的作者威廉·皮尤(William Pugh(的说法：
跳过列表是一种概率数据结构，似乎可能 取代平衡树作为实施方法的选择 许多应用程序。跳过列表算法具有相同的渐近 预期时间范围为平衡树，更简单、更快和使用 更少的空间。
概率数据结构允许恒定的内存空间和极快的处理速度，同时仍然保持低错误率和指定的不确定性程度。
一些用例是
- 检查数据集中是否存在值
- 事件频率
- 估计数据集的近似大小
- 排名和分组