合并哈希

原文：https://www.geeksforgeeks.org/coalesced-hashing/

合并哈希是在存在固定大小的数据时的避免冲突技术。 它是单链接和开放地址的组合。 它使用开放寻址（线性探测）的概念从哈希表的底部查找冲突元素的第一个空白位置，并使用单链接的概念通过指针将冲突元素彼此链接。 使用的哈希函数为h = key % (键总数)。 在哈希表中，每个节点具有三个字段：

• h(key)：键的哈希函数的值。

• data：键本身。

• next：指向下一个碰撞元素的链接。

合并哈希的基本操作是：

1. INSERT(key)：如果表中的哈希值为空，则插入操作将根据该键的哈希值插入键，否则，将键插入哈希表底部的第一个空位置，并将此空位置的地址映射到指向该节点的链中上一个节点的NEXT字段中（在以下示例中进行解释）。

2. DELETE(key)：删除该键（如果存在）。此外，如果要删除的节点包含哈希表中另一个节点的地址，则该地址将映射到指向要删除的节点的节点的NEXT字段中。

3. SEARCH(key)：如果存在键，则返回Yes，否则返回No。

所有这些操作的最佳情况复杂度为O(1)，最坏情况复杂度为O(n)，其中n是键的总数，它比单链接要好，因为它将冲突元素插入哈希表的内存中，仅代替在单独的链接中创建新的链表。

插图：

示例：

n = 10
Input : {20, 35, 16, 40, 45, 25, 32, 37, 22, 55}

哈希函数

h(key) = key%10

步骤：

1. 最初创建的空哈希表的所有NEXT字段都初始化为NULL，h(key)值的范围为 0-9。

1. 让我们从插入 20 开始，因为h(20) = 0并且 0 索引为空，所以我们在 0 索引处插入 20。

1. 下一个要插入的元素是 35，h(35) = 5，第 5 个索引为空，因此我们在此处插入 35。

1. 接下来，我们有 16，h(16) = 6是空的，所以在 6 索引值处插入了 16。

1. 现在我们必须插入 40，h(40) = 0，它已经被占用了，所以我们从底部开始搜索第一个空块并将其插入，即 9 索引值。 在第 0 个索引值节点的next字段中初始化节点的索引值（即（9））。

1. 要插入 45，则 h(45) = 5被占用，因此我们再次从底部搜索空块，即 8 索引值，并将此新插入的节点（即（8））的地址映射到第 5 个索引值节点的Next字段。 即在key = 35的next字段中。

1. 在插入 25 旁边，h(25) = 5被占用，因此从底部开始搜索第一个空块，即第 7 个索引值，然后在其中插入 25。 现在，重要的是要注意，该新节点的地址不能映射到已经指向某个其他节点的第 5 个索引值节点上。 要插入新节点的地址，我们必须遵循第 5 个索引节点的链接链，直到在next字段中获得NULL，然后将新节点的地址映射到该节点的next字段，即，从第 5 个索引节点开始，我们进入第 8 个索引节点，它的next字段中包含NULL，因此我们在第 8 个索引节点的next字段中插入新节点的地址（即（7））。

1. 要插入 32，h(32) = 2，该值为空，因此在第二个索引值处插入 32。

1. 要插入 37（h(37) = 7），请从底部开始搜索第四个索引值即第一个空闲块。 因此，在第 4 个索引值处插入 37，并将该节点的地址复制到第 7 个索引值节点的next字段中。

1. 要插入 22，则占用h(22) = 2，因此将其插入第三个索引值并将该节点的地址映射到第二个索引值节点的next字段中。

1. 最后，要插入 55，h(55) = 5，它已被占用，唯一的空白空间是第一个索引值，因此在此处插入 55。 现在再次映射此新节点的地址，我们必须遵循从第 5 个索引值节点开始的链，直到在next字段中获得NULL，即第 5 个索引 -> 第 8 个索引 -> 第 7 个索引 -> 第 4 个索引（在Next中包含NULL），然后将新插入的节点的地址插入第 4 个索引值节点。

删除的过程很简单，例如：

情况 1：要删除key = 37，请先搜索 37。如果存在，则只需删除数据值，如果节点的next字段中包含任何地址，并且该节点将被删除，即 37 本身由其他某个节点指向（即key = 25），然后将该地址在next字段 37 中复制到指向 37 的节点的next字段（即key = 25），然后将key = 37的NEXT字段再次初始化为NULL，然后删除key = 37。

情况 2：如果要删除的键是 35，而其他任何节点均未指向该键，则我们必须将连接到要删除的节点的链拉回去，即向后退 35，并将链的最后一个值再次标记为NULL。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://www.moonapi.com/news/32377.html