什么是碰撞避免技术(DBMS)？
冲突是当应用于哈希表的两个键映射到哈希表中的相同位置时发生的问题。
有两种技术可用于避免碰撞，它们是-
线性探测。
链接。
让我们详细讨论每种技术。
线性探测
线性探测是一种解决冲突的策略。在此，新密钥放置在最近的空单元格中。
这里元素存储在哈希函数映射到哈希表的任何位置，如果该单元格被填充，则搜索下一个连续位置以存储该值。这里一般我们使用数组。
步骤1-让我们以一个表T来存储内存中的所有记录。
步骤2-如果内存位置(h)已经填充，那么我们将记录存储在下一个空位置。
Step3-我们在表T中应用线性搜索来找到一个空的内存位置T(h)，T(h+1)，T(h+2)，……..
记录：A、B、C、D、E、X、Y、Z
H(k):4,8,2,11,4,11,5,1
线性探测表如下-
优点是线性探测非常快，这是由于参考使用的局部性。
缺点是线性探测需要散列函数中的五向独立性。
最小化聚类的方法
有两种方法可用于最小化聚类。这些方法如下-
二次探测
假设一条记录的哈希地址为h，已经被填满，那么我们搜索地址为h,h+1,h+4,h+9,h+16,……h+i2,...的内存位置。以减少碰撞。
双哈希
通过再次散列散列地址来解决冲突。所以hashfunctionHash(h)=h'，我们搜索地址为h,h+h',h+2h',h+3h',...的内存位置。
双哈希的优点
双哈希极大地减少了聚类。
双哈希需要较少的比较。
可以使用较小的哈希表。
双哈希最小化重复冲突和聚类的影响，它没有聚类中看到的问题。
双哈希的缺点
双哈希技术非常频繁地填充哈希表，因此我们的性能下降。
下面的事情使处理机制变慢并降低系统质量。
链接
链接被称为链式哈希表机制。顾名思义，它将索引保存在指向链表头部的指针中。
这里使用了链表。每条记录有两部分，如下所示-
用于存储数据的数据部分。
下一部分是链接具有相同哈希地址的记录。
示例
使用链接方法将键25、96、102、162、197存储在哈希表中。
这里，
H(k):k%5
H(26)=26%5=1
H(44)=44%5=4
H(38)=38%5=3
H(29)=29%5=4
H(16)=16%5=1
链接表如下所示-
链式的优势
链接的优点如下-
即使键的数量存储在不同的共享位置，链式哈希表仍然有效。
减少碰撞
性能升级。
链接的缺点
链接的缺点如下-
存储的密钥会更多，因为链式哈希表必须为每个数据存储单独的密钥。
空间开销。
适用于链表的所有缺点都适用于链式哈希表。因为，它也使用链表逻辑。