国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

站在巨人肩膀上看源碼-HashMap(基于jdk1.8)

劉玉平 / 600人閱讀

摘要:而中,采用數(shù)組鏈表紅黑樹實(shí)現(xiàn),當(dāng)鏈表長(zhǎng)度超過閾值時(shí),將鏈表轉(zhuǎn)換為紅黑樹,這樣大大減少了查找時(shí)間。到了,當(dāng)同一個(gè)值的節(jié)點(diǎn)數(shù)不小于時(shí),不再采用單鏈表形式存儲(chǔ),而是采用紅黑樹,如下圖所示。

一. HashMap概述

在JDK1.8之前,HashMap采用數(shù)組+鏈表實(shí)現(xiàn),即使用鏈表處理沖突,同一hash值的節(jié)點(diǎn)都存儲(chǔ)在一個(gè)鏈表里。但是當(dāng)位于一個(gè)桶中的元素較多,即hash值相等的元素較多時(shí),通過key值依次查找的效率較低。而JDK1.8中,HashMap采用數(shù)組+鏈表+紅黑樹實(shí)現(xiàn),當(dāng)鏈表長(zhǎng)度超過閾值(8)時(shí),將鏈表轉(zhuǎn)換為紅黑樹,這樣大大減少了查找時(shí)間。
下圖中代表jdk1.8之前的hashmap結(jié)構(gòu),左邊部分即代表哈希表,也稱為哈希數(shù)組,數(shù)組的每個(gè)元素都是一個(gè)單鏈表的頭節(jié)點(diǎn),鏈表是用來解決沖突的,如果不同的key映射到了數(shù)組的同一位置處,就將其放入單鏈表中。

jdk1.8之前hashmap結(jié)構(gòu)圖

jdk1.8之前的hashmap都采用上圖的結(jié)構(gòu),都是基于一個(gè)數(shù)組和多個(gè)單鏈表,hash值沖突的時(shí)候,就將對(duì)應(yīng)節(jié)點(diǎn)以鏈表的形式存儲(chǔ)。如果在一個(gè)鏈表中查找其中一個(gè)節(jié)點(diǎn)時(shí),將會(huì)花費(fèi)O(n)的查找時(shí)間,會(huì)有很大的性能損失。到了jdk1.8,當(dāng)同一個(gè)hash值的節(jié)點(diǎn)數(shù)不小于8時(shí),不再采用單鏈表形式存儲(chǔ),而是采用紅黑樹,如下圖所示。

jdk1.8HashMap結(jié)構(gòu)圖
說明:上圖很形象的展示了HashMap的數(shù)據(jù)結(jié)構(gòu)(數(shù)組+鏈表+紅黑樹),桶中的結(jié)構(gòu)可能是鏈表,也可能是紅黑樹,紅黑樹的引入是為了提高效率。

二、涉及到的數(shù)據(jù)結(jié)構(gòu):處理hash沖突的鏈表和紅黑樹以及位桶 1、鏈表的實(shí)現(xiàn)

Node是HashMap的一個(gè)內(nèi)部類,實(shí)現(xiàn)了Map.Entry接口,本質(zhì)是就是一個(gè)映射(鍵值對(duì))。上圖中的每個(gè)黑色圓點(diǎn)就是一個(gè)Node對(duì)象。來看具體代碼:

//Node是單向鏈表,它實(shí)現(xiàn)了Map.Entry接口
static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;
    //構(gòu)造函數(shù)Hash值 鍵 值 下一個(gè)節(jié)點(diǎn)
    Node(int hash, K key, V value, Node next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
 
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + = + value; }
 
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
 
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    //判斷兩個(gè)node是否相等,若key和value都相等,返回true。可以與自身比較為true
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry e = (Map.Entry)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}


可以看到,node中包含一個(gè)next變量,這個(gè)就是鏈表的關(guān)鍵點(diǎn),hash結(jié)果相同的元素就是通過這個(gè)next進(jìn)行關(guān)聯(lián)的。

2、紅黑樹
//紅黑樹
static final class TreeNode extends LinkedHashMap.Entry {
    TreeNode parent;  // 父節(jié)點(diǎn)
    TreeNode left; //左子樹
    TreeNode right;//右子樹
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;    //顏色屬性
    TreeNode(int hash, K key, V val, Node next) {
        super(hash, key, val, next);
    }
 
    //返回當(dāng)前節(jié)點(diǎn)的根節(jié)點(diǎn)
    final TreeNode root() {
        for (TreeNode r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
}

紅黑樹比鏈表多了四個(gè)變量,parent父節(jié)點(diǎn)、left左節(jié)點(diǎn)、right右節(jié)點(diǎn)、prev上一個(gè)同級(jí)節(jié)點(diǎn),紅黑樹內(nèi)容較多,不在贅述。

三、HashMap源碼分析

1、類的繼承關(guān)系

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

可以看到HashMap繼承自父類(AbstractMap),實(shí)現(xiàn)了Map、Cloneable、Serializable接口。其中,Map接口定義了一組通用的操作;Cloneable接口則表示可以進(jìn)行拷貝,在HashMap中,實(shí)現(xiàn)的是淺層次拷貝,即對(duì)拷貝對(duì)象的改變會(huì)影響被拷貝的對(duì)象;Serializable接口表示HashMap實(shí)現(xiàn)了序列化,即可以將HashMap對(duì)象保存至本地,之后可以恢復(fù)狀態(tài)。
2、類的屬性

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
    // 序列號(hào)
    private static final long serialVersionUID = 362498820763181265L;    
    // 默認(rèn)的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 默認(rèn)的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)大于這個(gè)值時(shí)會(huì)轉(zhuǎn)成紅黑樹
    static final int TREEIFY_THRESHOLD = 8; 
    // 當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)小于這個(gè)值時(shí)樹轉(zhuǎn)鏈表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹對(duì)應(yīng)的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存儲(chǔ)元素的數(shù)組,總是2的冪次倍
    transient Node[] table; 
    // 存放具體元素的集
    transient Set> entrySet;
    // 存放元素的個(gè)數(shù),注意這個(gè)不等于數(shù)組的長(zhǎng)度。
    transient int size;
    // 每次擴(kuò)容和更改map結(jié)構(gòu)的計(jì)數(shù)器
    transient int modCount;   
    // 臨界值 當(dāng)實(shí)際大小(容量*填充因子)超過臨界值時(shí),會(huì)進(jìn)行擴(kuò)容
    int threshold;
    // 填充因子
    final float loadFactor;
}

理解數(shù)據(jù)的成員后再看幫助很大!
3、類的構(gòu)造函數(shù)
(1)HashMap(int, float)型構(gòu)造函數(shù)

public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不能小于0,否則報(bào)錯(cuò)
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
    // 初始容量不能大于最大值,否則為最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 填充因子不能小于或等于0,不能為非數(shù)字
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    // 初始化填充因子                                        
    this.loadFactor = loadFactor;
    // 初始化threshold大小
    this.threshold = tableSizeFor(initialCapacity);    
}

說明:tableSizeFor(initialCapacity)返回大于initialCapacity的最小的二次冪數(shù)值。

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

說明:>>> 操作符表示無符號(hào)右移,高位取0。

(2)HashMap(int)型構(gòu)造函數(shù)。

public HashMap(int initialCapacity) {
    // 調(diào)用HashMap(int, float)型構(gòu)造函數(shù)
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

(3)HashMap()型構(gòu)造函數(shù)。

public HashMap() {
    // 初始化填充因子
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

(4)HashMap(Map)型構(gòu)造函數(shù)。

public HashMap(Map m) {
    // 初始化填充因子
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // 將m中的所有元素添加至HashMap中
    putMapEntries(m, false);
}

說明:putMapEntries(Map m, boolean evict)函數(shù)將m的所有元素存入本HashMap實(shí)例中。

final void putMapEntries(Map m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 判斷table是否已經(jīng)初始化
        if (table == null) { // pre-size
            // 未初始化,s為m的實(shí)際元素個(gè)數(shù)
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                    (int)ft : MAXIMUM_CAPACITY);
            // 計(jì)算得到的t大于閾值,則初始化閾值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已初始化,并且m元素個(gè)數(shù)大于閾值,進(jìn)行擴(kuò)容處理
        else if (s > threshold)
            resize();
        // 將m中的所有元素添加至HashMap中
        for (Map.Entry e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}
4、hash算法

在JDK 1.8中,hash方法如下

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

(1)首先獲取對(duì)象的hashCode()值,然后將hashCode值右移16位,然后將右移后的值與原來的hashCode做異或運(yùn)算,返回結(jié)果。(其中h>>>16,在JDK1.8中,優(yōu)化了高位運(yùn)算的算法,使用了零擴(kuò)展,無論正數(shù)還是負(fù)數(shù),都在高位插入0)。

(2)在putVal源碼中,我們通過(n-1)&hash獲取該對(duì)象的鍵在hashmap中的位置。(其中hash的值就是(1)中獲得的值)其中n表示的是hash桶數(shù)組的長(zhǎng)度,并且該長(zhǎng)度為2的n次方,這樣(n-1)&hash就等價(jià)于hash%n。因?yàn)?運(yùn)算的效率高于%運(yùn)算。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    ...

    if ((p = tab[i = (n - 1) & hash]) == null)//獲取位置
        tab[i] = newNode(hash, key, value, null);
    ...
}

tab即是table,n是map集合的容量大小,hash是上面方法的返回值。因?yàn)橥ǔB暶鱩ap集合時(shí)不會(huì)指定大小,或者初始化的時(shí)候就創(chuàng)建一個(gè)容量很大的map對(duì)象,所以這個(gè)通過容量大小與key值進(jìn)行hash的算法在開始的時(shí)候只會(huì)對(duì)低位進(jìn)行計(jì)算,雖然容量的2進(jìn)制高位一開始都是0,但是key的2進(jìn)制高位通常是有值的,因此先在hash方法中將key的hashCode右移16位在與自身異或,使得高位也可以參與hash,更大程度上減少了碰撞率。

下面舉例說明下,n為table的長(zhǎng)度。

5、重要方法分析

(1)putVal方法

首先說明,HashMap并沒有直接提供putVal接口給用戶調(diào)用,而是提供的put方法,而put方法就是通過putVal來插入元素的。

public V put(K key, V value) {
    // 對(duì)key的hashCode()做hash 
    return putVal(hash(key), key, value, false, true);  
} 

putVal方法執(zhí)行過程可以通過下圖來理解:

①.判斷鍵值對(duì)數(shù)組table[i]是否為空或?yàn)閚ull,否則執(zhí)行resize()進(jìn)行擴(kuò)容;

②.根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i,如果table[i]==null,直接新建節(jié)點(diǎn)添加,轉(zhuǎn)向⑥,如果table[i]不為空,轉(zhuǎn)向③;

③.判斷table[i]的首個(gè)元素是否和key一樣,如果相同直接覆蓋value,否則轉(zhuǎn)向④,這里的相同指的是hashCode以及equals;

④.判斷table[i] 是否為treeNode,即table[i] 是否是紅黑樹,如果是紅黑樹,則直接在樹中插入鍵值對(duì),否則轉(zhuǎn)向⑤;

⑤.遍歷table[i],判斷鏈表長(zhǎng)度是否大于8,大于8的話把鏈表轉(zhuǎn)換為紅黑樹,在紅黑樹中執(zhí)行插入操作,否則進(jìn)行鏈表的插入操作;遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可;

⑥.插入成功后,判斷實(shí)際存在的鍵值對(duì)數(shù)量size是否超多了最大容量threshold,如果超過,進(jìn)行擴(kuò)容。

具體源碼如下:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node[] tab; Node p; int n, i;
    // 步驟①:tab為空則創(chuàng)建 
    // table未初始化或者長(zhǎng)度為0,進(jìn)行擴(kuò)容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步驟②:計(jì)算index,并對(duì)null做處理  
    // (n - 1) & hash 確定元素存放在哪個(gè)桶中,桶為空,新生成結(jié)點(diǎn)放入桶中(此時(shí),這個(gè)結(jié)點(diǎn)是放在數(shù)組中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已經(jīng)存在元素
    else {
        Node e; K k;
        // 步驟③:節(jié)點(diǎn)key存在,直接覆蓋value 
        // 比較桶中第一個(gè)元素(數(shù)組中的結(jié)點(diǎn))的hash值相等,key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 將第一個(gè)元素賦值給e,用e來記錄
                e = p;
        // 步驟④:判斷該鏈為紅黑樹 
        // hash值不相等,即key不相等;為紅黑樹結(jié)點(diǎn)
        else if (p instanceof TreeNode)
            // 放入樹中
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        // 步驟⑤:該鏈為鏈表 
        // 為鏈表結(jié)點(diǎn)
        else {
            // 在鏈表最末插入結(jié)點(diǎn)
            for (int binCount = 0; ; ++binCount) {
                // 到達(dá)鏈表的尾部
                if ((e = p.next) == null) {
                    // 在尾部插入新結(jié)點(diǎn)
                    p.next = newNode(hash, key, value, null);
                    // 結(jié)點(diǎn)數(shù)量達(dá)到閾值,轉(zhuǎn)化為紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循環(huán)
                    break;
                }
                // 判斷鏈表中結(jié)點(diǎn)的key值與插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等,跳出循環(huán)
                    break;
                // 用于遍歷桶中的鏈表,與前面的e = p.next組合,可以遍歷鏈表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值與插入元素相等的結(jié)點(diǎn)
        if (e != null) { 
            // 記錄e的value
            V oldValue = e.value;
            // onlyIfAbsent為false或者舊值為null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替換舊值
                e.value = value;
            // 訪問后回調(diào)
            afterNodeAccess(e);
            // 返回舊值
            return oldValue;
        }
    }
    // 結(jié)構(gòu)性修改
    ++modCount;
    // 步驟⑥:超過最大容量 就擴(kuò)容 
    // 實(shí)際大小大于閾值則擴(kuò)容
    if (++size > threshold)
        resize();
    // 插入后回調(diào)
    afterNodeInsertion(evict);
    return null;
}

HashMap的數(shù)據(jù)存儲(chǔ)實(shí)現(xiàn)原理

流程:

根據(jù)key計(jì)算得到key.hash = (h = k.hashCode()) ^ (h >>> 16);

根據(jù)key.hash計(jì)算得到桶數(shù)組的索引index = key.hash & (table.length - 1),這樣就找到該key的存放位置了:

① 如果該位置沒有數(shù)據(jù),用該數(shù)據(jù)新生成一個(gè)節(jié)點(diǎn)保存新數(shù)據(jù),返回null;

② 如果該位置有數(shù)據(jù)是一個(gè)紅黑樹,那么執(zhí)行相應(yīng)的插入 / 更新操作;

③ 如果該位置有數(shù)據(jù)是一個(gè)鏈表,分兩種情況一是該鏈表沒有這個(gè)節(jié)點(diǎn),另一個(gè)是該鏈表上有這個(gè)節(jié)點(diǎn),注意這里判斷的依據(jù)是key.hash是否一樣:

如果該鏈表沒有這個(gè)節(jié)點(diǎn),那么采用尾插法新增節(jié)點(diǎn)保存新數(shù)據(jù),返回null;如果該鏈表已經(jīng)有這個(gè)節(jié)點(diǎn)了,那么找到該節(jié)點(diǎn)并更新新數(shù)據(jù),返回老數(shù)據(jù)。

注意:

HashMap的put會(huì)返回key的上一次保存的數(shù)據(jù),比如:

HashMap map = new HashMap();
System.out.println(map.put("a", "A")); // 打印null
System.out.println(map.put("a", "AA")); // 打印A
System.out.println(map.put("a", "AB")); // 打印AA
(2)getNode方法
說明:HashMap同樣并沒有直接提供getNode接口給用戶調(diào)用,而是提供的get方法,而get方法就是通過getNode來取得元素的。

public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    // table已經(jīng)初始化,長(zhǎng)度大于0,根據(jù)hash尋找table中的項(xiàng)也不為空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 桶中第一項(xiàng)(數(shù)組元素)相等
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 桶中不止一個(gè)結(jié)點(diǎn)
        if ((e = first.next) != null) {
            // 為紅黑樹結(jié)點(diǎn)
            if (first instanceof TreeNode)
                // 在紅黑樹中查找
                return ((TreeNode)first).getTreeNode(hash, key);
            // 否則,在鏈表中查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

(3)resize方法

①.在jdk1.8中,resize方法是在hashmap中的鍵值對(duì)大于閥值時(shí)或者初始化時(shí),就調(diào)用resize方法進(jìn)行擴(kuò)容;

②.每次擴(kuò)展的時(shí)候,都是擴(kuò)展2倍;

③.擴(kuò)展后Node對(duì)象的位置要么在原位置,要么移動(dòng)到原偏移量?jī)杀兜奈恢谩?/p>

final Node[] resize() {
    Node[] oldTab = table;//oldTab指向hash桶數(shù)組
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {//如果oldCap不為空的話,就是hash桶數(shù)組不為空
        if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了,就賦值為整數(shù)最大的閥值
            threshold = Integer.MAX_VALUE;
            return oldTab;//返回
        }//如果當(dāng)前hash桶數(shù)組的長(zhǎng)度在擴(kuò)容后仍然小于最大容量 并且oldCap大于默認(rèn)值16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold 雙倍擴(kuò)容閥值threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];//新建hash桶數(shù)組
    table = newTab;//將新數(shù)組的值復(fù)制給舊的hash桶數(shù)組
    if (oldTab != null) {//進(jìn)行擴(kuò)容操作,復(fù)制Node對(duì)象值到新的hash桶數(shù)組
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {//如果舊的hash桶數(shù)組在j結(jié)點(diǎn)處不為空,復(fù)制給e
                oldTab[j] = null;//將舊的hash桶數(shù)組在j結(jié)點(diǎn)處設(shè)置為空,方便gc
                if (e.next == null)//如果e后面沒有Node結(jié)點(diǎn)
                    newTab[e.hash & (newCap - 1)] = e;//直接對(duì)e的hash值對(duì)新的數(shù)組長(zhǎng)度求模獲得存儲(chǔ)位置
                else if (e instanceof TreeNode)//如果e是紅黑樹的類型,那么添加到紅黑樹中
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;//將Node結(jié)點(diǎn)的next賦值給next
                        if ((e.hash & oldCap) == 0) {//如果結(jié)點(diǎn)e的hash值與原h(huán)ash桶數(shù)組的長(zhǎng)度作與運(yùn)算為0
                            if (loTail == null)//如果loTail為null
                                loHead = e;//將e結(jié)點(diǎn)賦值給loHead
                            else
                                loTail.next = e;//否則將e賦值給loTail.next
                            loTail = e;//然后將e復(fù)制給loTail
                        }
                        else {//如果結(jié)點(diǎn)e的hash值與原h(huán)ash桶數(shù)組的長(zhǎng)度作與運(yùn)算不為0
                            if (hiTail == null)//如果hiTail為null
                                hiHead = e;//將e賦值給hiHead
                            else
                                hiTail.next = e;//如果hiTail不為空,將e復(fù)制給hiTail.next
                            hiTail = e;//將e復(fù)制個(gè)hiTail
                        }
                    } while ((e = next) != null);//直到e為空
                    if (loTail != null) {//如果loTail不為空
                        loTail.next = null;//將loTail.next設(shè)置為空
                        newTab[j] = loHead;//將loHead賦值給新的hash桶數(shù)組[j]處
                    }
                    if (hiTail != null) {//如果hiTail不為空
                        hiTail.next = null;//將hiTail.next賦值為空
                        newTab[j + oldCap] = hiHead;//將hiHead賦值給新的hash桶數(shù)組[j+舊hash桶數(shù)組長(zhǎng)度]
                    }
                }
            }
        }
    }
    return newTab;
}

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/69657.html

相關(guān)文章

  • 站在巨人肩膀上看源碼-HashSet

    摘要:實(shí)際運(yùn)行上面程序?qū)⒖吹匠绦蜉敵觯@是因?yàn)榕袛鄡蓚€(gè)對(duì)象相等的標(biāo)準(zhǔn)除了要求通過方法比較返回之外,還要求兩個(gè)對(duì)象的返回值相等。通常來說,所有參與計(jì)算返回值的關(guān)鍵屬性,都應(yīng)該用于作為比較的標(biāo)準(zhǔn)。 1.HashSet概述:   HashSet實(shí)現(xiàn)Set接口,由哈希表(實(shí)際上是一個(gè)HashMap實(shí)例)支持。它不保證set 的迭代順序;特別是它不保證該順序恒久不變。此類允許使用null元素。Hash...

    DevTTL 評(píng)論0 收藏0
  • 站在巨人肩膀上看源碼-Map

    摘要:在學(xué)習(xí)的實(shí)現(xiàn)類是基于實(shí)現(xiàn)的前,先來介紹下接口及其下的子接口先看下的架構(gòu)圖如上圖是映射接口,中存儲(chǔ)的內(nèi)容是鍵值對(duì)。是繼承于的接口。中的內(nèi)容是排序的鍵值對(duì),排序的方法是通過比較器。 Map 在學(xué)習(xí)Set(Set的實(shí)現(xiàn)類是基于Map實(shí)現(xiàn)的)、HashMap、TreeMap前,先來介紹下Map接口及其下的子接口.先看下Map的架構(gòu)圖:showImg(https://segmentfault.c...

    xiaotianyi 評(píng)論0 收藏0
  • 站在巨人肩膀上看源碼-ArrayList

    摘要:源碼剖析的源碼如下加入了比較詳細(xì)的注釋序列版本號(hào)基于該數(shù)組實(shí)現(xiàn),用該數(shù)組保存數(shù)據(jù)中實(shí)際數(shù)據(jù)的數(shù)量帶容量大小的構(gòu)造函數(shù)。該方法被標(biāo)記了,調(diào)用了系統(tǒng)的代碼,在中是看不到的,但在中可以看到其源碼。 ArrayList簡(jiǎn)介 ArrayList是基于數(shù)組實(shí)現(xiàn)的,是一個(gè)動(dòng)態(tài)數(shù)組,其容量能自動(dòng)增長(zhǎng),類似于C語(yǔ)言中的動(dòng)態(tài)申請(qǐng)內(nèi)存,動(dòng)態(tài)增長(zhǎng)內(nèi)存。ArrayList不是線程安全的,只能用在單線程環(huán)境下,多...

    ThinkSNS 評(píng)論0 收藏0
  • 站在巨人肩膀上看源碼-LinkedList

    摘要:在閱讀源碼之前,我們先對(duì)的整體實(shí)現(xiàn)進(jìn)行大致說明實(shí)際上是通過雙向鏈表去實(shí)現(xiàn)的。獲取的最后一個(gè)元素由于是雙向鏈表而表頭不包含數(shù)據(jù)。實(shí)際上是判斷雙向鏈表的當(dāng)前節(jié)點(diǎn)是否達(dá)到開頭反向迭代器獲取下一個(gè)元素。 第1部分 LinkedList介紹 LinkedList簡(jiǎn)介 LinkedList 是一個(gè)繼承于AbstractSequentialList的雙向鏈表。它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操...

    learn_shifeng 評(píng)論0 收藏0
  • 站在巨人肩膀上看源碼-ConcurrentHashMap

    摘要:一出現(xiàn)背景線程不安全的因?yàn)槎嗑€程環(huán)境下,使用進(jìn)行操作會(huì)引起死循環(huán),導(dǎo)致利用率接近,所以在并發(fā)情況下不能使用。是由數(shù)組結(jié)構(gòu)和數(shù)組結(jié)構(gòu)組成。用來表示需要進(jìn)行的界限值。也是,這使得能夠讀取到最新的值而不需要同步。 一、出現(xiàn)背景 1、線程不安全的HashMap 因?yàn)槎嗑€程環(huán)境下,使用Hashmap進(jìn)行put操作會(huì)引起死循環(huán),導(dǎo)致CPU利用率接近100%,所以在并發(fā)情況下不能使用HashMap。...

    n7then 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<