前面講解了順序表和鏈表侍芝，兩者的優(yōu)點(diǎn)和缺點(diǎn)都非常明顯。
??順序表特點(diǎn)：尋址容易比勉，插入刪除困難
??鏈表特點(diǎn)?：尋址困難劳较，插入刪除容易
??那么驹止，我們肯定會(huì)想，有沒有這樣一種數(shù)據(jù)結(jié)構(gòu)观蜗，它能融合以上兩種線性表的優(yōu)點(diǎn)即：尋址也容易臊恋，插入刪除也快呢？答案是肯定的墓捻，這就是我們今天要分析的hash表抖仅。
??hash表定義：哈希表（Hash table，也叫散列表）砖第，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)撤卢。也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄梧兼，以加快查找的速度放吩。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表羽杰。
上面的定義來源于百度百科渡紫，定義往往說的不是人話，但我們可以從定義中抓取到幾個(gè)重要的關(guān)鍵詞考赛。
??1.關(guān)鍵碼值
??2.散列函數(shù)
??3.數(shù)組
??4.散列表
??首先惕澎，hash表存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)是一個(gè)數(shù)組，其次存儲(chǔ)數(shù)據(jù)的形式是以key-value的形式來存儲(chǔ)的颜骤，第三數(shù)據(jù)存儲(chǔ)的位置是由指定的散列函數(shù)來決定的唧喉，最終才形成了一個(gè)散列表。
??那么复哆，通過以上信息欣喧，我們可以得到一個(gè)什么信息呢？首先數(shù)據(jù)是存在數(shù)組中的梯找，既然是數(shù)組唆阿，那么我們首先得知道他的大小。其次锈锤，既然是數(shù)組驯鳖，那么它的擴(kuò)容必定是麻煩的，這個(gè)我們后面再講久免。
??通過以上概念浅辙，我們簡(jiǎn)單來走一遍hash表的存儲(chǔ)過程。
??首先阎姥，我們得有一個(gè)散列函數(shù)记舆。簡(jiǎn)單一點(diǎn)f(x)= x mod 10
??其次，我們既然要存儲(chǔ)數(shù)據(jù)呼巴，我們得有一個(gè)數(shù)組泽腮。array[10]
??最后御蒲，我們定義一下我們要存儲(chǔ)的數(shù)據(jù)。前面說到诊赊，hash表存儲(chǔ)的數(shù)據(jù)是key-value這種形式的厚满。那么，我們就定義8對(duì)這樣的數(shù)據(jù)吧碧磅。
??由于本人不喜歡用電腦畫圖碘箍，并且感覺效率比較低，一般我都用筆紙畫鲸郊。
??先看一下我們的準(zhǔn)備工作丰榴。
??一開始，我們的散列表是空的严望，默認(rèn)將它的length設(shè)為10多艇。
??現(xiàn)在，我們根據(jù)散列函數(shù)即f(x)=x mod 10 找到對(duì)應(yīng)數(shù)據(jù)存儲(chǔ)的位置像吻。
??當(dāng)我們?cè)谡?lt;12,6>這對(duì)數(shù)據(jù)的時(shí)候峻黍，我們發(fā)現(xiàn)，a2這個(gè)位置已經(jīng)存儲(chǔ)過數(shù)據(jù)了拨匆。這就有沖突了姆涩。那么，我們要如何來解決這個(gè)沖突呢惭每？ 沖突的解決方式我們可以自己定義骨饿。
??比如說，當(dāng)產(chǎn)生沖突時(shí)台腥，我們往數(shù)組的后一位繼續(xù)查找宏赘，如果不存在數(shù)據(jù)，那么我們就往里存黎侈，如果存在的話就繼續(xù)往下找察署，直到找到空的位置為止。查找的方式也要遵循如上原則峻汉，先通過散列函數(shù)查找到對(duì)應(yīng)的索引位置贴汪，確認(rèn)索引位置的key與我們要查找的key相同，才將數(shù)據(jù)返回休吠；若不相同扳埂，則按照解決沖突的函數(shù)往下找，直到找到對(duì)應(yīng)的key瘤礁，才將對(duì)應(yīng)的value返回阳懂。
最終，我們的數(shù)據(jù)存入hash表中的結(jié)果就是這樣的。
當(dāng)然希太，常見的hash表的存儲(chǔ)肯定不是我們這樣的簡(jiǎn)單克饶，我們只是通過這樣的方式能夠讓大家更容易理解酝蜒。而事實(shí)上誊辉，常見的hash表其實(shí)是通過這樣一種方式來存儲(chǔ)的。
??看到這張圖亡脑，大家是不是很熟悉堕澄？
??先看左邊，是不是就是一個(gè)數(shù)組霉咨。右邊呢蛙紫，就是我們之前分析過的單鏈表。
??這就是為什么我們說hash表融合了順序表和鏈表的優(yōu)點(diǎn)途戒。他的尋址是通過散列函數(shù)找到對(duì)應(yīng)的數(shù)組的索引坑傅，他的數(shù)據(jù)的插入刪除又是以鏈表的形式。所以說hash表尋址也快喷斋，數(shù)據(jù)的插入刪除也快唁毒。
??那么，hash表就沒有缺點(diǎn)了嗎星爪？
??首先浆西，hash表的底層首先是一個(gè)數(shù)組，那么數(shù)組的缺點(diǎn)也是一個(gè)hash表的缺點(diǎn)顽腾，擴(kuò)容的時(shí)候效率低近零，所以我們?cè)谑褂胔ash表的時(shí)候最好是能夠確定他的大小。
??其次抄肖，當(dāng)hash表的散列函數(shù)使用不當(dāng)時(shí)久信，很容易造成沖突，那么當(dāng)一個(gè)hash表存在有大量的沖突數(shù)據(jù)的時(shí)候漓摩，那么他的性能就會(huì)大打折扣裙士。
??在java中，常見的hash表有HashMap和HashTable幌甘。那么潮售，這兩者之間有什么區(qū)別呢？這是在面試過程中我們常被問到的一個(gè)問題锅风。
HashMap和HashTable的區(qū)別表現(xiàn)在以下幾個(gè)方面：
??1.HashMap幾乎可以等價(jià)于HashTable酥诽，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受為null的鍵值(key)和值(value)皱埠，而HashTable則不行)肮帐。
??2.HashMap是非synchronized，而HashTable是synchronized，這意味著HashTable是線程安全的训枢，多個(gè)線程可以共享一個(gè)HashTable托修；而如果沒有正確的同步的話，多個(gè)線程是不能共享HashMap的恒界。Java 5提供了ConcurrentHashMap睦刃，它是HashTable的替代，比HashTable的擴(kuò)展性更好十酣。
??3.另一個(gè)區(qū)別是HashMap的迭代器(Iterator)是fail-fast迭代器涩拙，而HashTable的enumerator迭代器不是fail-fast的。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素）耸采，將會(huì)拋出ConcurrentModificationException兴泥，但迭代器本身的remove()方法移除元素則不會(huì)拋出ConcurrentModificationException異常。但這并不是一個(gè)一定發(fā)生的行為虾宇，要看JVM搓彻。這條同樣也是Enumeration和Iterator的區(qū)別。
??4.由于HashTable是線程安全的也是synchronized嘱朽，所以在單線程環(huán)境下它比HashMap要慢旭贬。如果你不需要同步，只需要單一線程燥翅，那么使用HashMap性能要好過HashTable骑篙。
??5.HashMap不能保證隨著時(shí)間的推移Map中的元素次序是不變的。
有興趣的同學(xué)可以去研究一下二者的源碼森书，來驗(yàn)證一下上面的準(zhǔn)確性靶端。
