引子
散列的概念應(yīng)用很廣泛，比如加密昌讲，散列表，幾何散列等霹菊。而散列表更是日常工作中常見的數(shù)據(jù)結(jié)構(gòu)剧蚣，同時(shí)也是面試中最常見的面試話題之一支竹，很多問題都可以歸結(jié)到散列表。網(wǎng)上的大部分文章都是直接進(jìn)入hashMap的源碼解讀上鸠按，這會(huì)讓很多剛開始接觸散列表的童鞋覺得如墜霧里礼搁，看的不知所以。我認(rèn)為這是因?yàn)閷?duì)于散列的最基本的概念不熟悉導(dǎo)致的目尖，所以這篇文章立足于散列的基本概念馒吴，層層遞進(jìn)講解散列表，目的是讓不了解散列的同學(xué)讀完這篇文章也能較為深入了解散列表瑟曲。
什么是散列表
提到散列表饮戳，關(guān)鍵的三個(gè)概念是鍵（key）、散列函數(shù)（hash Fuction）洞拨、散列表（hash Table）扯罐。通過wiki的解釋我們可以加深理解散列表是根據(jù)鍵（key）直接訪問內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。即通過調(diào)用一個(gè)散列函數(shù)（形如F(key)）來得到實(shí)際存放位置（散列表）來訪問記錄還有一個(gè)實(shí)際的例子：查找電話簿中某人號(hào)碼烦衣，在首字母為W的表中查找“王”姓的電話號(hào)碼歹河，顯然比直接查找就要快得多。這里使用人名作為關(guān)鍵字花吟，“取首字母”是這個(gè)例子中散列函數(shù)的函數(shù)法則 F()秸歧，存放首字母的表對(duì)應(yīng)散列表。我們可以通過下圖簡(jiǎn)單的模型更加形象的了解散列表衅澈。
為什么會(huì)有散列
hash的概念起源于1956年键菱，dumey用它來解決符號(hào)表問題。使得數(shù)據(jù)表的插入今布、刪除经备、查詢操作都可以在常數(shù)時(shí)間完成。我們常用的arrayList险耀、linkedList一個(gè)善于查詢弄喘、一個(gè)善于新增和刪除，而散列表完美的將兩者的長(zhǎng)處集合甩牺，通過一層散列函數(shù)將數(shù)據(jù)的增刪改查都維持在常數(shù)時(shí)間蘑志，正是這種長(zhǎng)處讓散列如此迷人。
散列深入
接下來我們更加深入的了解散列的內(nèi)容
散列函數(shù)
我們知道散列函數(shù)就是通過key找到對(duì)應(yīng)值的函數(shù)贬派。作為一個(gè)散列函數(shù)急但，唯一的職責(zé)就是將key散列到散列表對(duì)應(yīng)的位置上，從而找到記錄搞乏。那么一個(gè)好的散列函數(shù)應(yīng)該是保證對(duì)于每個(gè)key都均勻的對(duì)應(yīng)到散列表的位置上波桩，而不是每次都對(duì)應(yīng)一個(gè)位置，或者某些位置對(duì)應(yīng)次數(shù)明顯多于其他请敦，這是非常重要的镐躲。因?yàn)樯⒘泻瘮?shù)越好储玫，那么出現(xiàn)散列沖突（見下面散列沖突）的次數(shù)就越少，從而間接提高了整個(gè)散列表的效率萤皂。
散列沖突
所謂散列沖突撒穷，就是多個(gè)key通過散列函數(shù)散列之后對(duì)應(yīng)同一個(gè)地址。出現(xiàn)散列沖突之后我們要進(jìn)行沖突的處理裆熙。通常使用的散列沖突處理方法有兩種端礼。一種是分離鏈接法（拉鏈法），另外一種是開放定址法（探測(cè)散列）入录。下面通過簡(jiǎn)單的散列函數(shù)（除留余數(shù)）來簡(jiǎn)單的介紹這兩種方法蛤奥。
-
分離鏈接: 當(dāng)遇到散列沖突時(shí)，使用鏈表解決僚稿，將沖突的key放到原來數(shù)據(jù)節(jié)點(diǎn)后面凡桥，形成鏈表數(shù)據(jù)結(jié)構(gòu)。我們經(jīng)常使用的
hashmap使用的就是分離鏈接處理散列沖突蚀同。如下圖所示
-
開放定址:遇到散列沖突唬血，一次嘗試余下的單元，直到有空單元唤崭。如下圖
裝填因子
裝填因子一般用λ表示，意義為散列表中的元素個(gè)數(shù)與該表大小的比脖律。如果比例超過了裝填因子谢肾，那么散列表會(huì)擴(kuò)容，然后將原本的數(shù)據(jù)重新散列到新的散列表里小泉，這個(gè)過程稱之為rehash（再散列）芦疏。
越大越好？:一般散列表會(huì)設(shè)置裝填因子微姊，理想的裝填因子當(dāng)然是1酸茴，即填滿散列表，但是實(shí)際上并不是如此兢交。因?yàn)檠b填因子越大意味著發(fā)生散列沖突的概率越大薪捍，而散列沖突對(duì)散列表的效率有影響。這一點(diǎn)不難理解配喳，因?yàn)樯⒘械氖欠癜l(fā)生多少?zèng)_突酪穿，那么查詢修改刪除的時(shí)候也會(huì)遇到同樣次數(shù)的沖突，次數(shù)越多散列表的效率越低晴裹，所以裝填因子不是越大越好而是選擇合適的值被济。
應(yīng)該多大：不同的散列沖突方法采用的裝填因子是不同的。比如分離鏈接采用的裝填因子一般是0.7到0.8涧团，開放定址一般是小于0.5（
hashmap默認(rèn)的裝填因子為0.75）只磷。這是因?yàn)榉蛛x連接采用的是鏈表解決沖突经磅，如果沖突就加到鏈表里，這步動(dòng)作是常數(shù)時(shí)間不論發(fā)生多少次沖突钮追，而對(duì)于開放定址遇到?jīng)_突會(huì)繼續(xù)尋找空單元预厌，如果裝填因子太大，那么沖突次數(shù)會(huì)增多畏陕，影響效率配乓。所以分離連接的裝填因子比開放定址的要大一些。
結(jié)語(yǔ)
本文對(duì)散列表的起源惠毁，基本的概念做了初步的介紹犹芹。理解這些散列表的概念能夠幫助我們?cè)谄匠Ｊ褂蒙⒘斜硐嚓P(guān)的比如hashmap等做到心中有數(shù)，同時(shí)對(duì)理解hashmap的實(shí)現(xiàn)也有很大的幫助鞠绰。篇幅所限腰埂，關(guān)于散列表更加細(xì)致的內(nèi)容此處沒有詳細(xì)講解，但是相信度過的童鞋對(duì)于散列表也應(yīng)該有了初步的理解蜈膨，后續(xù)會(huì)深入研究java中用到散列的集合類屿笼，從而更加深入的理解散列表。
