哈希函数的概率数据结构

哈希函数 在计算机科学中广泛使用，并在概率数据结构和算法中非常有用。我们都知道数据结构是大多数算法的构建块。一个糟糕的选择可能会导致出现一个困难和低效的解决方案，而不是优雅和高效的解决方案。

正如Linus Torvalds在谈论Git时所说: 事实上，我非常支持围绕数据设计代码。相反，我认为这也是Git取得成功的原因之一(*)。

辨别是否是一个糟糕 程序员 之间的一个好方法是考虑他的代码或数据结构

更重要的是。糟糕的程序员担心代码。优秀的程序员担心数据结构及其关系。如果你是一名计算机科学家、工程师或程序员，你会非常清楚不同层次的数据结构的细节。与任何程序员进行十分钟的交谈可能会得到以下信息:链表、树、堆积、地图等等。

我已经和同事和朋友讨论过关于掌握这些数据结构的重要性，这取决于你的工作内容。

大多数情况下，如果您使用高级语言进行编程，那么这是一种重新发明的轮子。大多数框架都内置了这些数据结构，或者有一些非常高效的库，这些库可以让你进行更好的工作状态。

从另一个角度来看，大多数人在维护软件或者资源约束不是问题的地方工作。专注于将性能或资源消耗作为数据结构或算法的唯一度量标准是非常不明智的。这取决于你要解决的问题以及它的规模。

但有时资源约束确实是一个问题，在这种情况下，您应该考虑 工具 箱中的一个重要工具:概率数据结构。它们牺牲了相当可观的资源需求的精确性。如果您正在解决一个内存空间不受限制的小问题，计算不是瓶颈，精确的精度是必需的，那么在使用它们之前，您可能会三思而后行。如果不是这样，你应该知道它们存在的意义。另外，它们学起来很有趣。

有很多书、论文和文章都在讨论这个话题。在这里，我将讨论其中两个我认为非常漂亮并且在实际问题中大量使用的方法。我将使用一些数学言语，但不是很详细，因为网上有很多优秀的资源。即使你不懂数学，你也会得到它们的基本概念(这就是我们的目标)。

布隆过滤器 （Bloom filters）

如果我没记错的话，布隆过滤器是我几年前在阅读somepetascale数据库时听说的第一个概率数据结构。与许多其他概率数据结构一样，考虑到它们所需的空间和计算非常少，您会对它们的有效性感到非常惊讶。

假设你有一个很大的整数集S，你想要检查S是否包含一个元素i。你可以使用一个简单的带有空间/时间O(n)/O(n)的链表来解决这个问题。同样，尝试一个平衡的二叉树，包含O(n)/O(log(n))。或者显然是O(n)/O(1)的映射。

似乎大多数选项都需要与S的基数线性的内存空间有关，这听起来很合理，因为如果我们不存储S的每个元素的值，我们如何检查S中是否存在元素?

布隆的思想是将整个集合S编码成一个固定长度的二进制字符串，我们将其称为q。这是通过对Swithin q中的每个元素进行编码来实现的。

让我们看一个布隆的典型示例。假设我们将Q定义为一个长度固定为64位的二进制字符串。同时，我们选择k个不同的哈希函数，如MD5或SHA-1。接下来，我们做以下工作:

· 取S中的第一个元素

· 使用k个哈希函数对元素进行哈希，并取它们的模64在Q中生成k个索引。

· 在之前计算的索引处，设置为Q中的每一位1

· 对于S中剩下的每个元素，是否执行前面的两个步骤

当我们完成时，我们有一个64位的值Q，其中一些位被设置为1，另一些为0。

如上所述检查位应该是在问:如果还没有设置相应的k位,我们可以确定元素并不是在美国，如果他们都准备好了,我们可以说之前的元素可能被许多其他元素设置为1。事实上，当你不断地在S中添加元素时，越来越多的位在Q中被设置为1，因此你不断地增大了这个概率。

Bloom filters可以产生误报，但不会产生漏报。如果我们增加Q的大小，从而避免了误报的概率。k值对碰撞概率也有影响。这是大小(Q)和k以及误报率之间的权衡。如果你对计算误报率感兴趣，你可以在这里阅读。同时，您可以在这里看到考虑到S或期望的误报率的最佳大小(Q)和k。

还有一个更重要的需要考虑:在q中选择哈希函数来生成索引，之前我提到过MD5或SHA-1，但这些并不是真正明智的选择。加密货币哈希函数试图生成不可逆转的输出。这在这里不是问题。我们对随机输出和尽可能快地进行计算感兴趣，因此有更好的选择。

大多数实现使用一个哈希函数来生成所需的k个输出。特别是MurmurHash 函数，其中计算了一些输出的常数基集，然后通过组合这些哈希值生成k个输出。

还有另一种概率数据结构，称为Count-min sketch，用于估计集合中每一项的概率。其思想与Bloom的工作原理非常相似，因此您可能有兴趣。

如果您对以太坊感兴趣，可以使用Bloom检查某个块是否包含与特定主题相关的日志。在以太坊中，主题与事件和索引参数相关。轻量级客户机不存储关于世界状态、事务或收据的任何数据，它可以非常快速地检查一个块是否包含与感兴趣的任何主题相关的日志。如果Bloom filter检查匹配，考虑到误报的可能性很小，我们可以非常确定这个块包含查询主题的日志条目。分析所有块的所有交易的所有收据的永久成本要大于分析所有块的所有交易的永久成本。

HyperLogLog

HyperLogLog是对以前的LogLog和线性计数等思想的改进，这些思想涉及到可数异的问题。

假设你想知道一个集合S i的基数。e:在s中有多少不同的元素?我们还想在O(1)时空中做这个。引用最初提出这个想法的论文:

例如,新算法可以估计基数远远超出10⁹典型的准确性为2%。这种数据结构中的形式数学要比bloom复杂得多，但其背后的主要思想相当简单。

假设您有一个由8000个随机生成的二进制字符串组成的集合。我们期望有多少个前导至少是3个0 ?至少有3个前导0的概率是1/8，所以，大约，我们可以估计有1000个前导0。当然，由于这是一个随机过程，我们可以从0个二进制字符串中看到满足这个属性的字符串，直到8000，但是每种情况的概率都很重要。更普遍的是,如果我们有n个前导0,然后似乎是合理的基数是2 ^ n。这和投掷一枚硬币100次得到50次正面和50次反面是一样的。

当你深入研究细节时，你很快就会意识到差异是个问题。这是一个很大的问题，因为每一个误差单位都会对估计产生指数级的影响。换种说法，如果我们碰巧有K+1个前导零而不是K个前导零，那么我们的估计就会加倍。改进这方面的思想是将集合划分为多个子集，并使用每个子集中最大前导零的平均值。

从LogLog到HyperLogLog的一个演进是改变估计的均值类型，以控制对异常值的敏感性。特别是，LogLog使用算术平均值，而超LogLog使用调和平均值。此外，偏置校正系数被用来校正更多的剩余偏置。

通过将集合划分为多个集合来重复这个实验是很好的，但是它会产生另一个问题:如果集合的基数太小，那么我们将没有足够的数据来进行统计。

就像在Bloom中一样，每个子集中的每个元素都经过哈希函数处理，以将其转换为一个固定长度的二进制字符串，我们可以从该字符串中遵循上面的逻辑。

总结

我们可以看到，在所有这些情况下，哈希函数都发挥着至关重要的作用。它们优雅地提供了许多对于概率数据结构和算法非常有用的特性:

· 它们将非均匀分布的数据转换成均匀分布的数据，这为概率假设提供了一个起点。

· 数据的统一可以促使数据自动重复或删除，这有助于快速的解决问题。

利用哈希值不可逆性不是一个必然要求，因为非加密哈希函数可以作为一个选择，可以更快地帮助算法的速度。

更多区块链信息：www.qukuaiwang.com.cn/news

声明：登载此文出于传递更多信息之目的，并不意味着赞同其观点或证实其描述。