一、hash中的Key和value的區(qū)別

hash中的Key和value本意是鑰匙和值的意思，在應(yīng)用中通常被用作鍵值對(duì)，例如在map、json中等。在鍵值對(duì)中，key是關(guān)鍵字，value是值，例如：{“firstName”:?“Brett”,?“l(fā)astName”:?“McLaughlin”}。在這個(gè)json中，firstName和lastName是key，分別對(duì)應(yīng)的value是Brett和McLaughlin。

哈希表基本概念

哈希表（Hash Table）：也叫散列表，是根據(jù)關(guān)鍵碼值（Key-Value）而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，也就是我們常用到的map。

哈希函數(shù)：也稱(chēng)為是散列函數(shù)，是Hash表的映射函數(shù)，它可以把任意長(zhǎng)度的輸入變換成固定長(zhǎng)度的輸出，該輸出就是哈希值。哈希函數(shù)能使對(duì)一個(gè)數(shù)據(jù)序列的訪問(wèn)過(guò)程變得更加迅速有效，通過(guò)哈希函數(shù)數(shù)據(jù)元素能夠被很快的進(jìn)行定位。

若關(guān)鍵字為k，則其值存放在f(k)的存儲(chǔ)位置上。由此，不需比較便可直接取得所查記錄。稱(chēng)這個(gè)對(duì)應(yīng)關(guān)系f為哈希函數(shù)，按這個(gè)思想建立的表為哈希表。

設(shè)所有可能出現(xiàn)的關(guān)鍵字集合記為U(簡(jiǎn)稱(chēng)全集)。實(shí)際發(fā)生(即實(shí)際存儲(chǔ))的關(guān)鍵字集合記為K（|K|比|U|小得多）。

散列方法是使用函數(shù)h將U映射到表T[0..m-1]的下標(biāo)上（m=O(|U|)）。這樣以U中關(guān)鍵字為自變量，以h為函數(shù)的運(yùn)算結(jié)果就是相應(yīng)結(jié)點(diǎn)的存儲(chǔ)地址。從而達(dá)到在O(1)時(shí)間內(nèi)就可完成查找。

其中：

① h：U→{0，1，2，…，m-1} ，通常稱(chēng)h為哈希函數(shù)(Hash Function)。哈希函數(shù)h的作用是壓縮待處理的下標(biāo)范圍，使待處理的|U|個(gè)值減少到m個(gè)值，從而降低空間開(kāi)銷(xiāo)。

② T為哈希表(Hash Table)。

③ h(Ki)(Ki∈U)是關(guān)鍵字為Ki結(jié)點(diǎn)存儲(chǔ)地址(亦稱(chēng)散列值或散列地址)。

④ 將結(jié)點(diǎn)按其關(guān)鍵字的哈希地址存儲(chǔ)到哈希表中的過(guò)程稱(chēng)為散列(Hashing)

延伸閱讀：

二、哈希沖突

1）沖突

　兩個(gè)不同的關(guān)鍵字，由于散列函數(shù)值相同，因而被映射到同一表位置上。該現(xiàn)象稱(chēng)為沖突(Collision)或碰撞。發(fā)生沖突的兩個(gè)關(guān)鍵字稱(chēng)為該散列函數(shù)的同義詞(Synonym)。

2）安全避免沖突的條件

最理想的解決沖突的方法是安全避免沖突。要做到這一點(diǎn)必須滿(mǎn)足兩個(gè)條件：

①其一是|U|≤m

②其二是選擇合適的散列函數(shù)。

這只適用于|U|較小，且關(guān)鍵字均事先已知的情況，此時(shí)經(jīng)過(guò)精心設(shè)計(jì)散列函數(shù)h有可能完全避免沖突。

3）沖突不可能完全避免

通常情況下，h是一個(gè)壓縮映像。雖然|K|≤m，但|U|>m，故無(wú)論怎樣設(shè)計(jì)h，也不可能完全避免沖突。因此，只能在設(shè)計(jì)h時(shí)盡可能使沖突最少。同時(shí)還需要確定解決沖突的方法，使發(fā)生沖突的同義詞能夠存儲(chǔ)到表中。

4）影響沖突的因素

沖突的頻繁程度除了與h相關(guān)外，還與表的填滿(mǎn)程度相關(guān)。

設(shè)m和n分別表示表長(zhǎng)和表中填入的結(jié)點(diǎn)數(shù)，則將α=n/m定義為散列表的裝填因子(Load Factor)。α越大，表越滿(mǎn)，沖突的機(jī)會(huì)也越大。通常取α≤1。