一、hash中的Key和value的區別

hash中的Key和value本意是鑰匙和值的意思，在應用中通常被用作鍵值對，例如在map、json中等。在鍵值對中，key是關鍵字，value是值，例如：{“firstName”:?“Brett”,?“lastName”:?“McLaughlin”}。在這個json中，firstName和lastName是key，分別對應的value是Brett和McLaughlin。

哈希表基本概念

哈希表（Hash Table）：也叫散列表，是根據關鍵碼值（Key-Value）而直接進行訪問的數據結構，也就是我們常用到的map。

哈希函數：也稱為是散列函數，是Hash表的映射函數，它可以把任意長度的輸入變換成固定長度的輸出，該輸出就是哈希值。哈希函數能使對一個數據序列的訪問過程變得更加迅速有效，通過哈希函數數據元素能夠被很快的進行定位。

若關鍵字為k，則其值存放在f(k)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系f為哈希函數，按這個思想建立的表為哈希表。

設所有可能出現的關鍵字集合記為U(簡稱全集)。實際發生(即實際存儲)的關鍵字集合記為K（|K|比|U|小得多）。

散列方法是使用函數h將U映射到表T[0..m-1]的下標上（m=O(|U|)）。這樣以U中關鍵字為自變量，以h為函數的運算結果就是相應結點的存儲地址。從而達到在O(1)時間內就可完成查找。

其中：

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

② T為哈希表(Hash Table)。

③ h(Ki)(Ki∈U)是關鍵字為Ki結點存儲地址(亦稱散列值或散列地址)。

④ 將結點按其關鍵字的哈希地址存儲到哈希表中的過程稱為散列(Hashing)

延伸閱讀：

二、哈希沖突

1）沖突

　兩個不同的關鍵字，由于散列函數值相同，因而被映射到同一表位置上。該現象稱為沖突(Collision)或碰撞。發生沖突的兩個關鍵字稱為該散列函數的同義詞(Synonym)。

2）安全避免沖突的條件

最理想的解決沖突的方法是安全避免沖突。要做到這一點必須滿足兩個條件：

①其一是|U|≤m

②其二是選擇合適的散列函數。

這只適用于|U|較小，且關鍵字均事先已知的情況，此時經過精心設計散列函數h有可能完全避免沖突。

3）沖突不可能完全避免

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

4）影響沖突的因素

沖突的頻繁程度除了與h相關外，還與表的填滿程度相關。

設m和n分別表示表長和表中填入的結點數，則將α=n/m定義為散列表的裝填因子(Load Factor)。α越大，表越滿，沖突的機會也越大。通常取α≤1。