再平衡算法可以按以下方式执行 - 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 所有元素的单个双端优先队列。meld 操作具有破坏性，因为在 meld 之后，p 和 q 不会保留为独立的 DEPQ。为了在不到线性时间内合并两个 DEPQ，有必要使用显式实现的 DEPQ ... 阅读更多