java中Hash表與樹(shù)的介紹

這篇文章主要介紹“java中Hash表與樹(shù)的介紹”，在日常操作中，相信很多人在java中Hash表與樹(shù)的介紹問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”java中Hash表與樹(shù)的介紹”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

成都創(chuàng)新互聯(lián)專業(yè)IDC數(shù)據(jù)服務(wù)器托管提供商，專業(yè)提供成都服務(wù)器托管，服務(wù)器租用，成都電信服務(wù)器托管，成都電信服務(wù)器托管，成都多線服務(wù)器托管等服務(wù)器托管服務(wù)。

jdk1.7中HashMap是由Hash表(即數(shù)組加鏈表)這種結(jié)構(gòu)組成，而在jdk1.8后升級(jí)成了Hash表+紅黑樹(shù)用來(lái)提升數(shù)據(jù)的查詢效率。下面將介紹hash表與紅黑樹(shù)。

Hash表

講解hash表中我們先介紹線性檢索與二分搜索：

線性檢索

把所有數(shù)據(jù)遍歷，找到你所需要的數(shù)據(jù)。其對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組、鏈表等線性結(jié)構(gòu)，這種方式對(duì)于大數(shù)據(jù)而言效率極低，其時(shí)間復(fù)雜度為O(n)。比如ArrayList中的indexOf方法：

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

二分搜索

二分搜索算是對(duì)線性搜索的一個(gè)改進(jìn)，比如說(shuō)對(duì)于【1，2，3，4，5，6，7，8】，我要搜索一個(gè)數(shù)（假設(shè)是2），我先將這個(gè)數(shù)與4（這個(gè)數(shù)一般選中位數(shù)比較好）比較，小于4則在4的左邊【1，2，3】中查找，再與2比較，相等，就成功找到了，這種檢索方式好處在于可以省去很多不必要的檢索，每次只用查找集合中一半的元素。其時(shí)間復(fù)雜度為O(logn)。但其也有限制，他的數(shù)排列本身就需要是有序的。

Hash表

好了，重點(diǎn)來(lái)了，Hash表閃亮登場(chǎng)，這是一種時(shí)間復(fù)雜度為O(1)的檢索，就是說(shuō)不管你數(shù)據(jù)有多少只需要查一次就可以找到目標(biāo)數(shù)據(jù)。

Hash表的本質(zhì)在于可以通過(guò)value本身的特征定位到查找集合的元素下標(biāo)，從而快速查找。一般的Hash函數(shù)為：要存入的數(shù) mod（求余） Hash數(shù)組長(zhǎng)度。

看了上面的講解，機(jī)智的你們肯定已經(jīng)發(fā)現(xiàn)了一個(gè)問(wèn)題，通過(guò)求余數(shù)得到的地址可能是一樣的。這種我們稱為Hash沖突，如果數(shù)據(jù)量比較大而Hash桶比較小，這種沖突就很嚴(yán)重。我們采取如下方式解決沖突問(wèn)題。

我們可以看到12和0的位置沖突了，然后我們把該數(shù)組的每一個(gè)元素變成了一個(gè)鏈表頭，沖突的元素放在了鏈表中，這樣在找到對(duì)應(yīng)的鏈表頭之后會(huì)順著鏈表找下去，至于為什么采用鏈表，是為了節(jié)省空間，鏈表在內(nèi)存中并不是連續(xù)存儲(chǔ)，所以我們可以更充分地使用內(nèi)存。

Hash表實(shí)現(xiàn)的HashMap見(jiàn)源碼分析之HashMap (JDK7)

樹(shù)

在JDK1.7中HashMap就采用了Hash表來(lái)存儲(chǔ)數(shù)據(jù)，根據(jù)key計(jì)算出hashcode然后再與Hash數(shù)組長(zhǎng)度求余得到Hash桶的位置。

如果很多的key產(chǎn)生了Hash沖突，那么每個(gè)桶里面的數(shù)據(jù)量比較大導(dǎo)致鏈表非常長(zhǎng)，這樣Hash表的優(yōu)勢(shì)就不復(fù)存在了，反而傾向于線性檢索。

在jdk1.8版本后，java對(duì)HashMap做了改進(jìn)，在鏈表長(zhǎng)度大于8的時(shí)候，將后面的數(shù)據(jù)存在紅黑樹(shù)中，以加快檢索速度。

在將紅黑樹(shù)之前我們先講一講常見(jiàn)的樹(shù)：

二叉樹(shù)

二叉樹(shù)就是每個(gè)父節(jié)點(diǎn)下面有零個(gè)一個(gè)或兩個(gè)子節(jié)點(diǎn)，在向二叉樹(shù)中存放數(shù)據(jù)的時(shí)候?qū)⒈雀腹?jié)點(diǎn)大的數(shù)放在右節(jié)點(diǎn)，將比父節(jié)點(diǎn)小的數(shù)放在左節(jié)點(diǎn)，這樣之后我們?cè)诓檎夷硞€(gè)數(shù)的時(shí)候只需要將其與父節(jié)點(diǎn)比較，大則進(jìn)入右邊并遞歸調(diào)用，小則進(jìn)入左邊遞歸。 缺點(diǎn)：假如數(shù)據(jù)本身就是有序的，比如【1，2，3，4，5，6，7】，這樣就會(huì)導(dǎo)致樹(shù)的不平衡，二叉樹(shù)就會(huì)退化成為鏈表。所以我們推出了avl樹(shù)。

平衡二叉樹(shù)(AVL樹(shù))二三樹(shù)紅黑樹(shù)

到此，關(guān)于“java中Hash表與樹(shù)的介紹”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！

當(dāng)前題目：java中Hash表與樹(shù)的介紹
當(dāng)前網(wǎng)址：http://m.kartarina.com/article38/ppphsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開(kāi)發(fā)、網(wǎng)站營(yíng)銷、做網(wǎng)站、面包屑導(dǎo)航、品牌網(wǎng)站設(shè)計(jì)、網(wǎng)頁(yè)設(shè)計(jì)公司

廣告

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