一、HashMap
1、基于哈希表的 Map 接口的實(shí)現(xiàn)。
此實(shí)現(xiàn)提供所有可選的映射操作,并允許使用 null 值和 null 鍵。(除了非同步和允許使用 null 之外,HashMap 類與 Hashtable 大致相同。)此類不保證映射的順序,特別是它不保證該順序恒久不變。
2、HashMap 的實(shí)例有兩個(gè)參數(shù)影響其性能:初始容量 和 加載因子。
容量是哈希表中桶的數(shù)量,初始容量只是哈希表在創(chuàng)建時(shí)的容量。
加載因子是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時(shí),則要對(duì)該哈希表進(jìn)行rehash 操作(即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)),從而哈希表將具有大約兩倍的桶數(shù)。
按照key關(guān)鍵字的哈希值和buckets數(shù)組的長(zhǎng)度取模查找桶的位置,如果key的哈希值相同,Hash沖突(也就是指向了同一個(gè)桶)則每次新添加的作為頭節(jié)點(diǎn),而最先添加的在表尾。

HashMap中的桶的個(gè)數(shù)就是下圖中的0- n的數(shù)組的長(zhǎng)度,存儲(chǔ)第一個(gè)entry的位置叫桶(bucket)而桶中只能存一個(gè)值也就是鏈表的頭節(jié)點(diǎn),鏈表的每個(gè)節(jié)點(diǎn)就是添加的一個(gè)值(HashMap內(nèi)部類Entry的實(shí)例Entry有哪些屬性之后在詳說(shuō))。
也可以這樣理解,一個(gè)entry 類型的存儲(chǔ)鏈表的數(shù)組。數(shù)組的索引位置就是一個(gè)個(gè)桶的索引地址。

從上圖我們可以發(fā)現(xiàn)哈希表是由數(shù)組+鏈表組成的,一個(gè)長(zhǎng)度為16的數(shù)組中,每個(gè)元素存儲(chǔ)的是一個(gè)鏈表的頭結(jié)點(diǎn)。那么這些元素是按照什么樣的規(guī)則存儲(chǔ)到數(shù)組中呢。
一般情況是通過(guò)hash(key)%len獲得,也就是元素的key的哈希值對(duì)數(shù)組長(zhǎng)度取模得到。比如上述哈希表中,12%16=12、28%16=12、108%16=12、140%16=12。所以12、28、108以及140都存儲(chǔ)在數(shù)組下標(biāo)為12的位置。
HashMap簡(jiǎn)單總結(jié):
1、HashMap 是鏈?zhǔn)綌?shù)組(存儲(chǔ)鏈表的數(shù)組)實(shí)現(xiàn)查詢速度可以,而且能快速的獲取key對(duì)應(yīng)的value;
2、查詢速度的影響因素有 容量和負(fù)載因子,容量大負(fù)載因子小查詢速度快但浪費(fèi)空間,反之則相反;
3、數(shù)組的index值是(key 關(guān)鍵字, hashcode為key的哈希值, len 數(shù)組的大小):hashcode%len的值來(lái)確定,如果容量大負(fù)載因子小則index相同(index相同也就是指向了同一個(gè)桶)的概率小,鏈表長(zhǎng)度小則查詢速度快,反之index相同的概率大鏈表比較長(zhǎng)查詢速度慢。
4、對(duì)于HashMap以及其子類來(lái)說(shuō),他們是采用hash算法來(lái)決定集合中元素的存儲(chǔ)位置,當(dāng)初始化HashMap的時(shí)候系統(tǒng)會(huì)創(chuàng)建一個(gè)長(zhǎng)度為capacity的Entry數(shù)組,這個(gè)數(shù)組里可以存儲(chǔ)元素的位置稱為桶(bucket),每一個(gè)桶都有其指定索引,系統(tǒng)可以根據(jù)索引快速訪問(wèn)該桶中存儲(chǔ)的元素。
5、無(wú)論何時(shí)HashMap 中的每個(gè)桶都只存儲(chǔ)一個(gè)元素(Entry 對(duì)象)。由于Entry對(duì)象可以包含一個(gè)引用變量用于指向下一個(gè)Entry,因此可能出現(xiàn)HashMap 的桶(bucket)中只有一個(gè)Entry,但這個(gè)Entry指向另一個(gè)Entry 這樣就形成了一個(gè)Entry 鏈。
6、通過(guò)上面的源碼發(fā)現(xiàn)HashMap在底層將key_value對(duì)當(dāng)成一個(gè)整體進(jìn)行處理(Entry 對(duì)象)這個(gè)整體就是一個(gè)Entry對(duì)象,當(dāng)系統(tǒng)決定存儲(chǔ)HashMap中的key_value對(duì)時(shí),完全沒(méi)有考慮Entry中的value,而僅僅是根據(jù)key的hash值來(lái)決定每個(gè)Entry的存儲(chǔ)位置。
注意點(diǎn)
JDK1.8中使用一個(gè)Node數(shù)組來(lái)存儲(chǔ)數(shù)據(jù),但這個(gè)Node可能是鏈表結(jié)構(gòu),也可能是紅黑樹(shù)結(jié)構(gòu)如果插入的key的hashcode相同,那么這些key也會(huì)被定位到Node數(shù)組的同一個(gè)格子里。
如果同一個(gè)格子里的key不超過(guò)8個(gè),使用鏈表結(jié)構(gòu)存儲(chǔ)。如果超過(guò)了8個(gè),那么會(huì)調(diào)用treeifyBin函數(shù),將鏈表轉(zhuǎn)換為紅黑樹(shù)。那么即使hashcode完全相同,由于紅黑樹(shù)的特點(diǎn),查找某個(gè)特定元素,也只需要O(log n)的開(kāi)銷。
也就是說(shuō)put/get的操作的時(shí)間復(fù)雜度最差只有O(log n)。
需要注意:key的對(duì)象,必須正確的實(shí)現(xiàn)了Compare接口
二、TreeMap
1、紅黑樹(shù)是一種近似平衡的二叉查找樹(shù),它能夠確保任何一個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度差不會(huì)超過(guò)二者中較低那個(gè)的一倍。具體來(lái)說(shuō),紅黑樹(shù)是滿足如下條件的二叉查找樹(shù)(binary search tree):
- 每個(gè)節(jié)點(diǎn)要么是紅色,要么是黑色。
- 根節(jié)點(diǎn)必須是黑色
- 紅色節(jié)點(diǎn)不能連續(xù)(也即是,紅色節(jié)點(diǎn)的孩子和父親都不能是紅色)。
- 對(duì)于每個(gè)節(jié)點(diǎn),從該點(diǎn)至null(樹(shù)尾端)的任何路徑,都含有相同個(gè)數(shù)的黑色節(jié)點(diǎn)。
在樹(shù)的結(jié)構(gòu)發(fā)生改變時(shí)(插入或者刪除操作),往往會(huì)破壞上述條件3或條件4,需要通過(guò)調(diào)整使得查找樹(shù)重新滿足紅黑樹(shù)的條件。

2、TreeMap的底層使用了紅黑樹(shù)來(lái)實(shí)現(xiàn),像TreeMap對(duì)象中放入一個(gè)key-value 鍵值對(duì)時(shí),就會(huì)生成一個(gè)Entry對(duì)象,這個(gè)對(duì)象就是紅黑樹(shù)的一個(gè)節(jié)點(diǎn),其實(shí)這個(gè)和HashMap是一樣的,一個(gè)Entry對(duì)象作為一個(gè)節(jié)點(diǎn),只是這些節(jié)點(diǎn)存放的方式不同。
3、存放每一個(gè)Entry對(duì)象時(shí)都會(huì)按照key鍵的大小按照二叉樹(shù)的規(guī)范進(jìn)行存放,所以TreeMap中的數(shù)據(jù)是按照key從小到大排序的。
TreeMap總結(jié):
程序添加新節(jié)點(diǎn)時(shí),總是從樹(shù)的根節(jié)點(diǎn)開(kāi)始比較,即將根節(jié)點(diǎn)當(dāng)成當(dāng)前節(jié)點(diǎn)。如果新增節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)并且當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)存在,則以右節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn),如果新增節(jié)點(diǎn)小于當(dāng)前節(jié)點(diǎn)并且當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)存在,則以左子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn);
如果新增節(jié)點(diǎn)等于當(dāng)前節(jié)點(diǎn),則用新增節(jié)點(diǎn)覆蓋當(dāng)前節(jié)點(diǎn),并結(jié)束循環(huán) 直到某個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)不存在,將新節(jié)點(diǎn)添加為該節(jié)點(diǎn)的子節(jié)點(diǎn)。如果新節(jié)點(diǎn)比該節(jié)點(diǎn)大,則添加其為右子節(jié)點(diǎn)。如果新節(jié)點(diǎn)比該節(jié)點(diǎn)小,則添加其為左子節(jié)點(diǎn)。
最后
歡迎大家一起交流,喜歡文章記得關(guān)注我點(diǎn)贊轉(zhuǎn)發(fā)喲,感謝支持!