1.HashMap的社會關系
HashMap的爸爸是AbstractMap，他的老師Cloneable教會了他如何復制，老師Serializable教會了他如何序列化，老師Map也是他爸爸的老師，教會了他們爺倆如何好好做一個Map，
2.HashMap的自我介紹
再說下HashMap自己，我們先把他當成是一個key/value存盤的容器吧，就像是下面這個寄存柜，一個人可以保存一樣物品，多了會替換前面的，
門牌號就是Hash，你的身份證就是Key，里面的書包就是Value，
3.HashMap的作用
1.你把身份證和書包（Key-Value）給管理員（JVM），然后你就可以溜了，
2.管理員苦逼的先用Hash演算法算你的身份證號，得到了一個柜門號，再把你的書包丟進去，
3.你玩完回來拿書包，把身份證號給管理員，管理員去算柜門號，然后打開柜門把書包給你，
時間復雜度只需要O(1),因為直接打開了目標柜門，
4.理想與現實
理想
現實
事實上這個柜子不是給你個人服務的，而是給一大群人服務的，而且會有一些人剛好用Hash演算法算出來的柜號子和你相同.....，這就出現了沖突，總不能把你的書包扔出去吧，也不能不讓人家放吧......該怎么辦呢？
5.如何解決沖突？（Hash沖突的解決）
事實上關于解決Hash沖突的方法有很多，比如看看隔壁柜子是不是空的、看看隔壁第N個柜子是不是空的、一直翻柜子直到翻到空柜子等等，但目前來說，運用最多的還是鏈地址法（書包鏈）解決沖突，因為它可以最有效的利用陣列（柜子）空間，并且可以將陣列的查詢優勢和鏈表的增刪改優勢結合起來，
也就是說，現在的儲物柜，不再放書包啦，里面放一個卡片，卡片上記錄了第一個書包的位置，而書包呢，彼此之間用繩子連起來，那么不管堆在那里，通過繩子總不會丟，OK，找到A書包，那么這一條繩上的螞蚱，都是1號柜子的，
我：管理員給我書包，我的身份證號是123456，
管理員：好，我先Hash一下，哦哦，你的柜子號是8號，（打開8號柜子）我看看鏈頭書包在哪，原來在第一個窗戶下面，（順著繩子一個一個看），123444不是，123455也不是，123456是，來給你書包，
不考慮書包拿出來的問題，這樣就找到你存的書包了，
不過拿出來也沒啥，先抓住你書包后面書包的繩子，然后讓你書包前面書包的繩子幫綁到你后面的書包上就OK了，（洗掉鏈表節點，沒人不會吧）
6.回頭看一下放書包的流程（HashMap插入流程）
12:00 管理員把你的書包放到8號柜子里
12:30 管理員把張三的書包放到9號柜子里
（java 1.7版本）
13:00 管理員發現李四的書包也應該放到8號，于是他把李四的書包扔到了廁所門口，把你的書包用繩子綁到了李四書包后面，把8號柜子里板子上的字寫成廁所門口，
......
15:30 王五的書包也要放到8號，管理員先把之前李四的書包綁到王五的書包后面，然后把王五的 書包放到了廁所門口窗臺上，把8號柜子里板子上的字改成廁所門口窗戶上，
（java 1.8版本）
13:00 管理員發現李四的書包也應該放到8號，于是他把李四的書包扔到了廁所門口，把你的書包掛到廁所墻上，李四書包綁在你書包后面，把8號柜子里板子上的字寫成廁所墻上，
......
15:30 王五的書包也要放到8號，管理員先把王五的書包綁到李四的書包后面，然后把王五的 書包放到了廁所門口窗臺上，
.....
16:00 你來拿書包
7.柜子的擴容以及多管理員下的問題（HashMap擴容和多執行緒問題）
OK，討論回柜子（HashMap）
（1）HashMap是一種散串列，采用（陣列 + 鏈表 + 紅黑樹）的存盤結構；
（2）HashMap的默認初始容量為16（1<<4），默認裝載因子為0.75f，容量總是2的n次方；
（3）HashMap擴容時每次容量變為原來的兩倍；
（4）當桶的數量小于64時不會進行樹化，只會擴容；
（5）當桶的數量大于64且單個桶中元素的數量大于8時，進行樹化；
（6）當單個桶中元素數量小于6時，進行反樹化；
（7）HashMap是非執行緒安全的容器；
（8）HashMap查找添加元素的時間復雜度都為O(1)；
java 1.7版本的柜子如何擴容的？
1.無要求（無引數），一開始是空柜子，16格子，柜子的使用率超過0.75，拿來一個兩倍大的柜子，重新計算hash值，再把之前柜子里的內容都遷移過去，頭插法遷移，所以書包鏈的前后順序會顛倒，
2.有要求（有引數），根據你的要求配置柜子大小，柜子的使用率，第一次使用初始化容量為你的要求最近的2的冪，
擴容條件：當前資料存盤的數量（即size()）大小必須大于等于閾值；當前加入的資料發生了hash沖突，柜子大于等于使用率了，下一個要放到新的空間里了，
java 1.8版本的柜子如何擴容的？
1.無要求（無引數），一開始是空柜子，0格子，使用一次立即變16格，柜子的使用率超過0.75，拿來一個兩倍大的柜子，重新計算hash值，把之前柜子里的內容都遷移過去，尾插法遷移，
2.有要求（有引數），根據你的要求配置柜子大小，柜子的使用率，第一次使用初始化容量為你的要求最近的2的冪，（細小區別是，先把最近的2的冪給閾值，再把閾值給容量，再把閾值等于容量*加載因子）
擴容條件：當前資料存盤的數量（即size()）大小必須大于等于閾值；柜子大于等于使用率了，
多個管理員（多執行緒下的問題）
java 1.7死回圈
甲乙兩個管理員要做擴容
甲管理員先拿來了一個大柜子，然后先標記12345要放到新柜子里，然后再標記下一個是12346，這時候突然他拉肚子，就去廁所了，
乙管理員哪里知道甲已經做這么多了，乙就都給搬好了，因為是頭插法，現在是12346后面是12345，
甲回來了，嘴里念叨著12345，他也不知道乙都搬完了，他就回來把頭指標指向12345，他就查記錄，12345，下一個是12346，OK，再做一步標記，然后開始搬，現在是12346，下一個是12345，好眼熟啊....，于是就把12346頭插到12345前面了，然后再往后...12345頭插到12346前面，
死回圈了....
java 1.8死回圈
這個是陣列轉紅黑樹時出現的問題，先不說了，你知道就好，
資料丟失
甲管理員要把書包放到8號空箱子，他要放還沒放的時候突然拉肚子，回來的時候乙已經把另一個書包也是8號放好了，但是甲不知道，他還以為8號是空箱子，直接把里面的"垃圾"丟掉，把自己的放進去，（理解為覆寫吧）...
8.關于HashCode和Equals
Java里有個原則 相同物件——相同Hash
一旦違背了這個原則，就違背了一個人只能保存一樣物品這個規矩，一個人用身份證號可以占用多個箱子，但是查詢卻只能查詢到最先查到的，而且不允許重復的Set也會出現重復，Set失效，
所以這個原則不能被違背，
分兩種情況討論：
不同物件插入HashMap ——>小概率Hash相同 >equals判等，正常是不等，去鏈后面或去樹后面但如果重寫，使其相等，不同的物件間就會覆寫，物件丟失，
——>大概率Hash不同 放進不同的Hash桶里，
相同物件插入HashMap ——>Hash一定相同，不同就違反原則 >equals判等，正常是相等，覆寫或不變，這時equals重寫了使其兩者不相等 ，一個鏈上就會出現重復的值，Set失效，而且查詢只能拿到最前面的，
所以，重寫Equals一定要重寫HashCode，一定要滿足相同物件——相同Hash原則，而且先判斷HashCode后判斷Equals，否則效率太低，一個是直接判斷數值，一個是可能要對比物件，最主要的是HashCode做的事和Equals不同，他承擔了維護哈希表的任務，
9.掛書包的藝術（HashMap紅黑樹）
我真編不下去了，難不成讓我說管理員吧掛書包用繩子搞了個樹出來？
關于紅黑樹，看這個清晰理解紅黑樹的演變---紅黑的含義_chen_zhang_yu的博客-CSDN博客
1.柜子容量大于64，單個桶中元素的數量大于8時，才會進行樹化，
2.當單個桶中元素數量小于6時，進行反樹化；
寫在最后的話：擁抱孤獨才能使人進步，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/307604.html
標籤：java