在本节中，我们将了解什么是 LCFS 哈希。这是一种开放寻址策略，它改变了冲突解决策略。如果我们检查开放寻址方案中哈希的算法，我们可以发现如果两个元素发生冲突，那么哪个优先级更高，将被插入到表中，后续元素必须继续移动。因此，我们可以说开放寻址方案中的哈希是 FCFS 标准。使用 LCFS（后进先出）方案。任务的执行方式完全相反。当我们插入一个元素时，它将被放置在位置... 阅读更多

在本节中，我们将了解什么是非对称哈希技术。在这种技术中，哈希表被分成 d 个块。每个拆分长度为 n/d。探测值 xi，0 ≤ i ≤ d，是从 $$\lbrace\frac{i*n}{d}, ..., \frac{(i+1)*n}{d-1}\rbrace$$ 中均匀抽取的。与多选哈希一样，要插入 x，算法检查列表 A[x0]、A[x1]、...、A[xd – 1] 的长度。然后将 x 附加到这些列表中最短的列表中。如果出现平局，则将其插入到索引最小的列表中。根据 Vocking，预期长度为... 阅读更多

这里我们将了解什么是平衡二叉搜索树。二叉搜索树 (BST) 是二叉树，其左子节点具有较小的元素，右子节点具有较大的元素。在 BST 中搜索元素的平均时间复杂度为 O(log n)。它取决于二叉搜索树的高度。为了维护二叉搜索树的特性，有时树会变得倾斜。因此，倾斜的树将如下所示 -这实际上是一棵树，但它看起来像一个链表。对于这种类型的树，搜索时间将为... 阅读更多

在本节中，我们将了解与开放寻址哈希相关的 Brent 方法。此方法是一种启发式方法。这试图最小化哈希表中成功搜索的平均时间。此方法最初应用于双重哈希技术，但可用于任何开放寻址技术，如线性探测和二次探测。存储在开放寻址哈希表中的元素 x 的年龄是 i 的最小值，使得 x 被放置在 A[xi] 中。Brent 方法试图最小化所有元素的总年龄。如果我们插入一个元素 x，... 阅读更多

在本节中，我们将了解开放寻址方案中的双重哈希技术。存在一个普通的哈希函数 h´(x) : U → {0, 1, . . ., m – 1}。在开放寻址方案中，实际的哈希函数 h(x) 在空间未满时采用普通的哈希函数 h’(x)，然后执行另一个哈希函数以获取一些插入空间。$$h_{1}(x)=x\:mod\:m$$$$h_{2}(x)=x\:mod\:m^{\prime}$$$$h(x, i)=(h^{1}(x)+ih^{2})\:mod\:m$$i 的值为 0、1、...、m – 1。因此，我们从 i = 0 开始，并增加它，直到我们获得一个空闲空间。因此，最初当 i = ... 阅读更多

在本节中，我们将了解开放寻址方案中的二次探测技术。存在一个普通的哈希函数 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，... 阅读更多