【一文系列】一文了解java常用集合類(含源碼)

iliyaku 發(fā)布于2019-08-19 10:15 / 3424人閱讀

摘要：包含兩個(gè)重要的成員和。對(duì)于多線程環(huán)境，且可能同時(shí)被多個(gè)線程操作，此時(shí)，應(yīng)該使用同步的類如。小于等于且大于，代表用戶創(chuàng)建了一個(gè)，但是使用的構(gòu)造函數(shù)為或或，導(dǎo)致為，為，為用戶指定的的初始容量。本質(zhì)上是數(shù)組單向鏈表紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)如下圖。

一、List 1、ArrayList

① 關(guān)鍵源碼

// 默認(rèn)初始化為空數(shù)組
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 添加元素
public boolean add(E e) {
    // 增加modCount, 判斷擴(kuò)容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// 擴(kuò)容函數(shù)
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新的容量等于舊容量的1.5倍，使用位移更高效
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 擴(kuò)容是一個(gè)數(shù)組復(fù)制的過(guò)程
    elementData = Arrays.copyOf(elementData, newCapacity);
}

② 特點(diǎn)

空集合第一次添加元素時(shí)默認(rèn)初始容量為10

線程不安全(在單線程中才使用ArrayList，而在多線程中可以選擇Vector[方法加了sync關(guān)鍵字]或者CopyOnWriteArrayList[juc包])

遍歷時(shí)，使用隨機(jī)訪問(wèn)(即，通過(guò)索引序號(hào)訪問(wèn))效率最高，而使用迭代器的效率最低

fail-fast 機(jī)制

fail-fast 機(jī)制是java集合(Collection)中的一種錯(cuò)誤機(jī)制。當(dāng)多個(gè)線程對(duì)同一個(gè)集合的內(nèi)容進(jìn)行操作時(shí)，就可能會(huì)產(chǎn)生fail-fast事件。

AbstractList 源碼中，每修改一次(添加/刪除等操作)，將modCount+1
由于實(shí)現(xiàn)的 Itr 類中， next() 和 remove()都會(huì)執(zhí)行 checkForComodification()
若 “modCount 不等于expectedModCount”，則拋出ConcurrentModificationException異常，產(chǎn)生fail-fast事件。
所以當(dāng)多個(gè)線程同時(shí)操作時(shí)，會(huì)拋出ConcurrentModificationException異常

2、LinkedList

① 關(guān)鍵源碼

// 初始化空列表
public LinkedList() {
}

// 在列表末尾添加一個(gè)節(jié)點(diǎn)
public boolean add(E e) {
    linkLast(e);
    return true;
}

// linkLast函數(shù)
void linkLast(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        // last為空說(shuō)明是個(gè)空列表，插入的則為第一個(gè)節(jié)點(diǎn)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

// Node類
private static class Node {
    E item;
    Node next;
    Node prev;

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

② 特點(diǎn)

LinkedList的本質(zhì)是雙向鏈表。

LinkedList包含兩個(gè)重要的成員：Node 和 size。

Node是雙向鏈表節(jié)點(diǎn)所對(duì)應(yīng)的類的實(shí)例。Node中包含成員變量： prev, next, item

prev是該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，next是該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，item是該節(jié)點(diǎn)所包含的值。size是雙向鏈表中節(jié)點(diǎn)的個(gè)數(shù)。

3、LinkedList和ArrayList使用場(chǎng)景和性能分析

1、ArrayList 是一個(gè)數(shù)組隊(duì)列，相當(dāng)于動(dòng)態(tài)數(shù)組。它由數(shù)組實(shí)現(xiàn)，隨機(jī)訪問(wèn)效率高，隨機(jī)插入、隨機(jī)刪除效率低(涉及到復(fù)制)。
2、LinkedList 是一個(gè)雙向鏈表。它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作。LinkedList隨機(jī)訪問(wèn)效率低，但隨機(jī)插入、隨機(jī)刪除效率高。

(01) 對(duì)于需要快速插入，刪除元素，應(yīng)該使用LinkedList。
(02) 對(duì)于需要快速隨機(jī)訪問(wèn)元素，應(yīng)該使用ArrayList。
(03) 對(duì)于“單線程環(huán)境” 或者 “多線程環(huán)境，但List僅僅只會(huì)被單個(gè)線程操作”，此時(shí)應(yīng)該使用非同步的類(如ArrayList)。
     對(duì)于“多線程環(huán)境，且List可能同時(shí)被多個(gè)線程操作”，此時(shí)，應(yīng)該使用同步的類(如CopyOnWriteArrayList)。

二、Map 1、HashMap

① 關(guān)鍵源碼

// 加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 初始的加載因子默認(rèn)為0.75，此時(shí)還沒(méi)有初始化容量，在put的時(shí)候會(huì)進(jìn)行resize()將容量初始化為16
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}


public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
* key 的 hash值的計(jì)算是通過(guò)hashCode()的高16位異或低16位實(shí)現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)
* 這么做可以在數(shù)組table的length比較小的時(shí)候
* 也能保證考慮到高低Bit都參與到Hash的計(jì)算中，同時(shí)不會(huì)有太大的開(kāi)銷
*/
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 重點(diǎn)的putVal邏輯
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    // 如果table為null或者0，則進(jìn)行resize()操作  resize()方法在下面再說(shuō)
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 確定插入table的位置，算法是(n - 1) & hash，在n為2的冪時(shí)，相當(dāng)于除模取余操作。(這也是為什么長(zhǎng)度要取2的冪次方的原因之一)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
        
    // 在table的i位置發(fā)生hash碰撞或者除模取余后相同結(jié)果，有兩種情況：
    // 1、key值是一樣的，就替換成value值
    // 2、key值不一樣的有兩種處理方式：a、存儲(chǔ)在i位置的鏈表(鏈表長(zhǎng)度達(dá)到8時(shí)轉(zhuǎn)成紅黑樹(shù)); b、存儲(chǔ)在紅黑樹(shù)中
    else {
        Node e; K k;
        // key值是一樣的，替換value值
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 是紅黑樹(shù)結(jié)構(gòu)就putTreeVal
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 不是TreeNode,即為鏈表,遍歷鏈表并且去跟鏈表的每一個(gè)key做比較
            for (int binCount = 0; ; ++binCount) {
                // 直到鏈表的下一個(gè)節(jié)點(diǎn)為null，就進(jìn)去新建個(gè)節(jié)點(diǎn)
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 根據(jù)binCount去記錄鏈表的長(zhǎng)度，超過(guò)8就轉(zhuǎn)紅黑樹(shù)
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

final Node[] resize() {
    // 保存當(dāng)前table
    Node[] oldTab = table;
    // 保存當(dāng)前table的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 保存當(dāng)前閾值
    int oldThr = threshold;
    // 初始化新的table容量和閾值 
    int newCap, newThr = 0;
    /*
      1. resize（）函數(shù)在size　> threshold時(shí)被調(diào)用。oldCap大于 0 代表原來(lái)的 table 表非空，
      oldCap 為原表的大小，oldThr（threshold） 為 oldCap × load_factor
   */
    if (oldCap > 0) {
        // 若舊table容量已超過(guò)最大容量，更新閾值為Integer.MAX_VALUE（最大整形值），這樣以后就不會(huì)自動(dòng)擴(kuò)容了。
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 容量翻倍，使用左移，效率更高
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    /*
       2. resize（）函數(shù)在table為空被調(diào)用。oldCap 小于等于 0 且 oldThr 大于0，代表用戶創(chuàng)建了一個(gè) HashMap，但是使用的構(gòu)造函數(shù)為      
       HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)
       或 HashMap(Map m)，導(dǎo)致 oldTab 為 null，oldCap 為0， oldThr 為用戶指定的 HashMap的初始容量。
    */
    else if (oldThr > 0) // initial capacity was placed in threshold
        //當(dāng)table沒(méi)初始化時(shí)，threshold持有初始容量。還記得threshold = tableSizeFor(t)么;
        newCap = oldThr;
    /*
        3. resize（）函數(shù)在table為空被調(diào)用。oldCap 小于等于 0 且 oldThr 等于0，用戶調(diào)用 HashMap()構(gòu)造函數(shù)創(chuàng)建的　HashMap，所有值均采用默認(rèn)值，oldTab（Table）表為空，oldCap為0，oldThr等于0，
    */
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 新閾值為0
    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"})
    // 初始化table
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 把 oldTab 中的節(jié)點(diǎn)　reHash 到　newTab 中去
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 若節(jié)點(diǎn)是單個(gè)節(jié)點(diǎn)，直接在 newTab　中進(jìn)行重定位
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 若節(jié)點(diǎn)是　TreeNode 節(jié)點(diǎn)，要進(jìn)行 紅黑樹(shù)的 rehash　操作
                else if (e instanceof TreeNode)
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                // 若是鏈表，進(jìn)行鏈表的 rehash　操作
                else { // preserve order
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    // 將同一桶中的元素根據(jù)(e.hash & oldCap)是否為0進(jìn)行分割（代碼后有圖解，可以回過(guò)頭再來(lái)看），分成兩個(gè)不同的鏈表，完成rehash
                    do {
                        next = e.next;
                        // 根據(jù)算法　e.hash & oldCap 判斷節(jié)點(diǎn)位置rehash　后是否發(fā)生改變
                        // 最高位==0，這是索引不變的鏈表。
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //最高位==1 （這是索引發(fā)生改變的鏈表）
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原bucket位置的尾指針不為空(即還有node)
                    if (loTail != null) {
                        // 鏈表最后得有個(gè)null
                        loTail.next = null;
                        // 鏈表頭指針?lè)旁谛峦暗南嗤聵?biāo)(j)處
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // rehash　后節(jié)點(diǎn)新的位置一定為原來(lái)基礎(chǔ)上加上　oldCap，具體解釋看下圖
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

② 特點(diǎn)

HashMap 的實(shí)現(xiàn)不是線程安全的。它的key、value都可以為null。

初始化時(shí)加載因子為0.75，有put操作時(shí)將容量初始化為16(哈希表的桶數(shù)，即entry的數(shù)量)

當(dāng)哈希表中的條目數(shù)超出了加載因子與容量的乘積時(shí)(如0.75 * 16)，則要對(duì)該哈希表進(jìn)行resize操作（同時(shí)會(huì)進(jìn)行rehash操作，重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)），從而哈希表將具有兩倍的容量。

HashMap是通過(guò)拉鏈法實(shí)現(xiàn)的散列表。本質(zhì)上是數(shù)組 + 單向鏈表 + 紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)(如下圖)。

HashMap使用鏈表法避免哈希沖突(相同hash值)，當(dāng)鏈表長(zhǎng)度大于TREEIFY_THRESHOLD（默認(rèn)為8，設(shè)為8是因?yàn)檫_(dá)到8的概率為0.00000006，概率低）時(shí)，將鏈表轉(zhuǎn)換為紅黑樹(shù)(在轉(zhuǎn)紅黑樹(shù)之前會(huì)再進(jìn)行一次判斷map的容量是否小于64，是的話不會(huì)進(jìn)行轉(zhuǎn)紅黑樹(shù)，而是先resize()擴(kuò)容)，如果之后小于UNTREEIFY_THRESHOLD（默認(rèn)為6）時(shí)，又會(huì)轉(zhuǎn)回鏈表以達(dá)到性能均衡。

HashMap的數(shù)據(jù)結(jié)構(gòu)(圖片源自網(wǎng)絡(luò)，侵刪)

2、LinkedHashMap

① 關(guān)鍵源碼

// LinkedHashMap繼承了HashMap，實(shí)現(xiàn)Map接口
public class LinkedHashMap
    extends HashMap
    implements Map

// 初始化是默認(rèn)容量16，加載因子0.75.并且設(shè)定了 accessOrder = false，表示默認(rèn)按照插入順序進(jìn)行遍歷
public LinkedHashMap() {
    super();
    accessOrder = false;
}

② 特點(diǎn)

LinkedHashMap 是基于 HashMap 實(shí)現(xiàn)的一種集合，具有 HashMap 集合上面所說(shuō)的所有特點(diǎn)

除了 HashMap 無(wú)序的特點(diǎn)，LinkedHashMap 是有序的

LinkedHashMap 在 HashMap 的基礎(chǔ)上多帶帶維護(hù)了一個(gè)具有所有數(shù)據(jù)的雙向鏈表，該鏈表保證了元素迭代的順序

數(shù)據(jù)結(jié)構(gòu)圖

(圖片源自網(wǎng)絡(luò)，侵刪)

三、Set 1、HashSet

① 關(guān)鍵源碼

// HashSet 實(shí)現(xiàn)了 Cloneable 接口和 Serializable 接口，分別用來(lái)支持克隆以及支持序列化。還實(shí)現(xiàn)了 Set 接口，該接口定義了 Set 集合類型的一套規(guī)范
public class HashSet
    extends AbstractSet
    implements Set, Cloneable, java.io.Serializable
    
// HashSet集合中的內(nèi)容是通過(guò) HashMap 數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)的
private transient HashMap map;
// 向HashSet中添加數(shù)據(jù)，數(shù)據(jù)在上面的 map 結(jié)構(gòu)是作為 key 存在的，而value統(tǒng)一都是 PRESENT
private static final Object PRESENT = new Object();

// 初始化時(shí)就是new一個(gè)HashMap
public HashSet() {
    map = new HashMap<>();
}

// 將 e 作為 key，PRESENT 作為 value 插入到 map 集合中，如果 e 不存在，則插入成功返回 true;如果存在，則返回false
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

② 特點(diǎn)

HashSet 是一個(gè)沒(méi)有重復(fù)元素的集合。

它是由HashMap實(shí)現(xiàn)的，不保證元素的順序，而且HashSet允許使用 null 元素。

GPU云服務(wù)器云服務(wù)器 java集合工具類 java集合類詳解、 java集合類詳解 java集合源碼分析

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/75705.html

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

登陸后可評(píng)論

0條評(píng)論

iliyaku

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

四舍五入（YZOJ-1012）

閱讀 1772·2021-10-09 09:44
【C語(yǔ)言操作符多圖詳解】——“講述你所未知的操作符細(xì)節(jié)”

閱讀 3340·2021-09-27 13:36
國(guó)外主機(jī)如何備案-國(guó)外的云主機(jī)可以在中國(guó)備案嗎？

閱讀 1595·2021-09-22 15:33
云主機(jī)用什么系統(tǒng)-云主機(jī)怎么使用？

閱讀 1334·2021-09-22 15:23
用Python保住“設(shè)計(jì)大哥“的頭發(fā)，直接甩給他10000張參考圖，爬蟲(chóng)采集【稿定設(shè)計(jì)】平面模板素材

閱讀 1244·2021-09-06 15:02
css清除浮動(dòng)常用的四種方法實(shí)現(xiàn)

閱讀 1766·2019-08-29 16:14
前端每日實(shí)戰(zhàn)：25# 視頻演示如何用純 CSS 創(chuàng)作一個(gè)慧星拖尾效果的 loader 動(dòng)畫(huà)

閱讀 2981·2019-08-29 15:26
自我總結(jié)CSS中的陷阱（長(zhǎng)期更新）

閱讀 2471·2019-08-28 18:08

亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

【一文系列】一文了解java常用集合類(含源碼)

相關(guān)文章

Java相關(guān)

「碼個(gè)蛋」2017年200篇精選干貨集合

**一文掌握關(guān)于Java數(shù)據(jù)結(jié)構(gòu)所有知識(shí)點(diǎn)（歡迎一起完善）**

從能做什么到如何去做，一文帶你快速掌握Python編程基礎(chǔ)與實(shí)戰(zhàn)

??蘇州程序大白一文從基礎(chǔ)手把手教你Python數(shù)據(jù)可視化大佬??《??記得收藏??》

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

0條評(píng)論

iliyaku

男|高級(jí)講師

TA的文章

四舍五入（YZOJ-1012）

【C語(yǔ)言操作符多圖詳解】——“講述你所未知的操作符細(xì)節(jié)”

國(guó)外主機(jī)如何備案-國(guó)外的云主機(jī)可以在中國(guó)備案嗎？

云主機(jī)用什么系統(tǒng)-云主機(jī)怎么使用？

用Python保住“設(shè)計(jì)大哥“的頭發(fā)，直接甩給他10000張參考圖，爬蟲(chóng)采集【稿定設(shè)計(jì)】平面模板素材

css清除浮動(dòng)常用的四種方法實(shí)現(xiàn)

前端每日實(shí)戰(zhàn)：25# 視頻演示如何用純 CSS 創(chuàng)作一個(gè)慧星拖尾效果的 loader 動(dòng)畫(huà)

自我總結(jié)CSS中的陷阱（長(zhǎng)期更新）

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

【一文系列】一文了解java常用集合類(含源碼)

相關(guān)文章

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

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！