大香蕉超碰,婷婷激情四射久久

1. 概述

HashMap 底層的數(shù)據(jù)結(jié)構(gòu)主要是:數(shù)組 + 鏈表 + 紅黑樹。其中當(dāng)鏈表的長度大于等于 8 時(shí)，
鏈表會(huì)轉(zhuǎn)化成紅黑樹，當(dāng)紅黑樹的大小小于等于 6 時(shí)，紅黑樹會(huì)轉(zhuǎn)化成鏈表

HashMap是數(shù)組結(jié)構(gòu)，數(shù)組的元素可能是單個(gè) Node，也可能是個(gè)鏈表，也可能是個(gè)紅黑樹，
比如數(shù)組下標(biāo)索引為 2 的位置就是一個(gè)鏈表，下標(biāo)索引為 9 的位置對(duì)應(yīng)的就是紅黑樹，具體細(xì)節(jié)我們下文再說

1.1 類注釋

從HashMap的類注釋中，我們可以得到如下信息：

允許null值，不同于HashTable,是線程不安全的；
load factor(影響因子）默認(rèn)值是0.75,是均衡了時(shí)間和空間損耗算出來的值，較高的值
會(huì)減少空間開銷（擴(kuò)容減少，數(shù)組大小增長速度變慢）,但增加了查找成本（hash沖突增
加，鏈表長度變長）,不擴(kuò)容的條件：數(shù)組容量>需要的數(shù)組大小/load factor
如果有很多數(shù)據(jù)需要儲(chǔ)存到HashMap中，建議HashMap的容量一開始就設(shè)置成足夠的大
小，這樣可以防止在其過程中不斷的擴(kuò)容，影響性能；
HashMap是非線程安全的，我們可以自己在外部加鎖，或者通過
Collections#synchronizedMap來實(shí)現(xiàn)線程安全，Collections#synchronizedMap的實(shí)現(xiàn)
是在每個(gè)方法上加上了synchronized鎖；
在迭代過程中，如果HashMap的結(jié)構(gòu)被修改，會(huì)快速失敗。

1.2 常見屬性

//初始容量為16
static final int DEFAULT_INITIAL_CAPACITY=1<<4;
//最大容量
static final int MAXIMUM_CAPACITY =1<<30;
//負(fù)載因子默認(rèn)值
static final float DEFAULT_LOAD_FACTOR=0.75f;
/桶上的鏈表長度大于等于8時(shí)，鏈表轉(zhuǎn)化成紅黑樹
static final int TREEIFY_THRESHOLD=8
/桶上的紅黑樹大小小于等于6時(shí)，紅黑樹轉(zhuǎn)化成鏈表
static final int UNTREEIFY_THRESHOLD=6;
//HashMap 樹最小容量,最少4倍TREEIFY_THRESHOLD，防止經(jīng)常擴(kuò)容縮容的開銷
static final int MIN_TREEIFY_CAPACITY = 64;

2. 新增

新增 key，value 大概的步驟如下:

空數(shù)組有無初始化，沒有的話初始化;
如果通過 key 的 hash 能夠直接找到值，跳轉(zhuǎn)到 6，否則到 3;
如果 hash 沖突，兩種解決方案:鏈表 or 紅黑樹;
如果是鏈表，遞歸循環(huán)，把新元素追加到隊(duì)尾;
如果是紅黑樹，調(diào)用紅黑樹新增的方法;
通過 2、4、5 將新元素追加成功，再根據(jù) onlyIfAbsent 判斷是否需要覆蓋;
判斷是否需要擴(kuò)容，需要擴(kuò)容進(jìn)行擴(kuò)容，結(jié)束。

//入?yún)ash:通過hash算法計(jì)算出來的值。
//入?yún)nlylfAbsent:false表示即使key已經(jīng)存在了，仍然會(huì)用新值覆蓋原來的值，默認(rèn)為false
final V putVal(int hash, K key, V value, boolean onlylfAbsent,boolean evict){
    //n表示數(shù)組的長度，i為數(shù)組索引下標(biāo)，p為i下標(biāo)位置的Node值
    Node<K,V>[]tab;Node<K,V>p;int n,i;
    //如果數(shù)組為空，使用resize方法初始化
    if((tab=table)==nullll(n=tab.length)==0)
        n=(tab=resize().length;
    //如果當(dāng)前索引位置是空的，直接生成新的節(jié)點(diǎn)在當(dāng)前索引位置上
    if((p=tab[i=(n-1)&hash])==null)
        tab[i]=newNode(hash,key,value,null);
    //如果當(dāng)前索引位置有值的處理方法，即我們常說的如何解決hash沖突
    }else {
        //e當(dāng)前節(jié)點(diǎn)的臨時(shí)變量
        Node<K,V>e;Kk;
        //如果key的hash和值都相等，直接把當(dāng)前下標(biāo)位置的Node值賦值給臨時(shí)變量
        if(p.hash==hash&&
        ((k=p.key)==keyll(key!=null&&key.equals(k))))
            e=p;
        //如果是紅黑樹，使用紅黑樹的方式新增
        else if (p instanceof TreeNode)
            e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);
        //是個(gè)鏈表，把新節(jié)點(diǎn)放到鏈表的尾端
        else{
            for (int binCount = 0; ; ++binCount) {
                //p.next==null表明p是鏈表的尾節(jié)點(diǎn)
                if((e=p.next)==null){
                    //把新節(jié)點(diǎn)放到鏈表的尾部
                    p.next=newNode(hash,key,value,null);
                    //當(dāng)鏈表的長度大于等于8時(shí)，鏈表轉(zhuǎn)紅黑樹
                    if(binCount>=TREEIFY_THRESHOLD-1)
                    treeifyBin(tab,hash);
                    break;
                }
                //鏈表遍歷過程中，發(fā)現(xiàn)有元素和新增的元素相等，結(jié)束循環(huán)
                if(e.hash==hash&&
                ((k=e.key)==keyll(key!=null&key.equals(k))))
                    break;
                //更改循環(huán)的當(dāng)前元素，使p在遍歷過程中，一直往后移動(dòng)。
                p=e;
            }
        }
        //說明新節(jié)點(diǎn)的新增位置已經(jīng)找到了
        if(e!=null){
            V oldValue = e.value
            //當(dāng)onlylfAbsent為false時(shí)，才會(huì)覆蓋值
            if(!onlylfAbsentlloldValue==null)
                e.value = value ;
            afterNodeAccess(e);
            //返回老值
            return oldValue
        }
    }
    //記錄HashMap的數(shù)據(jù)結(jié)構(gòu)發(fā)生了變化
    ++modCount;
    //如果HashMap的實(shí)際大小大于擴(kuò)容的門檻，開始擴(kuò)容
    if(++size>threshold)
        resize();
    afterNodelnsertion(evict);
    return null;
}

新增的流程上面應(yīng)該已經(jīng)表示很清楚了，接下來我們來看看鏈表和紅黑樹新增的細(xì)節(jié)：

2.1 鏈表的新增

鏈表的新增比較簡單，就是把當(dāng)前節(jié)點(diǎn)追加到鏈表的尾部，和LinkedList的追加實(shí)現(xiàn)一樣的。

當(dāng)鏈表長度大于等于8時(shí)，此時(shí)的鏈表就會(huì)轉(zhuǎn)化成紅黑樹，轉(zhuǎn)化的方法是：treeifyBin,此方法
有一個(gè)判斷，當(dāng)鏈表長度大于等于8,并且整個(gè)數(shù)組大小大于64時(shí)，才會(huì)轉(zhuǎn)成紅黑樹，當(dāng)數(shù)組
大小小于64時(shí)，只會(huì)觸發(fā)擴(kuò)容，不會(huì)轉(zhuǎn)化成紅黑樹，轉(zhuǎn)化成紅黑樹的過程也比較簡單

可能面試的時(shí)候，有人問你為什么是8,這個(gè)答案在源碼中注釋有說，中文翻譯過來大概的意思是：

鏈表查詢的時(shí)間復(fù)雜度是O(n),紅黑樹的查詢復(fù)雜度是O(log(n))。在鏈表數(shù)據(jù)不多的時(shí)候，
使用鏈表進(jìn)行遍歷也比較快，只有當(dāng)鏈表數(shù)據(jù)比較多的時(shí)候，才會(huì)轉(zhuǎn)化成紅黑樹，但紅黑樹需要
的占用空間是鏈表的2倍，考慮到轉(zhuǎn)化時(shí)間和空間損耗，所以我們需要定義出轉(zhuǎn)化的邊界值。

在考慮設(shè)計(jì)8這個(gè)值的時(shí)候，我們參考了泊松分布概率函數(shù)，由泊松分布中得出結(jié)論，鏈表各
個(gè)長度的命中概率為：

0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006

意思是，當(dāng)鏈表的長度是8的時(shí)候，出現(xiàn)的概率是0.00000006,不到千萬分之一，所以說正常
情況下，鏈表的長度不可能到達(dá)8,而一旦到達(dá)8時(shí)，肯定是hash算法出了問題，所以在這
種情況下，為了讓HashMap仍然有較高的查詢性能，所以讓鏈表轉(zhuǎn)化成紅黑樹，我們正常寫
代碼，使用HashMap時(shí)，幾乎不會(huì)碰到鏈表轉(zhuǎn)化成紅黑樹的情況，畢竟概念只有千萬分之一

2.2 紅黑樹新增節(jié)點(diǎn)過程

首先判斷新增的節(jié)點(diǎn)在紅黑樹上是不是已經(jīng)存在，判斷手段有如下兩種：
1.1. 如果節(jié)點(diǎn)沒有實(shí)現(xiàn)Comparable接口，使用equals進(jìn)行判斷；
1.2. 如果節(jié)點(diǎn)自己實(shí)現(xiàn)了Comparable接口，使用compareTo進(jìn)行判斷。
新增的節(jié)點(diǎn)如果已經(jīng)在紅黑樹上，直接返回；不在的話，判斷新增節(jié)點(diǎn)是在當(dāng)前節(jié)點(diǎn)的左邊
還是右邊，左邊值小，右邊值大；
自旋遞歸1和2步，直到當(dāng)前節(jié)點(diǎn)的左邊或者右邊的節(jié)點(diǎn)為空時(shí)，停止自旋，當(dāng)前節(jié)點(diǎn)即為
我們新增節(jié)點(diǎn)的父節(jié)點(diǎn)；
把新增節(jié)點(diǎn)放到當(dāng)前節(jié)點(diǎn)的左邊或右邊為空的地方，并于當(dāng)前節(jié)點(diǎn)建立父子節(jié)點(diǎn)關(guān)系；
進(jìn)行著色和旋轉(zhuǎn)，結(jié)束。

//入?yún):key的hash值
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V> tab,int h,K k,V v){
    Class<?>kc=null;
    boolean searched = false
    //找到根節(jié)點(diǎn)
    TreeNode<K,V>root=(parent!=null)?root():this;
    //自旋
    for(TreeNode<K,V>p=root;;){
        int dir, ph; K pk;
        //p hash值大于h,說明p在h的右邊
        if((ph=p.hash)&gt;h)
            dir=-1;
        //p hash值小于h,說明p在h的左邊
        else if (ph < h)
            dir = 1;
        //要放進(jìn)去key在當(dāng)前樹中已經(jīng)存在了（equals來判斷）
        else if ((pk=p.key)==kll(k!=null&&kequals(pk))
            return p;
        //自己實(shí)現(xiàn)的Comparable的話，不能用hashcode比較了，需要用compareTo
        else if ((kc== null &&
        //得到key的Class類型，如果key沒有實(shí)現(xiàn)Comparable就是null
                        (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
            if(!searched){
                TreeNode<K,V> q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                return q;
            }
            dir = tieBreakOrder(k, pk);
        }
        TreeNode<K,V> xp = p;
        //找到和當(dāng)前hashcode值相近的節(jié)點(diǎn)（當(dāng)前節(jié)點(diǎn)的左右子節(jié)點(diǎn)其中一個(gè)為空即可）
        if((p=(dir<=0)?p.left:p.right)==null){
            Node<K,V>xpn=xp.next
            //生成新的節(jié)點(diǎn)
            TreeNode<K,V>x=map.newTreeNode(h,k,v,xpn);
            //把新節(jié)點(diǎn)放在當(dāng)前子節(jié)點(diǎn)為空的位置上
            if(dir<=0)
                xp.left=X;
            else
                xp.right
            //當(dāng)前節(jié)點(diǎn)和新節(jié)點(diǎn)建立父子，前后關(guān)系
            xp.next = X;
            x.parent=x.prev=xp;
            if(xpn!=null)
                ((TreeNode<K,V>)xpn).prev=X;
            //balancelnsertion對(duì)紅黑樹進(jìn)行著色或旋轉(zhuǎn)，以達(dá)到更多的查找效率，著色或旋轉(zhuǎn)的幾種場
            //著色：新節(jié)點(diǎn)總是為紅色；如果新節(jié)點(diǎn)的父親是黑色，則不需要重新著色；如果父親是紅色
            //旋轉(zhuǎn)：父親是紅色，叔叔是黑色時(shí)，進(jìn)行旋轉(zhuǎn)
            //如果當(dāng)前節(jié)點(diǎn)是父親的右節(jié)點(diǎn)，則進(jìn)行左旋
            //如果當(dāng)前節(jié)點(diǎn)是父親的左節(jié)點(diǎn)，則進(jìn)行右旋
            //moveRootToFront方法是把算出來的root放到根節(jié)點(diǎn)上
            moveRootToFront(tab,balancelnsertion(root,x);
            return null;
        }
    }
}

紅黑樹的新增，要求大家對(duì)紅黑樹的數(shù)據(jù)結(jié)構(gòu)有一定的了解。面試的時(shí)候，一般只會(huì)問到新增節(jié)
點(diǎn)到紅黑樹上大概是什么樣的一個(gè)過程，著色和旋轉(zhuǎn)的細(xì)節(jié)不會(huì)問，因?yàn)楹茈y說清楚，但我們要
清楚著色指的是給紅黑樹的節(jié)點(diǎn)著上紅色或黑色，旋轉(zhuǎn)是為了讓紅黑樹更加平衡，提高查詢的效
率，總的來說都是為了滿足紅黑樹的5個(gè)原則：

節(jié)點(diǎn)是紅色或黑色
根是黑色
所有葉子都是黑色
從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)
從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)

3 查找

HashMap的查找主要分為以下三步：

初始判斷，hash定位到具體的數(shù)組下標(biāo)的元素，判斷第一個(gè)節(jié)點(diǎn)的key是否匹配，匹配則返回值，若不匹配則步驟2
判斷當(dāng)前節(jié)點(diǎn)有無next節(jié)點(diǎn)，有的話判斷是鏈表類型，還是紅黑樹類型。
分別走鏈表和紅黑樹不同類型的查找方法。
鏈表查找的關(guān)鍵代碼是：

 final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //初始判斷
        if ((tab = table) != null && (n = tab.length) > 0 &&
            //hash定位到數(shù)組下標(biāo)元素
            (first = tab[(n - 1) & hash]) != null) {
            //看到第一個(gè)節(jié)點(diǎn)key是否匹配，匹配則返回值
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
             //判斷有無next節(jié)點(diǎn)
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //采用自旋方式從鏈表中查找key,e初始為為鏈表的頭節(jié)點(diǎn)
                do {
                    //如果當(dāng)前節(jié)點(diǎn)hash等于key的hash,并且equals相等，當(dāng)前節(jié)點(diǎn)就是我們要找的節(jié)點(diǎn)
                    //當(dāng)hash沖突時(shí)，同一個(gè)hash值上是一個(gè)鏈表的時(shí)候，我們是通過equals方法來比較key是己
                    if(e.hash==hash&&
                    ((k=e.key)==keyll(key!=null&&key.equals(k))))
                        return e;
                    //否則，把當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)拿出來繼續(xù)尋找
                } while ((e = e.next) != null)
            }
        }
        return null;
    }

紅黑樹查找的代碼很多，我們大概說下思路，實(shí)際步驟比較復(fù)雜，可以去github上面去查看源

從根節(jié)點(diǎn)遞歸查找；
根據(jù)hashcode,比較查找節(jié)點(diǎn)，左邊節(jié)點(diǎn)，右邊節(jié)點(diǎn)之間的大小，根本紅黑樹左小右大的特性進(jìn)行判斷；
判斷查找節(jié)點(diǎn)在第2步有無定位節(jié)點(diǎn)位置，有的話返回，沒有的話重復(fù)2,3兩步；
一直自旋到定位到節(jié)點(diǎn)位置為止如果紅黑樹比較平衡的話，每次查找的次數(shù)就是樹的深度。

總結(jié)

HashMap的內(nèi)容雖然較多，但大多數(shù)api都只是對(duì)數(shù)組+鏈表+紅黑樹這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行封
裝而已，本小節(jié)我們從新增和查找兩個(gè)角度進(jìn)行了源碼的深入分析，分析了是如何對(duì)數(shù)組、鏈表
和紅黑樹進(jìn)行操作的

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

老猿說說-HashMap

老猿說說-HashMap

1. 概述

1.1 類注釋

1.2 常見屬性

2. 新增

2.1 鏈表的新增

2.2 紅黑樹新增節(jié)點(diǎn)過程

3 查找

總結(jié)

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

老猿說說-HashMap

1. 概述

1.1 類注釋

1.2 常見屬性

2. 新增

2.1 鏈表的新增

2.2 紅黑樹新增節(jié)點(diǎn)過程

3 查找

總結(jié)

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av