? ?散列表的英文叫 Hash Table，我們平時也叫它 哈希表 或者 Hash 表。散列表用的是數(shù)組支持按照下標(biāo)隨機訪問數(shù)據(jù)的特性，所以散列表其實就是數(shù)組的一種擴(kuò)展，由數(shù)組演化而來。可以說，如果沒有數(shù)組，就沒有散列表。
? 數(shù)組和鏈表都被直接映射到內(nèi)存，但散列表更復(fù)雜，它使用?散列函數(shù)?來確定元素的存儲位置。
??你可能根本不需要自己去實現(xiàn)散列表，任一優(yōu)秀的語言都提供了散列表實現(xiàn)。
? ??一個通俗的例子是，為了查找電話簿中某人的號碼，可以創(chuàng)建一個按照人名首字母順序排列的表（即建立人名 X 到首字母F(x)的一個 函數(shù)關(guān)系），在首字母為W的表中查找“王”姓的電話號碼，顯然比直接查找就要快得多。這里使用人名作為關(guān)鍵字 key，取首字母是這個例子中散列函數(shù)的函數(shù)法則，存放首字母的表對應(yīng)散列表。關(guān)鍵字和函數(shù)法則理論上可以任意確定。
? ??散列表用的就是數(shù)組支持按照下標(biāo)隨機訪問的時候，時間復(fù)雜度是O(1)的特性。我們通過散列函數(shù)把元素的鍵值映射為下標(biāo)，然后將數(shù)據(jù)存儲在數(shù)組中對應(yīng)下標(biāo)的位置。當(dāng)我們按照鍵值查詢元素時，我們用同樣的散列函數(shù)，將鍵值轉(zhuǎn)化數(shù)組下標(biāo)，從對應(yīng)的數(shù)組下標(biāo)的位置取數(shù)據(jù)。
散列函數(shù)
? ? ? ? 散列函數(shù)又稱 哈希函數(shù)，是將關(guān)鍵字映射到存儲地址的函數(shù)（將輸入映射到數(shù)字），我們可以把它定義成 hash(key) = Addr。其中key表示元素的鍵值，hash(key)的值表示經(jīng)過散列函數(shù)計算得到的散列值。
? ? ? ?散列函數(shù)必須滿足一些條件： 1 它必須是一致的；2 它應(yīng)將不同的輸入映射到不同的數(shù)組。
? ? ? ? 設(shè)計散列函數(shù)必須遵守以下兩個原則：
? ? ? ? ? ? 1. 散列函數(shù)要盡可能簡單，能夠快速計算任意關(guān)鍵字的散列地址；
? ? ? ? ? ? 2. 散列函數(shù)映射的地址應(yīng)該均勻分布整個地址空間，避免聚集，以減少沖突。
? ? ? ? 簡單總結(jié)就是： 簡單、均勻。
散列沖突
? ? 散列函數(shù)總是將不同 的鍵映射到數(shù)組的不同位置。
? ?前面的散列函數(shù)將所有的鍵都映射到一個位 置，而?最理想的情況?是，散列函數(shù)將鍵均勻地映射到散列表的不同位置，但是這個幾乎不可能，這就會造成 不同的 key 會產(chǎn)生相同的 散列值，這就是 散列沖突。
? ? 那么如何解決 散列沖突呢，常用的有兩種：
? ? ? ? 1. 開放尋址法
? ? ? ? 2. 鏈表法
? ?2?如果散列表存儲的鏈表很長，散列表的速度將急劇下降。然而，如 果使用的散列函數(shù)很好 ，這些鏈表就不會很長！
散列表的應(yīng)用
? ? 散列表作為緩存
? ? ?緩存是一種常用的加速方式，所有大型網(wǎng)站都使用緩存，而緩存的數(shù)據(jù)則存儲在散列表中。
散列表適用于：
? ? 仿真映射關(guān)系；防止重復(fù)；緩存/記住數(shù)據(jù)，以免服務(wù)器在通過處理來生成它們。
