定義
散列表是一種以平均O(1)時間插入跋涣、刪除和查找的數(shù)據(jù)結(jié)構(gòu)许师，可是類似于findMax，findMin等操作則需要以O(shè)(N)的時間才能完成
散列函數(shù)
散列函數(shù)是將關(guān)鍵字計算成Hash值的一個函數(shù)
散列函數(shù)的選擇是非常重要的，它的復(fù)雜度影響著影響著插入、刪除宙址、查找的速度：
- 散列值的計算時間
- 每次操作前需要根據(jù)關(guān)鍵字進行散列，尋找關(guān)鍵字存儲位置
- 散列值的重合度
- 根據(jù)散列沖突（Hash Conflict）的解決方案调卑，從沖突的存儲數(shù)據(jù)中找到真正的數(shù)據(jù)位置
解決Hash沖突
方案1：分離鏈接法
將關(guān)鍵字的Hash值相同的節(jié)點以鏈表的方式進行存儲抡砂，以解決Hash沖突
新插入的節(jié)點都會放在第一個，因為往往新插入的節(jié)點元素最有可能被訪問恬涧，所以插入效率很高注益。
而當(dāng)需要刪除/查找節(jié)點的時候，如果散列函數(shù)的計算出來的值重合度非常高溯捆，那么最壞的情況會將O(1)的常數(shù)時間變成O(N)的線性時間丑搔，因為需要把整個鏈表進行遍歷。也可以用變種的二叉樹進行存儲，也只是將O(N)的時間變成了O(logN)而已低匙。
所以散列函數(shù)的選擇是非常非常重要的，盡量對關(guān)鍵字所計算的時間要短碳锈，并且重合度低才能保證Hash的效率
方案2：開放尋址法-線性探測
根據(jù)關(guān)鍵字散列后顽冶，找到關(guān)鍵字散列位置，查找散列表中離沖突單元最近的空閑單元售碳，并且把新的鍵插入這個空閑單元强重。當(dāng)插入節(jié)點滿了的話，則需要進行擴容贸人。
如下圖：
John Smith和Sandra Dee（都被雜湊映射到了單元873）的沖突间景，借由把后者放在下一個空閑單元（單元874）而解決
當(dāng)查找節(jié)點的時候，找到Hash位置艺智，然后一個個往下找倘要，直到找到節(jié)點或者空節(jié)點才返回。
當(dāng)刪除節(jié)點的時候十拣，單純地清空對應(yīng)的單元是不夠的封拧。這會影響到對于儲存時間早于該單元、但儲存位置在該單元之后的其他鍵夭问，從而對查找產(chǎn)生影響泽西。
相較于直接清空對應(yīng)單元i，更好的做法是先清空缰趋，然后把它之后所有會造成問題的單元向前移動捧杉，來避免搜索出錯。重復(fù)直到出現(xiàn)空單元秘血，則刪除動作安全完成味抖。如下圖：
方案3：開放尋址法-平方探測
與線性探測差不多非竿，只是插入的間隔從1變成了沖突間隔的平方，如A與B沖突了谋竖，而C與AB都沖突了红柱，那么C就會插入到距離A的2*2的空閑位置處。
荷載因子
散列表的載荷因子定義為：A = 填入表中的元素個數(shù) / 散列表的長度
A越大蓖乘，表明填入表中的元素越多锤悄，產(chǎn)生沖突的可能性就越大，A越小嘉抒，標(biāo)明填入表中的元素越少零聚，產(chǎn)生沖突的可能性就越小
對于開放定址法，荷載因子是特別重要因素，應(yīng)嚴格限制在0.7-0.8以下隶症。超過0.8政模，查表時的CPU緩存不命中（cache missing）按照指數(shù)曲線上升。因此蚂会，一些采用開放定址法的hash庫淋样，如Java的系統(tǒng)庫限制了荷載因子為0.75，超過此值將resize散列表
