HashMap是java中相當(dāng)重要的數(shù)據(jù)結(jié)構(gòu)，使用HashMap的場(chǎng)景非常之多，因此，了解HashMap實(shí)現(xiàn)的過程和原理，是非常有必要的，在一些面試中也會(huì)經(jīng)常被問到。好了，我們趕緊來研究java內(nèi)部是怎么實(shí)現(xiàn)HashMap的吧！

  首先，我們都知道，數(shù)組的元素查找的效率是不錯(cuò)的，但是涉及到插入操作和刪除操作，效率低下，因?yàn)榭赡軙?huì)涉及到后續(xù)元素位置的遷移。而另外一個(gè)數(shù)據(jù)結(jié)構(gòu)鏈表則很好的解決了這個(gè)問題，插入和刪除操作都只需要改變節(jié)點(diǎn)的指針就行，但是鏈表的檢索的效率就很低了，試想一下，要檢索的元素在鏈表的末尾，而我們只能從鏈表頭開始走完整個(gè)鏈表，才能檢索到這個(gè)元素。而Hash表能給我們帶來高效查詢，插入和刪除。它是怎么做到的呢？

  Hash表的實(shí)質(zhì)是構(gòu)造記錄的存儲(chǔ)位置和其對(duì)應(yīng)的關(guān)鍵字之間的映射函數(shù)f，關(guān)于Hash函數(shù)的構(gòu)造方法，主要有如下幾種：

    （1）直接定址法，取關(guān)鍵字的某個(gè)線性函數(shù)作為Hash函數(shù)即Hash(key) = a*key+b。這種方法很少使用，雖然不會(huì)發(fā)生沖突，但是當(dāng)key非常多的時(shí)候，整張Hash表也會(huì)非常大，畢竟是一一映射的。

    （2）平方取中法，將key的平方的中間幾位數(shù)作為得到的Hash地址。

    （3）除留余數(shù)法，將key除以某個(gè)數(shù)，得到的余數(shù)作為Hash地址。

還有一些方法我們?cè)诖司筒徽f了。當(dāng)多個(gè)關(guān)鍵字經(jīng)過這個(gè)Hash函數(shù)的映射而得到同一個(gè)值的時(shí)候，就發(fā)生了Hash沖突。解決Hash沖突主要有兩種方法：

    （1）開放定址法：