散列表是什么：

散列表（Hash table，也叫哈希表），是根據(jù)關鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結構也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

簡單來說就是我們要存一組數(shù)據(jù)，我們可以拿他的關鍵值（key）通過散列函數(shù)的到散列值，以散列值為下標存入數(shù)組。

但是隨著數(shù)據(jù)量的增加會出現(xiàn)哈希沖突這種情況

何為哈希沖突？

用散列函數(shù)得到的散列值在數(shù)據(jù)量大的情況下是會重復的，這種情況無法避免，那么我要存的數(shù)據(jù)的位置給之前的數(shù)據(jù)占了，尷尬了，到底要存哪呢？這就是所謂的哈希沖突。

解決途徑：

介紹兩種方法：

1、開放尋址法
如果發(fā)生了哈希沖突，需要找個新的位置存進去，這個位置要探測出來，探測的方法有許多種，舉一個簡單的辦法，線性探測

這種方法就是，從沖突的地方繼續(xù)往下找空閑的位置，找到就插進去，遍歷到數(shù)組末尾沒找到，就從頭找，如果回到?jīng)_突位置就滿了，考慮動態(tài)擴容問題（有點類似數(shù)組動態(tài)擴容，但是要解決數(shù)據(jù)量過大數(shù)據(jù)搬遷的時效問題）

查找的方法也一樣，通過散列值找，然后比較下標為散列值的元素與要查找的元素，相等說明找到了，沒找到就繼續(xù)順序往后找，直到找到空閑位置，那就是該元素壓根就不在這散列表里。

刪除操作則需在刪除的位置打上標記，免的查的時候出錯了。

2、鏈表法

把哈希表中的每一位置看做是桶或者槽（實際上是一條條鏈表），哈希沖突時只需將數(shù)據(jù)插入到該散列值對應的鏈表中即可，查找的時候就遍歷這條鏈表，對比是否有相同的元素，插入時間復雜度為O（1）。

散列表的核心就是散列函數(shù)的設計，還有哈希沖突。

補充：
當裝載因子（存的元素數(shù)/散列表大小）過大時，出現(xiàn)沖突的可能性就越大，那么此時散列表可能會退化鏈表，遍歷起來耗時長。
關于動態(tài)擴容問題，動態(tài)擴容的話會導致散列函數(shù)出現(xiàn)變化，從而導致散列值出現(xiàn)變化，所有的數(shù)據(jù)要重新計算并且遷移都是十分耗費時間的，比方說幾G的數(shù)據(jù)需要重新算又要移動位置，需要耗費相當?shù)臅r間，解決這個問題的方法是搞個新的散列表，這個新的散列表的大小是原先的2倍或者幾倍，然后把新的值插入新的散列表里，每插一個新值，就把舊的值搬一個到新的表，慢慢地實現(xiàn)更替，然后查詢的時候先查新的再查舊的。