在本节中，我们将了解什么是开放寻址哈希。开放寻址是另一种解决冲突的技术。与链式方法不同，它不会将元素插入到其他数据结构中。它将数据插入到哈希表本身。哈希表的尺寸应大于键的数量。开放寻址技术有三种不同的常用方法。这些方法是：线性探测、二次探测和双重哈希。在这种技术中，我们使用类似于其他哈希技术的哈希函数。如果该位置是空闲的，则将元素插入到该位置。现在，如果该位置已… 阅读更多

在本节中，我们将了解什么是链式哈希。链式法是一种解决冲突的技术。我们无法避免冲突，但可以尝试减少冲突，并尝试为相同的哈希值存储多个元素。此技术假设我们的哈希函数 h(x) 的范围为 0 到 6。因此，对于超过 7 个元素，必须有一些元素会被放置在同一个位置。为此，我们将创建一个列表来相应地存储它们。每次我们都将在列表的开头添加元素，以便在 O(1) 时间内执行插入操作。让… 阅读更多

对于任何哈希函数，我们都可以说，如果表大小 m 远小于宇宙大小 u，那么对于任何哈希函数 h，U 的某个大的子集将具有相同的哈希值。为了解决此问题，我们需要一组哈希函数，从中我们可以选择一个对 S 运行良好的函数。如果大多数哈希函数对 S 更好，我们可以选择随机哈希函数。假设 ℌ 是一组哈希函数。我们可以说 ℌ 是通用的，如果对于每个 x、y ∈ U，… 阅读更多

这里我们将讨论乘法哈希方法。为此，我们使用哈希函数：ℎ(𝑥) = ⌊𝑚𝑥𝐴⌋ 𝑚𝑜𝑑 𝑚这里 A 是一个实值常数。此方法的优点是 m 的值不是那么关键。我们也可以将 m 设为 2 的幂。虽然 A 的任何值都会产生哈希函数，但某些 A 值比其他值更好。根据 Knuth 的说法，我们可以使用黄金分割率作为 A，所以 A 将是$$A=\frac{\sqrt5-1}{2}=0.61803398$$当然，无论为 A 选择什么值。鸽巢原理意味着如果 u ≥ … 阅读更多

这里我们将讨论除法哈希。为此，我们使用哈希函数：ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚要使用此哈希函数，我们维护一个数组 A[0, … m – 1]。其中数组的每个元素都是指向链接列表头的指针。链接列表 Li 指向数组元素 A[i]，包含所有满足 h(x) = i 的元素 x。此技术称为链式哈希。在这种哈希表中，如果我们想要增加一个元素 x，这将花费 O(1) 时间。我们计算索引 i = h(x)。… 阅读更多

这里我们将讨论具有整数键的哈希表。这里键值 𝑥 来自宇宙 𝑈，其中 𝑈 = {0, 1, … , 𝑢 – 2, 𝑢 – 1}。哈希函数是 ℎ。此哈希函数的域是 𝑈。范围在集合 {0, 1, … , 𝑚 – 1} 中，并且 𝑚 ≤ 𝑢。如果对于每个 𝑥 ∈ 𝑆，ℎ(𝑥) 都是唯一的，则称哈希函数 h 是集合 𝑆 ⊆ 𝑈 的完美哈希函数。S 的完美哈希函数 ℎ 是最小的… 阅读更多

我们将了解如何从二叉最大堆数据结构中删除元素。假设初始树如下所示：删除算法delete(heap, n) - 开始    如果堆为空，则退出    否则       item := heap[1]       last := heap[n]       n := n – 1       对于 i := 1, j := 2, j = heap[j]，则中断          heap[i] := heap[j]       完成    结束 if    heap[i] := last 结束示例假设我们想要从最终堆中删除 30：-

我们将了解如何从二叉最大堆数据结构中插入和元素。假设初始树如下所示：插入算法insert(heap, n, item) - 开始    如果堆已满，则退出    否则       n := n + 1       对于 i := n, i > 1, 在每次迭代中设置 i := i / 2，执行          如果 item

与二项堆一样，斐波那契堆是树的集合。它们松散地基于二项堆。与二项堆中的树不同，斐波那契堆中的树是有根的但无序的。斐波那契堆中每个节点 x 都包含一个指向其父节点的指针 p[x]，以及一个指向其任意一个子节点的指针 child[x]。x 的子节点通过一个称为 x 的子列表的循环双向链表链接在一起。子列表中的每个子节点 y 都有指针 left[y] 和 right[y] 分别指向 y 的左右兄弟节点。如果节点 y 只是… 阅读更多

二项堆是二项树的集合。二项树 Bk 是一个递归定义的有序树。二项树 B0 由单个节点组成。二项树 Bk 由两个二项树 Bk-1 组成。它们链接在一起。其中一个的根是另一个的左端子节点。一些二项堆如下所示：二项树的一些属性是：Bk 的二项树有 2k 个节点。树的高度是 k深度为 i 的节点正好有 $$\left(\begin{array}{c}k\ j\end{array}\right)$$ 个，对于范围 0 到 k 中的所有 i 二项堆二项堆… 阅读更多