哈希表數據結構以鍵值對的形式存儲元素，其中

鍵- 用于索引值的唯一整數

值- 與鍵關聯的數據。

散列(散列函數)

在哈希表中，使用鍵處理新索引。并且，對應于該鍵的元素存儲在索引中。這個過程稱為散列。

讓 克 成為鑰匙和小時(x) 是一個哈希函數。

這里， h(k) 會給我們一個新的索引來存儲鏈接的元素克.

哈希沖突

當哈希函數為多個鍵生成相同的索引時，就會出現沖突(該索引中存儲什么值)。這稱為 哈希沖突。

我們可以使用以下技術之一解決哈希沖突。

通過鏈接解決沖突

開放尋址：線性/二次探測和雙散列

1. 通過鏈接解決沖突

在鏈式中，如果一個哈希函數為多個元素生成相同的索引，則這些元素通過使用雙向鏈表存儲在相同的索引中。

如果j是多個元素的插槽，則它包含一個指向元素列表頭部的指針。如果不存在元素，則j包含NIL。

操作偽代碼

chainedHashSearch(T, k)
  return T[h(k)]
chainedHashInsert(T, x)
  T[h(x.key)] = x //insert at the head
chainedHashDelete(T, x)
  T[h(x.key)] = NIL

線性探測的問題是填充了一組相鄰的插槽。插入新元素時，必須遍歷整個簇。這增加了對哈希表執行操作所需的時間。

ii. 二次探測

它的工作原理類似于線性探測，但通過使用以下關系增加了插槽之間的間距(大于 1)。

h(k, i) = (h′(k) + c1i + c2i2) mod m在哪里，

c1和c2是正輔助常數，

i = {0, 1, ….}

雙哈希

如果在應用散列函數后發生沖突h(k)，則計算另一個散列函數以查找下一個時隙。

h(k, i) = (h1(k) + ih2(k)) mod m

良好的哈希函數

一個好的散列函數可能無法完全防止沖突，但它可以減少沖突的數量。

在這里，我們將研究不同的方法來找到一個好的哈希函數

1.除法

如果k是一個鍵并且m是哈希表的大小，則哈希函數h()計算如下：

h(k) = k mod m例如，如果一個哈希表的大小10和k = 112然后h(k) = 112國防部10 = 2。的值m不能是 的冪2。這是因為2二進制格式的的冪是10, 100, 1000, …. 當我們找到 時k mod m，我們總是會得到低階 p 位。

如果 m = 22, k = 17，則 h(k) = 17 mod 22 = 10001 mod 100 = 01

如果 m = 23, k = 17，則 h(k) = 17 mod 22 = 10001 mod 100 = 001

如果 m = 24, k = 17，則 h(k) = 17 mod 22 = 10001 mod 100 = 0001

如果 m = 2p，則 h(k) = m 的 p 個低位

2. 乘法

h(k) = ⌊m(kA mod 1)⌋在哪里，

kA mod 1給出小數部分kA，

⌊ ⌋ 給出底值

A是任意常數。的值A介于 0 和 1 之間。但是，≈ (√5-1)/2Knuth會建議最佳選擇。

3. 通用哈希

在通用散列中，散列函數是隨機選擇的，與密鑰無關。

Java示例

// Java program to demonstrate working of HashTable 
import java.util.*; 
class HashTable { 
  public static void main(String args[]) 
  {
  Hashtable<Integer, Integer> 
    ht = new Hashtable<Integer, Integer>();   
  ht.put(123, 432); 
  ht.put(12, 2345);
  ht.put(15, 5643); 
  ht.put(3, 321);
  ht.remove(12);
  System.out.println(ht); 
  } 
} 

哈希表的應用

哈希表在何處實現

需要恒定時間查找和插入

密碼應用

需要索引數據

大家如果想了解更多相關知識，不妨來關注一下動力節點的Java在線學習，里面有更多的知識可以學習，從基礎到進階的都有，很適合零基礎的小伙伴學習哦。