前面講解了順序表和鏈表，兩者的優(yōu)點(diǎn)和缺點(diǎn)都非常明顯。
??順序表特點(diǎn)：尋址容易，插入刪除困難
??鏈表特點(diǎn)?：尋址困難，插入刪除容易
??那么，我們肯定會(huì)想，有沒(méi)有這樣一種數(shù)據(jù)結(jié)構(gòu)，它能融合以上兩種線性表的優(yōu)點(diǎn)即：尋址也容易，插入刪除也快呢？答案是肯定的，這就是我們今天要分析的hash表。
??hash表定義：哈希表（Hash table，也叫散列表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
上面的定義來(lái)源于百度百科，定義往往說(shuō)的不是人話(huà)，但我們可以從定義中抓取到幾個(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的形式來(lái)存儲(chǔ)的，第三數(shù)據(jù)存儲(chǔ)的位置是由指定的散列函數(shù)來(lái)決定的，最終才形成了一個(gè)散列表。
??那么，通過(guò)以上信息，我們可以得到一個(gè)什么信息呢？首先數(shù)據(jù)是存在數(shù)組中的，既然是數(shù)組，那么我們首先得知道他的大小。其次，既然是數(shù)組，那么它的擴(kuò)容必定是麻煩的，這個(gè)我們后面再講。
??通過(guò)以上概念，我們簡(jiǎn)單來(lái)走一遍hash表的存儲(chǔ)過(guò)程。
??首先，我們得有一個(gè)散列函數(shù)。簡(jiǎn)單一點(diǎn)f(x)= x mod 10
??其次，我們既然要存儲(chǔ)數(shù)據(jù)，我們得有一個(gè)數(shù)組。array[10]
??最后，我們定義一下我們要存儲(chǔ)的數(shù)據(jù)。前面說(shuō)到，hash表存儲(chǔ)的數(shù)據(jù)是key-value這種形式的。那么，我們就定義8對(duì)這樣的數(shù)據(jù)吧。
??由于本人不喜歡用電腦畫(huà)圖，并且感覺(jué)效率比較低，一般我都用筆紙畫(huà)。
??先看一下我們的準(zhǔn)備工作。
??一開(kāi)始，我們的散列表是空的，默認(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ǔ)過(guò)數(shù)據(jù)了。這就有沖突了。那么，我們要如何來(lái)解決這個(gè)沖突呢？ 沖突的解決方式我們可以自己定義。
??比如說(shuō)，當(dāng)產(chǎn)生沖突時(shí)，我們往數(shù)組的后一位繼續(xù)查找，如果不存在數(shù)據(jù)，那么我們就往里存，如果存在的話(huà)就繼續(xù)往下找，直到找到空的位置為止。查找的方式也要遵循如上原則，先通過(guò)散列函數(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)然，常見(jiàn)的hash表的存儲(chǔ)肯定不是我們這樣的簡(jiǎn)單，我們只是通過(guò)這樣的方式能夠讓大家更容易理解。而事實(shí)上，常見(jiàn)的hash表其實(shí)是通過(guò)這樣一種方式來(lái)存儲(chǔ)的。
??看到這張圖，大家是不是很熟悉？
??先看左邊，是不是就是一個(gè)數(shù)組。右邊呢，就是我們之前分析過(guò)的單鏈表。
??這就是為什么我們說(shuō)hash表融合了順序表和鏈表的優(yōu)點(diǎn)。他的尋址是通過(guò)散列函數(shù)找到對(duì)應(yīng)的數(shù)組的索引，他的數(shù)據(jù)的插入刪除又是以鏈表的形式。所以說(shuō)hash表尋址也快，數(shù)據(jù)的插入刪除也快。
??那么，hash表就沒(méi)有缺點(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中，常見(jiàn)的hash表有HashMap和HashTable。那么，這兩者之間有什么區(qū)別呢？這是在面試過(guò)程中我們常被問(wèn)到的一個(gè)問(wèn)題。
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；而如果沒(méi)有正確的同步的話(huà)，多個(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性能要好過(guò)HashTable。
??5.HashMap不能保證隨著時(shí)間的推移Map中的元素次序是不變的。
有興趣的同學(xué)可以去研究一下二者的源碼，來(lái)驗(yàn)證一下上面的準(zhǔn)確性。
