再平衡算法可以通过以下方式执行：Day-Stout-Warren 算法我们可以使用 Day-Stout-Warren 算法来实现实际的再平衡方法。它是线性于节点数量的。以下是伪代码中基本 DSW 算法的演示。分配一个称为“伪根”的节点，并将树的实际根节点作为伪根的右子节点。调用 tree-to-vine 函数，将树转换为以伪根作为参数的有序链表。调用 vine-to-tree 函数，将有序链表再次转换为树，其参数为伪根和树的大小（元素数量）。树的实际…… 阅读更多

我们首先选择一个内存块。然后，我们在每个块内选择局部布隆过滤器。这可能会导致内存块之间不平衡。此过滤器效率很高，但错误肯定率 (FPR) 很低。最初，分块布隆过滤器的 FPR（错误肯定率）应该与相同大小的标准布隆过滤器相同。分块布隆过滤器由一系列块 b 组成，该块比标准布隆过滤器（布隆过滤器块）小得多，每个块都适合一个缓存行。分块布隆过滤器方案与分区方案不同，在分区方案中，每个位都插入到不同的块中。分块布隆过滤器以以下方式实现：位…… 阅读更多

计数器大小我们必须选择足够大的计数器以避免溢出。泊松逼近建议大小为 4 位/计数器。实现 k = (ln 2)m/n 个计数器的平均负载为 ln 2。计数器负载至少为 16 的概率：≈e-ln2(ln 2)16/16！≈6.78E-17 我们考虑 4 位/计数器进行比较。计数器溢出当计数器溢出时，它可能达到其最大值。这种情况以后只会导致假阴性，如果计数器最终下降到 0，而它应该保持非零值。这种情况的预期时间非常长，但对于任何不允许假…… 阅读更多

基本概念计数布隆过滤器被定义为布隆过滤器的广义数据结构，用于在给定一系列元素时测试给定元素的计数是否小于给定阈值。作为布隆过滤器的广义形式，存在错误肯定匹配的可能性，但没有错误否定的可能性——换句话说，查询返回“可能高于或等于阈值”或“肯定低于阈值”。算法描述在计数布隆过滤器下使用的参数大多与布隆过滤器相同，例如 n，…… 阅读更多

布隆过滤器有三个可以权衡的性能指标：计算或执行时间（对应于哈希函数的数量 k）、过滤器的大小（对应于位数 m）和错误概率（对应于错误肯定率 f = (1 − p)k）。布隆过滤器 (BF) 引入误差容限以提高查找性能和空间效率。布隆过滤器返回真或假。因此，布隆过滤器的结果属于以下类别之一：真阳性、假阳性、真阴性和假阴性。布隆…… 阅读更多

布隆过滤器被定义为一种旨在快速有效地识别集合中元素存在的数据结构。概率数据结构被称为布隆过滤器。此数据结构有助于我们识别元素是否存在于集合中。位向量作为基本数据结构实现。这是一个我们将用来解释的小例子123456789101112131415表中每个空单元格都指定一个位及其下方的数字是其索引或位置。要将元素附加到布隆过滤器，我们只需哈希…… 阅读更多

多选哈希之所以得名，是因为它使用了多个哈希函数的实现。在高层次上，当有多个哈希函数时，每个项目都会映射到多个桶，因此算法设计者可以自由选择项目将驻留在哪个桶中。事实证明，这种自由允许算法获得比使用单个哈希函数获得的分配更平衡的分配。我们将介绍主要的算法思想和用于证明这些算法产生的分配范围的主要数学工具。我们将看到分析是…… 阅读更多

定义动态完美哈希被定义为一种编程方法，用于解决哈希表数据结构中的冲突。应用虽然比哈希表对应物更占用内存，但此方法非常适合必须对大量元素执行快速查询、插入和删除的情况。实现Dietzfelbinger 等人解释了一种动态字典算法，当将一组 m 个项目增量地附加到字典时，成员资格查询始终消耗恒定时间，因此为 O(1) 最坏情况时间，所需的总存储量为 O(m)（线性），并且 O(1) 预期摊销插入和删除时间（摊销恒定时间）。在动态情况下，当…… 阅读更多

完美哈希的定义完美哈希被定义为一种哈希模型，其中任何一组 n 个元素都可以存储在大小相同的哈希表中，并且可以在恒定时间内执行查找。它是由 Fredman、Komlos 和 Szemeredi (1984) 特别发明和讨论的，因此被称为“FKS 哈希”。静态哈希的定义静态哈希定义了另一种哈希问题形式，允许用户对最终字典集执行查找（这意味着字典中的所有对象都是最终的，并且不会更改）。应用由于静态哈希需要数据库、其对象和…… 阅读更多

可合并 DEPQ (MDEPQ) 被定义为 DEPQ（双端优先队列），除了上面列出的 DEPQ 操作外，还包括操作 meld(p, q)……将 DEPQ p 和 q 合并成单个 DEPQ。合并双端优先队列 p 和 q 的结果是一个包含 p 和 q 所有元素的单个双端优先队列。合并操作具有破坏性，因为合并后，p 和 q 不再作为独立的 DEPQ 存在。为了以小于线性时间合并两个 DEPQ，必须使用显式实现…… 阅读更多