data-structures - 冲突处理中的开放寻址是什么意思？

Question

碰撞发生在散列中，有不同类型的碰撞避免。 1)链接 2)开放寻址等， 什么是开放寻址以及如何在开放寻址中存储索引。计算??

Answer 1

Collision 是数据集 U 中两个或多个数据元素的哈希结果映射到哈希表中的相同位置的情况，称为哈希冲突。在这种情况下，两个或多个数据元素将有资格存储/映射到哈希表中的相同位置。

Open addressing 也称为 closed hashing 是一种通过探测 解决冲突的方法，或者搜索数组中的备用位置，直到找到目标记录，或者找到未使用的数组槽，说明表中没有该键。

在开放寻址中，插入时，如果发生冲突，将尝试替代单元，直到找到空 桶。为此采用了以下技术之一。 探测的方式有很多种:Linear、Quadratic、Cuckoo hashing(我在我的项目中使用过)、double hashing。

现在深入了解探测是什么意思。假设我们想在哈希表中进行插入和搜索操作。

插入:

当发生碰撞时，我们只是探测或转到表中的下一个插槽。 如果它未被占用——我们将 key 存储在那里。 如果它被占用——我们继续探测下一个插槽。

搜索:

如果键散列到一个被占用的位置并且没有匹配， 我们探测下一个位置。

a) 匹配 – 成功搜索

b) 空位置——不成功搜索

c) occupied 和no 匹配——continue 探测。

当到达表的末尾时，探测从开始继续， 直到到达原来的起始位置。

要添加更多内容，在开放式寻址中，我们不需要额外的数据结构来保存数据，就像在封闭式寻址中一样数据存储到一个链表中，其头指针通过一个指针引用，该指针的索引存储在我们的哈希表中。

索引是使用哈希函数为每个键计算的。比方说，在线性探测中，我们需要在哈希表中插入 [20]。

Hashtablesize=20;

void insert(string s)
{
    // Compute the index using the Hash Function
    int index = hashFunc(s);
    // Search for an unused slot and if the index will exceed the hashTableSize
    // we will roll back
    while(hashTable[index] != "")
        index = (index + 1) % hashTableSize;
    hashTable[index] = s;
}

二次探测也类似于线性探测，不同之处在于按探测序列进行迭代。在二次探测中，探测序列可以是

index = index % hashTableSize
index = (index + 1^2) % hashTableSize
index = (index + 2^2) % hashTableSize
index = (index + 3^2) % hashTableSize