java中Hash表與樹的介紹

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

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

Hash表

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

線性檢索

把所有數據遍歷，找到你所需要的數據。其對應的數據結構就是數組、鏈表等線性結構，這種方式對于大數據而言效率極低，其時間復雜度為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】，我要搜索一個數（假設是2），我先將這個數與4（這個數一般選中位數比較好）比較，小于4則在4的左邊【1，2，3】中查找，再與2比較，相等，就成功找到了，這種檢索方式好處在于可以省去很多不必要的檢索，每次只用查找集合中一半的元素。其時間復雜度為O(logn)。但其也有限制，他的數排列本身就需要是有序的。

Hash表

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

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

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

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

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

樹

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

如果很多的key產生了Hash沖突，那么每個桶里面的數據量比較大導致鏈表非常長，這樣Hash表的優勢就不復存在了，反而傾向于線性檢索。

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

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

二叉樹

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

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

到此，關于“java中Hash表與樹的介紹”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！