散列表（也叫哈希表)是根據(jù)鍵而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結構悼沈，它通過計算一個關于鍵值的函數(shù)烈炭，將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄挎袜，這加快了查找速度窘游。這個映射函數(shù)稱做散列函數(shù)况芒，存放記錄的數(shù)組稱做散列表惜纸，大多數(shù)編程語言都提供了散列表的實現(xiàn)，例如Python中的dict绝骚，C++中的map耐版。
散列函數(shù)
散列函數(shù)是這樣的函數(shù)，既無論你給它什么數(shù)據(jù)压汪，它都返回一個數(shù)字粪牲，同時散列函數(shù)還遵循兩個規(guī)則：
- 對于同樣的輸入數(shù)據(jù)，返回的數(shù)字必須是一樣的止剖。
- 對于不同的輸入數(shù)據(jù)腺阳，它應該盡可能返回不同的結果。
沖突
對于不同的鍵穿香，散列函數(shù)返回的結果相同亭引，這種情況被稱為沖突，這種情況雖然少皮获，但也確實存在焙蚓。
處理沖突的方法很多，最簡單的辦法是如果多個鍵映射到了同一個位置洒宝，就在這個位置存儲一個鏈表购公，在鏈表里存放沖突的鍵和值，當查找到?jīng)_突的鍵時去鏈表里再查一次雁歌，由于沖突一般情況下很少宏浩，所以鏈表一般很短，對查找速度影響不大将宪。
性能
散列表的查找绘闷，插入，刪除的平均時間都很快為O(1)较坛，但最差時間為O(n)印蔗，沖突越多散列表的性能越差，避免沖突需要有較低的填裝因子和良好的散列函數(shù)丑勤。
填裝因子指的是散列表包含的元素數(shù)除以散列表長度华嘹，填裝因子越低，發(fā)生沖突的可能性越小法竞，一個不錯的經(jīng)驗規(guī)則是：一旦填裝因子大于0.7就調(diào)整散列表的長度耙厚。不要頻繁調(diào)整散列表長度强挫，因為它的開銷很大。
