資料結構
網路
關係資料庫管理系統
作業系統
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+ 次瀏覽
