在本节中，我们将了解开放寻址方案中的二次探测技术。有一个普通的哈希函数 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]。其中数组的每个元素都是指向链接列表头的指针。链接列表 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