HashMap是java中相當重要的數據結構，使用HashMap的場景非常之多，因此，了解HashMap實現(xiàn)的過程和原理，是非常有必要的，在一些面試中也會經常被問到。好了，我們趕緊來研究java內部是怎么實現(xiàn)HashMap的吧！

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

  Hash表的實質是構造記錄的存儲位置和其對應的關鍵字之間的映射函數f，關于Hash函數的構造方法，主要有如下幾種：

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

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

    （3）除留余數法，將key除以某個數，得到的余數作為Hash地址。

還有一些方法我們在此就不說了。當多個關鍵字經過這個Hash函數的映射而得到同一個值的時候，就發(fā)生了Hash沖突。解決Hash沖突主要有兩種方法：

    （1）開放定址法：