哈希表數(shù)據(jù)結(jié)構(gòu)以鍵值對的形式存儲元素，其中

鍵- 用于索引值的唯一整數(shù)

值- 與鍵關(guān)聯(lián)的數(shù)據(jù)。

散列(散列函數(shù))

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

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

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

哈希沖突

當(dāng)哈希函數(shù)為多個(gè)鍵生成相同的索引時(shí)，就會出現(xiàn)沖突(該索引中存儲什么值)。這稱為 哈希沖突。

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

通過鏈接解決沖突

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

1. 通過鏈接解決沖突

在鏈?zhǔn)街校绻粋€(gè)哈希函數(shù)為多個(gè)元素生成相同的索引，則這些元素通過使用雙向鏈表存儲在相同的索引中。

如果j是多個(gè)元素的插槽，則它包含一個(gè)指向元素列表頭部的指針。如果不存在元素，則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

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

ii. 二次探測

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

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

c1和c2是正輔助常數(shù)，

i = {0, 1, ….}

雙哈希

如果在應(yīng)用散列函數(shù)后發(fā)生沖突h(k)，則計(jì)算另一個(gè)散列函數(shù)以查找下一個(gè)時(shí)隙。

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

良好的哈希函數(shù)

一個(gè)好的散列函數(shù)可能無法完全防止沖突，但它可以減少?zèng)_突的數(shù)量。

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

1.除法

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

h(k) = k mod m例如，如果一個(gè)哈希表的大小10和k = 112然后h(k) = 112國防部10 = 2。的值m不能是 的冪2。這是因?yàn)?二進(jìn)制格式的的冪是10, 100, 1000, …. 當(dāng)我們找到 時(shí)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 個(gè)低位

2. 乘法

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

kA mod 1給出小數(shù)部分kA，

⌊ ⌋ 給出底值

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

3. 通用哈希

在通用散列中，散列函數(shù)是隨機(jī)選擇的，與密鑰無關(guān)。

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); 
  } 
} 

哈希表的應(yīng)用

哈希表在何處實(shí)現(xiàn)

需要恒定時(shí)間查找和插入

密碼應(yīng)用

需要索引數(shù)據(jù)

大家如果想了解更多相關(guān)知識，不妨來關(guān)注一下動(dòng)力節(jié)點(diǎn)的Java在線學(xué)習(xí)，里面有更多的知識可以學(xué)習(xí)，從基礎(chǔ)到進(jìn)階的都有，很適合零基礎(chǔ)的小伙伴學(xué)習(xí)哦。