概覽
List
- ArrayList 實現(xiàn)了RandomAccess，可隨機讀取?？芍付ǔ跏伎臻g大小，默認(rèn)為10，超過此空間，數(shù)組空間增加以前的一半
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
//數(shù)組的定義
transient Object[] elementData;
//初始化 默認(rèn)大小 是10
private static final int DEFAULT_CAPACITY = 10;
//有意思的是 也定義了最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//初始化
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//實現(xiàn)原理是 創(chuàng)建一個Object類型的數(shù)組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
}
}
transient 一個對象只要實現(xiàn)了Serilizable接口，這個對象就可以被序列化,某個屬性不需要序列化，就可以用這個關(guān)鍵字
image
- 擴容
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//擴容大小是右移一位，比如初始化是10 即1010(10)右移一位變成0101(5)
//新的容量=old容量+old/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 然后把原來的數(shù)據(jù)復(fù)制到
elementData = Arrays.copyOf(elementData, newCapacity);
}
其他方法比較簡單，這里不寫了。
LinkedList：通過實現(xiàn)AbstractSequentialList來實現(xiàn)隨機的索引讀取。每個節(jié)點是Node,存有兩個指針Next，Prev,是個雙向鏈表。初始size=0，動態(tài)增加，不需預(yù)先分配空間，且實現(xiàn)了queue接口，可以查看首（first）尾(last)元素.
public class LinkedList<E> extends AbstractSequentialList<E>
//實現(xiàn)了deque接口
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
//初始化為0
transient int size = 0;
- 比較一下兩個
| 0 | ArrayList | LinkedList |
|---|---|---|
| 算法 | 數(shù)組 | 鏈表 |
| 優(yōu)勢 | 隨機讀取效率高 | 頭尾節(jié)點插入、刪除效率高 |
| 內(nèi)存占用 | 需要預(yù)留空間和擴容，內(nèi)存占用大 | 內(nèi)存占用小 |
| 遍歷 | 效率接近 | 需要用iterator遍歷 |
-
獲取線程安全的list
- 普通版
/**
* 獲取一個線程安全的LinkedList
*/
List synLinkedList = Collections.synchronizedList(new LinkedList());
/**
* 獲取一個線程安全的ArrayList
*/
List synArrayList = Collections.synchronizedList(new ArrayList());
或者
- Vector (ArrayList線程安全低配版 )
- 效率比arrayList差，一般不用，大部分方法都用synchronized修飾
- CopyOnWriteArrayList (ArrayList線程安全高配版 )
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
/** 加鎖 */
final transient ReentrantLock lock = new ReentrantLock();
/** 數(shù)組定義 用 volatile */
private transient volatile Object[] array;
- 插入
public boolean add(E e) {
final ReentrantLock lock = this.lock;
//加鎖
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
//先復(fù)制一個新的數(shù)組 然后插入到新的數(shù)組中
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
- 對比
- 讀沒有加鎖，所以不是絕對線程安全的。類似讀寫分離
- 讀性能比vector高，所以適合讀多寫少的場景。
Map
HashMap
- 理想狀態(tài)的hash算法是哈希表中的元素都是正常分布(不存在沖突)的,get,put操作時間復(fù)雜度都是O(1)
- K,V都可為null，所以get() 為null,不能判斷k為null，有可能是v為null,所以需要用containskey判斷
- 支持fail-fast
- 當(dāng)集合迭代時，其他線程修改了該線程，會拋出這個錯誤。
- 迭代器 Iterator
- 結(jié)構(gòu)圖
- HashMap采用數(shù)組鏈表的結(jié)構(gòu)<拉鏈法>來處理沖突，將散列到同一位置的數(shù)據(jù)頭插法插入一個鏈表。
- 在java8中，當(dāng)鏈表的長度大于8的時候?qū)⑦@個鏈表重構(gòu)成紅黑樹。
image
- 兩個影響性能的重要因素。初始容量initial capacity:16和負(fù)載因子local Factor:0.75：兩個影響性能的重要因素。
/**
* 默認(rèn)初始容量16，指的是桶的數(shù)量(數(shù)組的長度)，必須是2的N次冪
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
/**
* 最大的容量，可以在構(gòu)造的時候傳入?yún)?shù)，但是必需是小于2的30次冪=1073741824
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默認(rèn)的負(fù)載因子0.75，即使用容量超過初始容量*0.75必須擴容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 鏈表轉(zhuǎn)紅黑樹的閾值，大于這個值轉(zhuǎn)換
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 紅黑樹轉(zhuǎn)鏈表的閾值，小于這個值轉(zhuǎn)換
*/
static final int UNTREEIFY_THRESHOLD = 6;
- hashMap結(jié)構(gòu)
/**
* 哈希表，每個節(jié)點是Node<K,V>結(jié)構(gòu)，容量總是保持2的N次冪。
*/
transient Node<K,V>[] table;
- 節(jié)點 Node<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
/**
* 1 這個Next仍然是個Node 這種結(jié)構(gòu)決定了頭插法來鏈接鏈表的節(jié)點。
* 2 也說明了get()時它連K，V一起存**儲的，碰撞的時候hash值相同，我們也可以比較K的值來確定要返回的Value
*/
Node<K,V> next;
……
}
- 擴容
final Node<K,V>[] resize() {
……
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {//容量達到最大值
//把擴展閾值修改為最大，這樣以后就不能擴容了
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//容量翻倍
newThr = oldThr << 1;
}
……
- get()
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 &&
(first = tab[(n - 1) & hash]) != null) {
// 每次都需要一直檢查 first node
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) { //如果不是 則往下找
if (first instanceof TreeNode) //如果是樹形Node，則調(diào)用TreeNode的get方法
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {//否則直接查詢Next比較Key值。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
hashTable
線程安全
K,V都不允許為null
迭代器：Enumeration（枚舉類）
定義
//類型
private transient Entry<?,?>[] table;
//Entry<K,V>定義
private static class Entry<K,V> implements Map.Entry<K,V> {
// hashMap是node<> 但是結(jié)構(gòu)都是一樣的
static class Node<K,V> implements Map.Entry<K,V> {
- 初始化
//初始容量：11，負(fù)載因子：0.75f
public Hashtable() {
this(11, 0.75f);
}
- get()
//是線程安全的
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
//索引位置計算
int index = (hash & 0x7FFFFFFF) % tab.length;
//實現(xiàn)方式和hashMap有很大的不同
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
ConcurrentHashMap
- HashMap的線程安全版
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
//與hashMap不同的地方 用了volatile修飾
//保證了val被修改時線程可見性,無需加鎖便能實現(xiàn)線程安全的讀操作。
volatile V val;
volatile Node<K,V> next;
-
比Hashtable更高效的并發(fā)性能
- 使用分離鎖的思路解決并發(fā)性能，其將Entry數(shù)組拆分至16個Segment中，以哈希算法決定Entry應(yīng)該存儲在哪個Segment。在寫操作時只對一個Segment加鎖（hashMap對整個Entry加鎖），大幅提升了并發(fā)寫的性能。
-
缺點 :不能保證讀操作的絕對 一致性
- 如果寫操作在創(chuàng)建一個Entry,在寫操作完成之前(會加鎖)，讀操作不一定可以讀到這個Entry。
| 對比 | HashMap | Hashtable | Hashtable |
|---|---|---|---|
| 線程安全 | 否 | 是 | 是(不能保證數(shù)據(jù)絕對一致) |
| 性能 | 最好 | 最差 | 中間 |
TreeMap
- TreeMap是基于紅黑樹實現(xiàn)的Map結(jié)構(gòu)，其Entry類擁有到左/右葉子節(jié)點和父節(jié)點的引用，同時還記錄了自己的顏色
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
- 適合需要對key進行有序操作的場景。
- 提供了一系列方便的功能，比如獲取以升序或降序排列的KeySet()、獲取在指定key()之前/之后的key()等等
TreeSet
- 基于TreeMap構(gòu)造的Set，基本操作都是TreeMap的操作
HashSet 基本上就是用了hashTable
- 結(jié)構(gòu)
public HashSet() {
//直接就用了HashMap 真省事
map = new HashMap<>();
}
- add() 就是做了不能存儲重復(fù)value的操作
// Dummy value to associate with an Object in the backing Map 這個是不會重復(fù)的
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
- 存儲單值選hashSet（前提是數(shù)據(jù)不重復(fù)，否則就會丟失數(shù)據(jù)）查找速度理想是O(1)
結(jié)構(gòu)類似 只是簡單封裝
graph LR
HashMap-->HashSet
graph LR
TreeMap-->HashSet
