Java中的哈希

Java中的哈希

哈希技術用於高效地在大量項中查找或存儲項，而不需要遍曆每個項。鍵是哈希值，對象是鍵映射到的值。哈希值還表示項在大型項集合中的位置。java中的哈希函數以整數形式定義並返回對象的值。作為輸出獲得的返回值稱為散列值。哈希值的大小為4字節。相同類型的兩個對象將具有相同的整數值作為哈希值，而不同的對象將具有不同的哈希值。哈希函數是不可逆的，因為對象不能從哈希值導出。

Java中的哈希

哈希函數返回一個與對象對應的整數值。哈希算法操作數據來創建哈希值。哈希值用作哈希表中的索引。數組本身稱為哈希表。哈希表由兩個主要組件組成:桶數組和哈希函數。哈希函數的設計是快速的，在預期的輸入域產生很少的哈希碰撞。哈希函數是兩個函數的組合，首先應用哈希函數，然後應用壓縮函數。如果任何函數產生一個適合作為數組下標的整數，它被稱為哈希函數。

一個好的哈希函數計算起來很快。它必須足夠快來散列任何類型的數據，並在整個散列表中均勻分布實體，以最大限度地減少衝突。它必須服從雪崩效應，即消息的哈希值必須在消息稍有變化時發生變化。

哈希的方法幫助我們找到重複項。哈希表使用哈希函數。它們以鍵和值對的形式存儲數據。該鍵作為哈希函數的輸入，用於標識數據。然後將哈希碼(整數)映射到固定大小。如果兩個哈希值相同，那麼兩個輸入也是相同的。哈希算法有三種:MD5算法、SHA算法、pbkdf2和hmacsha1算法。

Java中的哈希函數用於檢查文件的完整性。他們可以輕鬆有效地比較兩個文件的內容，而無需打開文件。在哈希函數的幫助下，數據結構中的搜索操作變得更快。由於大多數安全算法和協議都使用哈希，因此哈希在數據安全中起著至關重要的作用。它們將數據轉換為更短的固定長度的值或鍵，表示通過網絡發送的原始字符串。

哈希函數有一些局限性。不能實現它們來對數據進行排序。實際上，哈希衝突無法避免，導致效率低下。

Java中的哈希技術

當兩個或多個對象返回相同的哈希值時，就會發生哈希衝突。哈希中使用了兩種技術來處理碰撞。

獨立的鏈接:

具有不同哈希值的對象存儲在不同的bucket中。相反，當兩個或多個對象具有相同的哈希值時，它們將使用稱為鏈表的額外數據結構存儲在相同的bucket位置。這種機製被稱為連鎖。所有相同的哈希值對象使用鏈表鏈接在一起，可以通過遍曆鏈表訪問具有唯一搜索鍵的項。使用單獨鏈接的問題是數據結構可以無限製地增長。

開放尋址:

在這種技術中，所有元素都存儲在bucket數組中。因此，當插入一個新條目時，將檢查桶，從一個散列到槽開始，按照某個探測序列進行，直到找到某個未占用的槽。當搜索一個表項時，桶會按照相同的順序掃描，直到找到該表項或發現一個未使用的數組槽，表明表中沒有這樣的鍵。因此，在哈希表中找到一個未使用或開放的位置稱為開放尋址。在哈希表中定位一個開放位置的過程稱為探測。有三種探測技術。

線性探測是一種處理碰撞的簡單方法，它將碰撞項放置在下一個可用的表單元格中。這個過程繼續進行，直到找到一個可以接受新條目的空桶。線性探測的方法節省空間，但複雜的刪除。碰撞的條目聚集在一起，導致未來的碰撞導致更長的探測序列。

線性探測的主要問題是聚類。當碰撞較少時，探測序列保持較短，可以快速搜索。如果集群內發生碰撞，則會增加集群的大小，從而產生更大的集群，從而延長搜索時間。您可以通過更改探測序列來避免集群問題。

二次調查:
在這種探測技術中，對桶進行迭代嚐試，以找到一個空桶，從而創建二級聚類。填充的數組單元格集以固定的模式在數組周圍跳動。當數組未滿時，此方法可能找不到空槽。

雙重散列:
為了以依賴鍵的方式計算增量，雙重哈希使用第二個哈希函數。第二個哈希函數應該不同於第一個哈希函數，並且依賴於具有非零值的搜索鍵。如果表的大小是質數，那麼Java中的雙重哈希可以到達哈希表中的每個位置。

由於需要嚐試一個更長的數組索引序列來查找給定的元素，當與桶的數組一起使用時，開放尋址方法比單獨鏈接技術要慢得多。