? ?散列表的英文叫 Hash Table嘀倒，我們平時(shí)也叫它 哈希表 或者 Hash 表剩檀。散列表用的是數(shù)組支持按照下標(biāo)隨機(jī)訪問數(shù)據(jù)的特性限佩，所以散列表其實(shí)就是數(shù)組的一種擴(kuò)展熊尉，由數(shù)組演化而來《凸罚可以說满力，如果沒有數(shù)組，就沒有散列表屋谭。
? 數(shù)組和鏈表都被直接映射到內(nèi)存脚囊，但散列表更復(fù)雜龟糕，它使用?散列函數(shù)?來確定元素的存儲位置桐磁。
??你可能根本不需要自己去實(shí)現(xiàn)散列表，任一優(yōu)秀的語言都提供了散列表實(shí)現(xiàn)讲岁。
? ??一個(gè)通俗的例子是我擂，為了查找電話簿中某人的號碼，可以創(chuàng)建一個(gè)按照人名首字母順序排列的表（即建立人名 X 到首字母F(x)的一個(gè) 函數(shù)關(guān)系）缓艳，在首字母為W的表中查找“王”姓的電話號碼校摩，顯然比直接查找就要快得多。這里使用人名作為關(guān)鍵字 key阶淘，取首字母是這個(gè)例子中散列函數(shù)的函數(shù)法則衙吩，存放首字母的表對應(yīng)散列表。關(guān)鍵字和函數(shù)法則理論上可以任意確定溪窒。
? ??散列表用的就是數(shù)組支持按照下標(biāo)隨機(jī)訪問的時(shí)候坤塞，時(shí)間復(fù)雜度是O(1)的特性冯勉。我們通過散列函數(shù)把元素的鍵值映射為下標(biāo)，然后將數(shù)據(jù)存儲在數(shù)組中對應(yīng)下標(biāo)的位置摹芙。當(dāng)我們按照鍵值查詢元素時(shí)灼狰，我們用同樣的散列函數(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ù)計(jì)算得到的散列值匆帚。
? ? ? ?散列函數(shù)必須滿足一些條件： 1 它必須是一致的军熏；2 它應(yīng)將不同的輸入映射到不同的數(shù)組。
? ? ? ? 設(shè)計(jì)散列函數(shù)必須遵守以下兩個(gè)原則：
? ? ? ? ? ? 1. 散列函數(shù)要盡可能簡單卷扮，能夠快速計(jì)算任意關(guān)鍵字的散列地址荡澎；
? ? ? ? ? ? 2. 散列函數(shù)映射的地址應(yīng)該均勻分布整個(gè)地址空間，避免聚集晤锹，以減少沖突摩幔。
? ? ? ? 簡單總結(jié)就是： 簡單、均勻鞭铆。
散列沖突
? ? 散列函數(shù)總是將不同 的鍵映射到數(shù)組的不同位置或衡。
? ?前面的散列函數(shù)將所有的鍵都映射到一個(gè)位 置，而?最理想的情況?是车遂，散列函數(shù)將鍵均勻地映射到散列表的不同位置封断，但是這個(gè)幾乎不可能，這就會造成 不同的 key 會產(chǎn)生相同的 散列值舶担，這就是 散列沖突坡疼。
? ? 那么如何解決 散列沖突呢，常用的有兩種：
? ? ? ? 1. 開放尋址法
? ? ? ? 2. 鏈表法
? ?2?如果散列表存儲的鏈表很長衣陶，散列表的速度將急劇下降柄瑰。然而，如 果使用的散列函數(shù)很好 剪况，這些鏈表就不會很長教沾！
散列表的應(yīng)用
? ? 散列表作為緩存
? ? ?緩存是一種常用的加速方式，所有大型網(wǎng)站都使用緩存译断，而緩存的數(shù)據(jù)則存儲在散列表中授翻。
散列表適用于：
? ? 仿真映射關(guān)系；防止重復(fù)；緩存/記住數(shù)據(jù)堪唐，以免服務(wù)器在通過處理來生成它們隆箩。
