java中Hash表與樹的介紹

這篇文章主要介紹“java中Hash表與樹的介紹”，在日常操作中，相信很多人在java中Hash表與樹的介紹問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”java中Hash表與樹的介紹”的疑惑有所幫助！接下來，請跟著小編一起來學(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后升級成了Hash表+紅黑樹用來提升數(shù)據(jù)的查詢效率。下面將介紹hash表與紅黑樹。

Hash表

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

線性檢索

把所有數(shù)據(jù)遍歷，找到你所需要的數(shù)據(jù)。其對應(yīng)的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組、鏈表等線性結(jié)構(gòu)，這種方式對于大數(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;
}

二分搜索

二分搜索算是對線性搜索的一個(gè)改進(jìn)，比如說對于【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)來了，Hash表閃亮登場，這是一種時(shí)間復(fù)雜度為O(1)的檢索，就是說不管你數(shù)據(jù)有多少只需要查一次就可以找到目標(biāo)數(shù)據(jù)。

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

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

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

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

樹

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

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

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

在將紅黑樹之前我們先講一講常見的樹：

二叉樹

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

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

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

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

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

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(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)