Java 集合

java集合

fail-fast機制

在java集合類中,使用

modCount

來檢查數組的狀态.

當在疊代集合的時候,(通常會實作

iterator()方法

來擷取疊代對象,或者

foreach

集合裡面的資料,在其他地方被修改了,這個時候

modCount

就會被修改,與疊代過程的

modCount

不一緻.将抛出

ConcurrentModificationException

異常,這個過程就叫

fail-fast

List 篇

主要介紹

ArrayList

Vector

和

LinkedList

CopyOnWriteArrayList

ArrayList

是一個數組長度可自增長的線程不安全的清單.内部使用數組實作.

Object[] elementData

預設的長度為 10.
fail-fast
自動擴容(每次擴容為原來的1.5倍)
線程不安全
使用連續控件存儲
繼承自 List RandomAccess 等.
允許添加 null 值

時間複雜度 :

根據索引查詢,複雜度為

O(1)

根據元素查詢,複雜度為

O(N)

插入和删除,如果在列首複雜度為

O(N)

;在列尾複雜度為

O(1)

;平均複雜為

O(N)

插入和删除非列尾資料, 将會導緻數組移動資料.

RandomAccess 接口

RandomAccess

是一個标記接口(沒有任何方法).

如果實作了

RandomAccess

接口,表示該集合可以進行随機快速通路(通常底層是數組形式的集合),如

ArrayList

可以快速通路的集合,使用

for (int i=0, n<size; i++)
    list.get(i);

未實作

RandomAccess

接口的集合,如

LinkedList

,使用疊代器效率更高.

for (Iterator i=list.iterator(); i.hasNext(); )
    i.next();

使用

instanceof RandomAccess

來判斷是否支援随機快速通路.

Vector

是一個數組長度可自增長的線程安全的清單,内部使用數組實作.

自動擴容(可設定每次擴容的增量值,預設擴容為原來的2倍.)
線程安全( synchronized )
RandomAccess List
null

線程安全的

vector

,照樣可以觸發

fail-fast

時間複雜度與

arraylist

一樣.

在不涉及線程安全的前提下,

arraylist

效率更高.

fun main(args: Array<String>) {
    val vector = Vector(listOf(1, 2, 3, 4, 5))

    singleThread(vector)
    multiThread(vector)
    multiThreadSynchronized(vector)
}

/**
 * 單線程下,疊代抛出 ConcurrentModificationException
 */
fun singleThread(vector: Vector<Int>) {
    val it = vector.iterator()
    while (it.hasNext()) {
        println(it.next())
        vector.add(1)
    }
}

/**
 * 多線程下,疊代抛出 ConcurrentModificationException
 */
fun multiThread(vector: Vector<Int>) {
    thread {
        repeat(10000) {
            vector.add(it)
        }
    }

    thread {
        vector.forEach { println(it) }
    }
}

/**
 * 多線程下,修改vector是添加同步鎖,避免同時疊代同時修改
 */
fun multiThreadSynchronized(vector: Vector<Int>) {
    thread {
        synchronized(vector) {
            repeat(10000) {
                vector.add(it)
            }
        }
    }

    thread {
        vector.forEach { println(it) }
    }
}

Stack

vector

,線程安全,棧結構,

先進後出

LinkedList

是以雙向連結清單方式實作的非線程安全的集合.

一個元素節點包含上一個節點和下一個節點的引用,以及自身的值.
記憶體空間可不連續
List Deque
null

時間複雜度:

删除和插入元素,複雜度為

O(1)

查詢時,由于采用雙向連結清單,判斷離哪頭近,從哪頭開始找.

最糟糕的情況是

O(N/2)

,是以它的複雜度為

O(N)

CopyOnWriteArrayList

CopyOnWriteArrayList

是并發包中的實作.使用

ReenterLock

System.arraycopy

來實作數組讀寫的線程安全.

在讀取的時不加鎖,是以可以支援多線程同時讀取資料,并且同時讀取數不受限制.

在寫入(add,set,remove等操作)的時候,使用

ReenterLock

鎖住方法,然後操作資料時先将原數組拷貝一份,對拷貝資料進行操作,操作完後将拷貝的原來的資料引用指向拷貝的數組引用,實作資料的更新操作,更新完後釋放鎖. 和其名字操作一緻(寫時拷貝).

沒有設定初始長度的方法和擴容的政策. 因為該數組在每次添加資料是, 都會使用

System.arraycopy

拷貝一份比目前資料 +1 的數組.

public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

ArrayList,Vector和LinkedList的差別

ArrayList

Vector

内部都是使用數組實作的.它們的主要差別在于

ArrayList 是線程不安全的, Vector 是線程安全的.
ArrayList 自動擴容時固定增長為原來的1.5倍,不可指定增量值. Vector 可指定每次的增量值,如果沒指定,則擴容為原來的2倍.

在不考慮線程安全的情況下,優先使用

ArrayList

,如果在使用前,能夠預估大概有元素,建立時指定個數,效果更好.

LinkedList

使用雙向連結清單實作,也是線程不安全的.與

ArrayList

的差別在于

實作方式不同. ArrayList 使用數組, Vector 使用雙向連結清單.
記憶體空間管理不同, LinkedList 可以是不連續的空間, ArrayList 需要連續的記憶體空間.
LinkedList 在删除和插入上的性能較好, ArrayList 在查詢上的效率更好.
ArrayList 一個item隻存自己的值,比較省空間, LinkedList 一個item除了自己的值,還需要存放上一個和下一個元素的引用,比較費空間.

如果主要需要對清單進行周遊,以及增删操作,使用

LinkedList

其他情況使用

ArrayList

如果需要用到線程安全的清單,請使用

CopyOnWriteArrayList

Map篇

Map

是以鍵值對形式存儲的集合.

HashMap

TreeMap

Hashtable

ConcurrentHashMap

HashMap

HashMap

内部混合使用數組,連結清單,紅黑樹的結構來建構的鍵值對集合.

HashMap

的本質基礎是基于數組的. 數組的各個元素,使用單向連結清單的結構.(

Node(int hash, K key, V value, Node<K,V> next)

HashMap

通過哈希函數(

hash()

)來完成

key

對

index

的映射.

當出現hash後index沖突(index位置已經存在不同的key的鍵值對)時,資料将在index位置,使用單向連結清單或紅黑樹(當連結清單長度大于等8個時,連結清單中的所有元素改用紅黑樹存放)來存放元素.

當使用掉的索引占用了數組長度的一定比例時(

填裝因子

HashMap

将進行擴容(擴容為原來的兩倍,key與index重新映射).

HashMap

的性能瓶頸:

優良的哈希函數.

理想的狀态是,每一個鍵值對的存放,能夠比較均勻适當的分布在數組的索引上,盡量避免過多的hash值沖突.

// java 8 中的實作
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
// index = (n - 1) & hash , 2的次方來說就是取餘操作.
// 由于 (n -1)的二進制 高位都是0,地位都是1.
// hashcode 與 它進行 & 操作的話, hashcode的高位變化低位不變,則計算出來的index值講不變.
// 為了消除高位變化 不影響 index 的值, 于是将 hashcode 的 高16位 移動到低16位,再和 hashcode進行 ^ 操作.
// 這樣高位的變化,也能影響index值, 降低了沖突的機率.

填裝因子

過低的填裝因子,如填裝因子=0.5,容量剩餘一半的時候就擴容,可能導緻空間上的浪費.

過高的填裝因子,可能導緻為了命中未使用的索引,而頻繁出現沖突.

HashMap

實作中,填裝因子預設使用

0.75

的值.

特點 :

預設的長度為 16,預設填裝因子為 0.75.
自動擴容(預設擴容為原來的2倍.)
混合使用數組,連結清單和紅黑樹
Map
key value 都可以添加 null
插入和周遊順序不一緻

查詢,插入和删除操作的平均時間複雜度為

O(1)

極端情況下(全部發生沖突),若長度小于8,使用單項連結清單,複雜度為

O(n)

,如果長度大于等于8,使用紅黑樹,複雜度為

O(logn)

LinkedHashMap

HashMap

, 底層使用哈希表與雙向連結清單來儲存元素,與

HashMap

的差異就在于通路順序上.

構造中,

accessOrder

預設為 false，代表按照插入順序進行疊代；為 true，代表以通路順序進行疊代(最常通路的在前,最不經常通路的在後

LRU

)。

TreeMap

TreeMap

内部使用

紅黑樹

來實作的鍵值對集合.與HashMap相比，TreeMap是一個能比較元素大小的Map集合，會對傳入的key進行了大小排序。其中，可以使用元素的自然順序，也可以使用集合中自定義的比較器來進行排序.

使用紅黑樹實作
key value null
支援對 key 排序
NavigableMap ,擁有強大的搜尋功能.

紅黑樹

是自平衡的二叉搜尋樹, 查詢,添加删除效率都是

O(logn)

HashTable

HashTable

内部使用數組和單項連結清單實作的鍵值對集合.

HashTable

的哈希函數

(hash & 0x7FFFFFFF) % tab.length

,隻是對key的

hashcod

進行取整和取餘操作.

HashTable預設的初始大小為11，之後每次擴充為原來的2n+1。

也就是說，HashTable的連結清單數組的預設大小是一個素數、奇數。之後的每次擴充結果也都是奇數。

由于HashTable會盡量使用素數、奇數作為容量的大小。當哈希表的大小為素數時，簡單的取模哈希的結果會更加均勻。（這個是可以證明出來的，可參考：
http://zhaox.github.io/algorithm/2015/06/29/hash ）

預設的長度為 11,預設填裝因子為 0.75.
自動擴容(擴容為原來的2n+1)
線程安全
混合使用數組,連結清單
Map
key value 都不能使用 null 值,否則抛出空指針異常.

HashMap

一緻

ConcurrentHashMap (java.util.concurrent)

HashMap

一樣,是内部使用數組,連結清單,紅黑樹的結構來建構的鍵值對集合,因為需要保證線程安全,是以内部實作更加複雜.

哈希函數

(h ^ (h >>> 16)) & HASH_BITS

, 和

HashMap

類似,與高位進行異或操作的方式,來消除高位資料變化導緻索引不變的情況,多加了一步正數的操作.

當沖突的連結清單中個數超過8個, 如果數組長度小于64,則擴容,否則,将連結清單資料轉化為紅黑樹結構存儲.

ConcurrentHashMap

采用

CAS(Compare and Swap)

原子類型操作,來保證線程的安全性. 較 jdk1.7 的分段鎖機制性能更好.

預設長度為16,無預設的裝填因子

構造函數為 :

ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)

沒有預設的裝填因子,傳入初始容量和裝填因子後,會被算法調整為 2次方,最小容量為 16.

并發級别,表示可以同時對資料進行寫操作的線程數, 最大可達16. 讀取不受限制.

沒有 fail-fast, 将保證線程安全.
自動擴容為原來的 2 倍.
ConcurrentMap
key value 都不可以添加 null

HashMap

`HashMap` `HashTable` `ConcurrentHashMap` 對比

HashMap

線程不安全 ,

HashTable

線程安全,但還是存在

fail-fast

問題 ,

ConcurrentHashMap

線程安全,不存在

fail-fast

問題.

HashMap

ConcurrentHashMap

内部都是用數組,連結清單加紅黑樹來建構.(較高效)

HashTable

使用數組加連結清單.

HashMap

ConcurrentHashMap

都是用高位異或的雜湊演算法.

HashTable

采用數組長度為素數,直接取餘的雜湊演算法.

HashMap

允許插入

null

鍵值對,

HashTable

ConcurrentHashMap

不允許.

結論 : 不考慮線程安全的情況下使用 HashMap , 線程安全則使用 ConcurrentHashMap 如果知道大概會存多少資料,指定初始容量會更高效, 避免擴容和重新hash映射産生的效率問題.

Set篇

Set

是沒有重複元素的單元素集合.

TreeSet

TreeMap

實作.

HashSet

HashMap

實作. 當構造參數為三個時

LinkedHashMap

LinkedHashSet

HashSet

,但是都是調用

HashSet

中有三個構造參數的

LinkedHashMap

來實作.

Java 集合

fail-fast機制

List 篇

ArrayList

RandomAccess 接口

Vector

Stack

LinkedList

CopyOnWriteArrayList

ArrayList,Vector和LinkedList的差別

Map篇

HashMap

LinkedHashMap

TreeMap

HashTable

ConcurrentHashMap (java.util.concurrent)

`HashMap` `HashTable` `ConcurrentHashMap` 對比

Set篇

繼續閱讀

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希

Java 集合

fail-fast機制

List 篇

ArrayList

RandomAccess 接口

Vector

Stack

LinkedList

CopyOnWriteArrayList

ArrayList,Vector和LinkedList的差別

Map篇

HashMap

LinkedHashMap

TreeMap

HashTable

ConcurrentHashMap (java.util.concurrent)

HashMap HashTable ConcurrentHashMap 對比

Set篇

繼續閱讀

`HashMap` `HashTable` `ConcurrentHashMap` 對比