java中Hash表與樹的介紹

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

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ù)而言效率極低，其時間復(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;
}

二分搜索

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

Hash表

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

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

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

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

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

樹

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

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

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

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

二叉樹

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

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

到此，關(guān)于“java中Hash表與樹的介紹”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>