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

总对应和叶对应是更复杂的对应技术。在这两种技术中，一半的元素位于最小 PQ 中，另一半位于最大 PQ 中。当元素数量为奇数时，一个元素存储在缓冲区中。此缓冲元素不是任一 PQ 的成员。在总对应技术中，最小 PQ 中的每个元素 x 都与最大 PQ 的不同元素 y 配对。（x，y）是对应元素对，使得 priority(x)

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

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

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

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