概覽
List
- ArrayList 實(shí)現(xiàn)了RandomAccess，可隨機(jī)讀取预麸〉山可指定初始空間大小，默認(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) {
//實(shí)現(xiàn)原理是 創(chuàng)建一個(gè)Object類型的數(shù)組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
}
}
transient 一個(gè)對(duì)象只要實(shí)現(xiàn)了Serilizable接口，這個(gè)對(duì)象就可以被序列化,某個(gè)屬性不需要序列化贡翘，就可以用這個(gè)關(guān)鍵字
image
- 擴(kuò)容
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//擴(kuò)容大小是右移一位蹈矮，比如初始化是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);
}
其他方法比較簡(jiǎn)單，這里不寫了鸣驱。
LinkedList：通過實(shí)現(xiàn)AbstractSequentialList來實(shí)現(xiàn)隨機(jī)的索引讀取泛鸟。每個(gè)節(jié)點(diǎn)是Node,存有兩個(gè)指針Next，Prev,是個(gè)雙向鏈表踊东。初始size=0北滥，動(dòng)態(tài)增加，不需預(yù)先分配空間闸翅，且實(shí)現(xiàn)了queue接口再芋，可以查看首（first）尾(last)元素.
public class LinkedList<E> extends AbstractSequentialList<E>
//實(shí)現(xiàn)了deque接口
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
//初始化為0
transient int size = 0;
- 比較一下兩個(gè)
| 0 | ArrayList | LinkedList |
|---|---|---|
| 算法 | 數(shù)組 | 鏈表 |
| 優(yōu)勢(shì) | 隨機(jī)讀取效率高 | 頭尾節(jié)點(diǎn)插入、刪除效率高 |
| 內(nèi)存占用 | 需要預(yù)留空間和擴(kuò)容坚冀，內(nèi)存占用大 | 內(nèi)存占用小 |
| 遍歷 | 效率接近 | 需要用iterator遍歷 |
-
獲取線程安全的list
- 普通版
/**
* 獲取一個(gè)線程安全的LinkedList
*/
List synLinkedList = Collections.synchronizedList(new LinkedList());
/**
* 獲取一個(gè)線程安全的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ù)制一個(gè)新的數(shù)組 然后插入到新的數(shù)組中
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
- 對(duì)比
- 讀沒有加鎖遗菠，所以不是絕對(duì)線程安全的联喘。類似讀寫分離
- 讀性能比vector高华蜒，所以適合讀多寫少的場(chǎng)景辙纬。
Map
HashMap
- 理想狀態(tài)的hash算法是哈希表中的元素都是正常分布(不存在沖突)的,get,put操作時(shí)間復(fù)雜度都是O(1)
- K,V都可為null，所以get() 為null,不能判斷k為null叭喜，有可能是v為null,所以需要用containskey判斷
- 支持fail-fast
- 當(dāng)集合迭代時(shí)贺拣，其他線程修改了該線程，會(huì)拋出這個(gè)錯(cuò)誤捂蕴。
- 迭代器 Iterator
- 結(jié)構(gòu)圖
- HashMap采用數(shù)組鏈表的結(jié)構(gòu)<拉鏈法>來處理沖突譬涡，將散列到同一位置的數(shù)據(jù)頭插法插入一個(gè)鏈表。
- 在java8中啥辨，當(dāng)鏈表的長度大于8的時(shí)候?qū)⑦@個(gè)鏈表重構(gòu)成紅黑樹涡匀。
image
- 兩個(gè)影響性能的重要因素。初始容量initial capacity:16和負(fù)載因子local Factor:0.75：兩個(gè)影響性能的重要因素溉知。
/**
* 默認(rèn)初始容量16陨瘩，指的是桶的數(shù)量(數(shù)組的長度)腕够，必須是2的N次冪
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
/**
* 最大的容量，可以在構(gòu)造的時(shí)候傳入?yún)?shù)舌劳，但是必需是小于2的30次冪=1073741824
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默認(rèn)的負(fù)載因子0.75帚湘，即使用容量超過初始容量*0.75必須擴(kuò)容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 鏈表轉(zhuǎn)紅黑樹的閾值，大于這個(gè)值轉(zhuǎn)換
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 紅黑樹轉(zhuǎn)鏈表的閾值甚淡，小于這個(gè)值轉(zhuǎn)換
*/
static final int UNTREEIFY_THRESHOLD = 6;
- hashMap結(jié)構(gòu)
/**
* 哈希表大诸，每個(gè)節(jié)點(diǎn)是Node<K,V>結(jié)構(gòu)，容量總是保持2的N次冪贯卦。
*/
transient Node<K,V>[] table;
- 節(jié)點(diǎn) Node<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
/**
* 1 這個(gè)Next仍然是個(gè)Node 這種結(jié)構(gòu)決定了頭插法來鏈接鏈表的節(jié)點(diǎn)资柔。
* 2 也說明了get()時(shí)它連K，V一起存**儲(chǔ)的脸侥，碰撞的時(shí)候hash值相同建邓，我們也可以比較K的值來確定要返回的Value
*/
Node<K,V> next;
……
}
- 擴(kuò)容
final Node<K,V>[] resize() {
……
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {//容量達(dá)到最大值
//把擴(kuò)展閾值修改為最大，這樣以后就不能擴(kuò)容了
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();
//索引位置計(jì)算
int index = (hash & 0x7FFFFFFF) % tab.length;
//實(shí)現(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被修改時(shí)線程可見性,無需加鎖便能實(shí)現(xiàn)線程安全的讀操作外遇。
volatile V val;
volatile Node<K,V> next;
-
比Hashtable更高效的并發(fā)性能
- 使用分離鎖的思路解決并發(fā)性能注簿，其將Entry數(shù)組拆分至16個(gè)Segment中，以哈希算法決定Entry應(yīng)該存儲(chǔ)在哪個(gè)Segment跳仿。在寫操作時(shí)只對(duì)一個(gè)Segment加鎖（hashMap對(duì)整個(gè)Entry加鎖）诡渴，大幅提升了并發(fā)寫的性能。
-
缺點(diǎn) :不能保證讀操作的絕對(duì) 一致性
- 如果寫操作在創(chuàng)建一個(gè)Entry,在寫操作完成之前(會(huì)加鎖)菲语，讀操作不一定可以讀到這個(gè)Entry妄辩。
| 對(duì)比 | HashMap | Hashtable | Hashtable |
|---|---|---|---|
| 線程安全 | 否 | 是 | 是(不能保證數(shù)據(jù)絕對(duì)一致) |
| 性能 | 最好 | 最差 | 中間 |
TreeMap
- TreeMap是基于紅黑樹實(shí)現(xiàn)的Map結(jié)構(gòu)，其Entry類擁有到左/右葉子節(jié)點(diǎn)和父節(jié)點(diǎn)的引用山上，同時(shí)還記錄了自己的顏色
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;
- 適合需要對(duì)key進(jìn)行有序操作的場(chǎng)景眼耀。
- 提供了一系列方便的功能，比如獲取以升序或降序排列的KeySet()佩憾、獲取在指定key()之前/之后的key()等等
TreeSet
- 基于TreeMap構(gòu)造的Set哮伟，基本操作都是TreeMap的操作
HashSet 基本上就是用了hashTable
- 結(jié)構(gòu)
public HashSet() {
//直接就用了HashMap 真省事
map = new HashMap<>();
}
- add() 就是做了不能存儲(chǔ)重復(fù)value的操作
// Dummy value to associate with an Object in the backing Map 這個(gè)是不會(huì)重復(fù)的
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
- 存儲(chǔ)單值選hashSet（前提是數(shù)據(jù)不重復(fù)，否則就會(huì)丟失數(shù)據(jù)）查找速度理想是O(1)
結(jié)構(gòu)類似 只是簡(jiǎn)單封裝
graph LR
HashMap-->HashSet
graph LR
TreeMap-->HashSet
