HashMap和TreeMap的內(nèi)部結(jié)構(gòu)是什么

HashMap和TreeMap的內(nèi)部結(jié)構(gòu)是什么，相信很多沒有經(jīng)驗(yàn)的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個(gè)問題。

成都創(chuàng)新互聯(lián)從2013年開始，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢想脫穎而出為使命，1280元白山做網(wǎng)站,已為上家服務(wù),為白山各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:028-86922220

一、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í)，則要對該哈希表進(jìn)行rehash 操作（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)），從而哈希表將具有大約兩倍的桶數(shù)。

按照key關(guān)鍵字的哈希值和buckets數(shù)組的長度取模查找桶的位置，如果key的哈希值相同，Hash沖突（也就是指向了同一個(gè)桶）則每次新添加的作為頭節(jié)點(diǎn)，而最先添加的在表尾。

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

從上圖我們可以發(fā)現(xiàn)哈希表是由數(shù)組+鏈表組成的，一個(gè)長度為16的數(shù)組中，每個(gè)元素存儲(chǔ)的是一個(gè)鏈表的頭結(jié)點(diǎn)。那么這些元素是按照什么樣的規(guī)則存儲(chǔ)到數(shù)組中呢。一般情況是通過hash(key)%len獲得，也就是元素的key的哈希值對數(shù)組長度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存儲(chǔ)在數(shù)組下標(biāo)為12的位置。

HashMap簡單總結(jié)：

1、HashMap 是鏈?zhǔn)綌?shù)組（存儲(chǔ)鏈表的數(shù)組）實(shí)現(xiàn)查詢速度可以，而且能快速的獲取key對應(yīng)的value；

2、查詢速度的影響因素有 容量和負(fù)載因子，容量大負(fù)載因子小查詢速度快但浪費(fèi)空間，反之則相反；

3、數(shù)組的index值是（key 關(guān)鍵字， hashcode為key的哈希值， len 數(shù)組的大?。篽ashcode%len的值來確定，如果容量大負(fù)載因子小則index相同（index相同也就是指向了同一個(gè)桶）的概率小，鏈表長度小則查詢速度快，反之index相同的概率大鏈表比較長查詢速度慢。

4、對于HashMap以及其子類來說，他們是采用hash算法來決定集合中元素的存儲(chǔ)位置，當(dāng)初始化HashMap的時(shí)候系統(tǒng)會(huì)創(chuàng)建一個(gè)長度為capacity的Entry數(shù)組，這個(gè)數(shù)組里可以存儲(chǔ)元素的位置稱為桶（bucket）,每一個(gè)桶都有其指定索引，系統(tǒng)可以根據(jù)索引快速訪問該桶中存儲(chǔ)的元素。

5、無論何時(shí)HashMap 中的每個(gè)桶都只存儲(chǔ)一個(gè)元素（Entry 對象）。由于Entry對象可以包含一個(gè)引用變量用于指向下一個(gè)Entry，因此可能出現(xiàn)HashMap 的桶（bucket）中只有一個(gè)Entry,但這個(gè)Entry指向另一個(gè)Entry 這樣就形成了一個(gè)Entry 鏈。

6、通過上面的源碼發(fā)現(xiàn)HashMap在底層將key_value對當(dāng)成一個(gè)整體進(jìn)行處理（Entry 對象）這個(gè)整體就是一個(gè)Entry對象，當(dāng)系統(tǒng)決定存儲(chǔ)HashMap中的key_value對時(shí)，完全沒有考慮Entry中的value，而僅僅是根據(jù)key的hash值來決定每個(gè)Entry的存儲(chǔ)位置。

JDK1.8中使用一個(gè)Node數(shù)組來存儲(chǔ)數(shù)據(jù)，但這個(gè)Node可能是鏈表結(jié)構(gòu)，也可能是紅黑樹結(jié)構(gòu)如果插入的key的hashcode相同，那么這些key也會(huì)被定位到Node數(shù)組的同一個(gè)格子里。

如果同一個(gè)格子里的key不超過8個(gè)，使用鏈表結(jié)構(gòu)存儲(chǔ)。如果超過了8個(gè)，那么會(huì)調(diào)用treeifyBin函數(shù)，將鏈表轉(zhuǎn)換為紅黑樹。那么即使hashcode完全相同，由于紅黑樹的特點(diǎn)，查找某個(gè)特定元素，也只需要O(log n)的開銷

也就是說put/get的操作的時(shí)間復(fù)雜度最差只有O(log n)。

需要注意：key的對象，必須正確的實(shí)現(xiàn)了Compare接口

二、TreeMap

紅黑樹是一種近似平衡的二叉查找樹，它能夠確保任何一個(gè)節(jié)點(diǎn)的左右子樹的高度差不會(huì)超過二者中較低那個(gè)的一陪。具體來說，紅黑樹是滿足如下條件的二叉查找樹（binary search tree）：

1. 每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。

2. 根節(jié)點(diǎn)必須是黑色

3. 紅色節(jié)點(diǎn)不能連續(xù)（也即是，紅色節(jié)點(diǎn)的孩子和父親都不能是紅色）。

4. 對于每個(gè)節(jié)點(diǎn)，從該點(diǎn)至null（樹尾端）的任何路徑，都含有相同個(gè)數(shù)的黑色節(jié)點(diǎn)。

在樹的結(jié)構(gòu)發(fā)生改變時(shí)（插入或者刪除操作），往往會(huì)破壞上述條件3或條件4，需要通過調(diào)整使得查找樹重新滿足紅黑樹的條件。

2、TreeMap的底層使用了紅黑樹來實(shí)現(xiàn)，像TreeMap對象中放入一個(gè)key-value 鍵值對時(shí)，就會(huì)生成一個(gè)Entry對象，這個(gè)對象就是紅黑樹的一個(gè)節(jié)點(diǎn)，其實(shí)這個(gè)和HashMap是一樣的，一個(gè)Entry對象作為一個(gè)節(jié)點(diǎn)，只是這些節(jié)點(diǎn)存放的方式不同。

3、存放每一個(gè)Entry對象時(shí)都會(huì)按照key鍵的大小按照二叉樹的規(guī)范進(jìn)行存放，所以TreeMap中的數(shù)據(jù)是按照key從小到大排序的。

   程序添加新節(jié)點(diǎn)時(shí)，總是從樹的根節(jié)點(diǎn)開始比較，即將根節(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)。

看完上述內(nèi)容，你們掌握HashMap和TreeMap的內(nèi)部結(jié)構(gòu)是什么的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

文章標(biāo)題：HashMap和TreeMap的內(nèi)部結(jié)構(gòu)是什么
本文來源：http://bm7419.com/article46/jdgieg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、標(biāo)簽優(yōu)化、微信公眾號、電子商務(wù)、網(wǎng)站建設(shè)、用戶體驗(yàn)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)