散列的基本思想：

如果將一個元素放到數(shù)組里面，通常情況就是按順序放椭员，但是在查找的時候，要么執(zhí)行順序查找（第一個津辩，第二個拆撼，....），要么使用二分查找（先排序喘沿，排序涉及到元素的移動）闸度，所以提出hash（哈希函數(shù)，也叫散列函數(shù)）蚜印，根據(jù)散列函數(shù)將要存放的對象做一次運算莺禁，運算之后會得到一個值，這個值就是元素應該放到數(shù)組當中的位置窄赋。當想要查找元素的時候哟冬，通過散列函數(shù)再進行運算楼熄，就會直接定位到所要查找的位置。

但會存在一種沖突情況浩峡，再去添加元素的時候可岂，所要存放的位置已經(jīng)有元素了。這時候會提供一個函數(shù)叫“再散列”翰灾，重新計算值缕粹，放到新的位置。如果再散列又出現(xiàn)沖突的情況纸淮，就不再進行散列了平斩，而認為這個數(shù)組里面的元素已經(jīng)快滿了（比如長度為6，可能裝4個元素咽块，就認為數(shù)組已經(jīng)快滿了）绘面，這時候會開辟一個新的數(shù)組（一個長度更大的數(shù)組），并且將原來數(shù)組里面的元素通過散列放到新的數(shù)組里面侈沪，這時候空余的空間就更大一些揭璃，再往里面放，發(fā)生沖突（碰撞）的概率就降低了亭罪。而什么時候認為快滿了呢塘辅？這個是由load factor（負載因子）決定的。比如load factor為0.75時皆撩，則表示當一個數(shù)組里面75%的位置上已經(jīng)被占據(jù)了元素，那就認為這個數(shù)組已經(jīng)滿了哲银，就會開辟一個新的數(shù)組扛吞。

參看HashMap的構(gòu)造方法：

HashMap的構(gòu)造方法

成員變量loadFactor是float類型的，是對于底層所維護的Hash表的負載因子荆责。

成員變量loadFactor

默認的負載因子滥比，值是0.75f（跟數(shù)據(jù)結(jié)構(gòu)中的hash有關(guān)）。

默認的負載因子

默認的初始化容量做院，必須是2的指數(shù)盲泛。

默認的初始化容量

Entry類型的表（數(shù)組），當需要的時候會重新調(diào)整大小键耕，它的長度必須總是2的指數(shù)寺滚。

會生成一個長度為16的Entry類型的數(shù)組

即：HashMap 底層維護一個數(shù)組，我們向 HashMap 中所放置的對象實際上是存儲在該數(shù)組當中屈雄。

一個包級別的訪問級別村视，我們自己定義的類在外面沒法調(diào)用它，只能java.util包下面的類使用酒奶。

包訪問級別的初始化方法

Entry類型蚁孔，一個內(nèi)部類，實現(xiàn)了Map.Entry接口。

類Entry是內(nèi)部類

HashMap底層維護的Entry類型的數(shù)組予权，每個元素都是Entry類型续崖，Entry類型會維護兩個信息，一個是key的信息鼻百，一個是value的信息绞旅，而key跟value正好是我們往HashMap里面put的那個key跟value。還有一個Entry類型的引用愕宋，用于指向下一個Entry類型的引用玻靡。

HashMap中的put()方法

當向 HashMap 中 put 一對鍵值時，它會根據(jù) key 的 hashCode 值計算出一個位置中贝， 該位置就是此對象準備往數(shù)組中存放的位置囤捻，而這樣做就是為了提高查找的效率，使得查找時間不隨著 HashMap 的大小而改變邻寿。

根據(jù)我們傳過來的鍵的hashCode值蝎土，通過散列函數(shù)計算（根據(jù)經(jīng)驗值計算）一個整數(shù)值，但這個整數(shù)值僅僅是用于存放位置的參考變量绣否，并不是說計算出來這個hash誊涯，它就真的存放在那個位置上了。

indexFor()才是真正決定新增加的Entry對象應該放在什么位置上蒜撮。根據(jù)hash跟數(shù)組長度進行與運算暴构，通過這個計算，返回存放的真正位置 i 段磨。

indexFor()返回存放的真正位置i

將Entry對象放置到那個真正的位置上取逾，將真正的位置 i 傳遞給addEntry()方法。

放置Entry對象

首先把位置 i 上的Entry對象 e 先拿出來苹支，接著構(gòu)造了一個新的Entry對象砾隅，將位置 i 指向了新構(gòu)造的Entry對象。注意：在構(gòu)造新的Entry對象時债蜜，在Entry的構(gòu)造方法中晴埂，e 賦給了next，即新構(gòu)造的Entry對象的下一個引用指向了位置 i 上的Entry對象寻定。

如果再去增加一個對象儒洛，如果正好也是放置到這個位置上，怎么辦呢特姐？回到put()方法參看for循環(huán)晶丘，如果計算出來的那個位置上已經(jīng)有Entry對象了，順著鏈往下走，每次判斷上面的對象是不是一樣的浅浮。

簡而言之：如果該位置沒有對象存在沫浆，就將此對象直接放進數(shù)組當中；如果該位置已經(jīng)有對象存在了滚秩，則順著此存在的對象的鏈開始尋找（Entry 類有一個 Entry 類型的 next 成員變量专执，指向了該對象的下一個對象）， 如果此鏈上有對象的話郁油，再去使用 equals 方 法進行比較本股，如果對此鏈上的某個對象的 equals 方法比較為 false，則將該對象放到數(shù)組當中桐腌，然后將數(shù)組中該位置以前存在的那個對象鏈接到此對象的后面拄显。

之所以需要將數(shù)組位置 i 上的Entry對象鏈到新增的Entry對象的next成員變量上，是因為操作系統(tǒng)的一個理論：最近被訪問的元素案站，在不遠的將來還會被訪問躬审。

HashMap 的內(nèi)存實現(xiàn)布局：

HashMap內(nèi)存布局

（完）