在本节中，我们将了解开放寻址方案中的二次探测技术。有一个普通的哈希函数h’(x) : U → {0, 1, . . ., m – 1}。在开放寻址方案中，实际的哈希函数h(x) 使用普通的哈希函数h’(x) 并附加另一部分来构成一个二次方程。h´ = (𝑥) = 𝑥 𝑚𝑜𝑑 𝑚ℎ(𝑥, 𝑖) = (ℎ´(𝑥) + 𝑖2)𝑚𝑜𝑑 𝑚我们也可以使用一些常数来设置其他二次方程。i 的值 = 0, 1, . . ., m – 1。因此，我们从 i 开始… 阅读更多

在本节中，我们将了解开放寻址方案中的线性探测技术。有一个普通的哈希函数h’(x) : U → {0, 1, . . ., m – 1}。在开放寻址方案中，实际的哈希函数h(x) 使用普通的哈希函数h’(x) 并附加另一部分来构成一个线性方程。h´(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚ℎ(𝑥, 𝑖) = (ℎ´(𝑥) + 𝑖)𝑚𝑜𝑑 𝑚i 的值 | = 0, 1, . . ., m – 1。因此，我们从 i = 0 开始，并增加它，直到找到一个空闲空间。因此，最初… 阅读更多

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

在本节中，我们将了解链式哈希法。链式法是一种冲突解决技术。我们无法避免冲突，但我们可以尝试减少冲突，并尝试为相同的哈希值存储多个元素。此技术假设我们的哈希函数 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]。其中数组的每个元素都是指向链接列表头的指针。指向数组元素 A[i] 的链接列表 Li 包含所有元素 x，使得 h(x) = i。此技术称为链式哈希。在此类哈希表中，如果我们想增加一个元素 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