布隆过滤器被定义为一种数据结构，旨在以快速且内存高效的方式识别元素是否存在于集合中。布隆过滤器实现为一种名为概率数据结构的特定数据结构。这种数据结构帮助我们识别元素是否存在于集合中。位向量被实现为基本数据结构。这是一个我们将用来解释的小例子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，必须使用显式实现来表示 DEPQ ... 阅读更多

总对应和叶子对应是更复杂的对应技术。在这两种技术中，一半的元素位于 min PQ 中，另一半位于 max PQ 中。当元素数量为奇数时，一个元素存储在缓冲区中。此缓冲元素不是任一 PQ 的成员。在总对应技术中，min PQ 中的每个元素 x 都与 max PQ 中的唯一元素 y 配对。(x, y) 是一对对应元素，使得优先级(x)

存在从单端优先队列 (PQ) 数据结构得出高效 DEPQ（双端优先队列）数据结构的一般方法，这些方法还提供了 remove(bNode) 操作的高效实现（此操作从 PQ 中消除节点 bNode）。最简单的方法，即双结构方法，同时维护所有 DEPQ 元素的 min PQ 和 max PQ，这些元素与 min PQ 和 max PQ 节点之间的对应指针相关联，这些指针包含相同的元素。图 D 显示了元素 7、8、3、6、5 的双堆结构。对应指针显示... 阅读更多

双堆存在从单端优先队列 (PQ) 数据结构得出高效 DEPQ（双端优先队列）数据结构的一般方法，这些方法还提供了 remove(aNode) 操作的高效实现（此操作从 PQ 中消除节点 aNode）。最简单的方法，即双结构方法，跟踪所有 DEPQ 元素的 min PQ 和 max PQ，这些元素与 min PQ 和 max PQ 节点之间的对应指针相关联，这些指针包含相同的元素。图 A 显示了元素 7、8、3、6、5 的双堆结构。对应... 阅读更多

现在我们将解释从 deap 数据结构中删除最小元素的技术。在删除过程中，我们的主要目标是从 deaps 中删除最小值。由于树的高度始终为 log n，因此它消耗时间顺序为 log n。我们可以将删除操作讨论如下：过程 deap_deletion(b[],m)：如果(m

要将元素插入 deap 数据结构，我们可能需要如下所示的计算最小值和最大值的程序：过程 min_value(m)：//计算 deap 中的最小值。返回 m-2log2((m-1)；过程 max_value(m)：//计算 deap 中的最大值。返回 m+2log2(m-1)；deap 数据结构中的插入操作可以通过以下方式完成：对于任何堆 b[]，我们应该检查 m 是否是 deap 最大堆内的位置。然后，我们将计算 deap 中的最小值和最大值。现在，比较左子树和右子树的键值。最后，我们执行... 阅读更多