数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究什么是冲突避免技术（DBMS）？
冲突是当应用于哈希表的两个键映射到哈希表中的相同位置时发生的问题。
有两种技术用于避免冲突，它们是：
- 线性探测。
- 链接法。
让我们详细讨论每种技术。
线性探测
线性探测是一种解决冲突的策略。在这种策略中，新键被放置在最接近的下一个空单元格中。
在这里，元素存储在哈希函数映射到哈希表的位置，如果该单元格已满，则搜索下一个连续的位置以存储该值。这里通常使用数组。
步骤 1 - 让我们取一个表 T，它将所有记录存储在内存中。
步骤 2 - 如果内存位置 (h) 已满，则我们将记录存储在下一个空位置。
步骤 3 - 我们在表 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
线性探测的表如下所示：
| 1 | X |
| 2 | C |
| 3 | Z |
| 4 | A |
| 5 | E |
| 6 | Y |
| 7 | |
| 8 | B |
| 9 | |
| 10 | |
| 11 | D |
优点是线性探测非常快，因为使用了局部性原理。
缺点是线性探测需要哈希函数的五路独立性。
最小化聚集的方法
有两种方法用于最小化聚集。这些方法如下：
- 二次探测
假设一个记录的哈希地址 h 已经满了，那么我们搜索地址为 h、h+1、h+4、h+9、h+16、……h+i2、…… 的内存位置，以减少冲突。
- 双重哈希
通过再次对哈希地址进行哈希来解决冲突。所以哈希函数 Hash(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
链接法的表将如下所示：
| 0 | ||||
| 1 | 26 | 16 | NULL | |
| 2 | ||||
| 3 | 38 | NULL | ||
| 4 | 44 | 29 | NULL |
链接法的优点
链接法的优点如下：
即使存储在不同共享位置的键的数量很多，链接哈希表仍然有效。
减少冲突
性能提升。
链接法的缺点
链接法的缺点如下：
存储的键会更多，因为链接哈希表必须为每个数据存储单独的键。
空间开销。
适用于链接列表的所有缺点都适用于链接哈希表。因为它也使用了链接列表逻辑。
2K+ 次浏览
