移步數(shù)據(jù)結(jié)構(gòu)--容器匯總（java & Android）
內(nèi)容：
- Vector 介紹及與 ArrayList 的區(qū)別
- ArrayList 與 LinkedList 的區(qū)別
- Stack 類(lèi)的介紹及實(shí)現(xiàn)一個(gè)簡(jiǎn)單的 Stack
-
SynchronizedList 與 Vector的區(qū)別
image
1 Vector
- Vector 是一個(gè)相當(dāng)古老的 Java 容器類(lèi)，始于 JDK 1.0控硼，并在 JDK 1.2 時(shí)代對(duì)其進(jìn)行修改摔敛，使其實(shí)現(xiàn)了 List 和 Collection 披诗。從作用上來(lái)看，Vector 和 ArrayList 很相似钻趋，都是內(nèi)部維護(hù)了一個(gè)可以動(dòng)態(tài)變換長(zhǎng)度的數(shù)組。
- 但是他們的擴(kuò)容機(jī)制卻不相同。對(duì)于 Vector 的源碼大部分都和 ArrayList 差不多鞭铆，這里簡(jiǎn)單看下 Vector 的構(gòu)造函數(shù)，以及 Vector 的擴(kuò)容機(jī)制焦影。
Java容器類(lèi)框架分析(1)ArrayList源碼分析
1.1 構(gòu)造函數(shù)
- Vector 的構(gòu)造函數(shù)可以指定內(nèi)部數(shù)組的初始容量和擴(kuò)容系數(shù)车遂，如果不指定初始容量默認(rèn)初始容量為 10，但是不同于 ArrayList 的是它在創(chuàng)建的時(shí)候就分配了容量為10的內(nèi)存空間斯辰，而 ArrayList 則是在第一次調(diào)用 add 的時(shí)候才生成一個(gè)容量為 10 數(shù)組舶担。
public Vector() {
this(10);//創(chuàng)建一個(gè)容量為 10 的數(shù)組。
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
// 此方法在 JDK 1.2 后添加
public Vector(Collection<? extends E> c) {
elementData = c.toArray();//創(chuàng)建與參數(shù)集合長(zhǎng)度相同的數(shù)組
elementCount = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
1..2 擴(kuò)容機(jī)制
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 如果我們沒(méi)有指定擴(kuò)容系數(shù)彬呻，那么 newCapacity = 2 * oldCapacity
// 如果我們指定了擴(kuò)容系數(shù)衣陶，那么每次增加指定的容量
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 由上邊的方法結(jié)合我們的構(gòu)造函數(shù)柄瑰，我們便可知道 Vector 的需要擴(kuò)容的時(shí)候，首先會(huì)判斷 capacityIncrement 即在構(gòu)造的 Vector 的時(shí)候時(shí)候指定了擴(kuò)容系數(shù)剪况，如果指定了則按照指定的系數(shù)來(lái)擴(kuò)大容量教沾，擴(kuò)大后新的容量為 oldCapacity + capacityIncrement，如果沒(méi)有指定capacityIncrement的大小译断，則默認(rèn)擴(kuò)大原來(lái)容量的一倍授翻，這點(diǎn)不同于 ArrayList 的 0.5 倍長(zhǎng)度。
- 對(duì)于 Vector 與 ArrayList 的區(qū)別最重要的一點(diǎn)是 Vector所有的訪問(wèn)內(nèi)部數(shù)組的方法都帶有synchronized孙咪，這意味著 Vector 是線程安全的堪唐，而ArrayList 并沒(méi)有這樣的特性。
1.3 elements()
- 對(duì)于 Vector 而言该贾，除了 for 循環(huán)羔杨，高級(jí) for 循環(huán)，迭代的迭代方法外杨蛋，還可以調(diào)用 elements() 返回一個(gè) Enumeration 兜材。
- Enumeration 是一個(gè)接口，其內(nèi)部只有兩個(gè)方法hasMoreElements 和 nextElement逞力，看上去和迭代器很相似曙寡，但是并沒(méi)迭代器的 add remove，只能作用于遍歷寇荧。
public interface Enumeration<E> {
boolean hasMoreElements();
E nextElement();
}
// Vector 的 elements 方法举庶。
public Enumeration<E> elements() {
return new Enumeration<E>() {
int count = 0;
public boolean hasMoreElements() {
return count < elementCount;
}
public E nextElement() {
synchronized (Vector.this) {
if (count < elementCount) {
return elementData(count++);
}
}
throw new NoSuchElementException("Vector Enumeration");
}
};
}
使用方法
Vector<String> vector = new Vector<>();
vector.add("1");
vector.add("2");
vector.add("3");
Enumeration<String> elements = vector.elements();
while (elements.hasMoreElements()){
System.out.print(elements.nextElement() + " ");
}
事實(shí)上烈评，這個(gè)接口也是很古老的一個(gè)接口琳轿，JDK 為了適配老版本，我們可以調(diào)用類(lèi)似 Enumeration<String> enumeration = Collections.enumeration(list); 來(lái)返回一個(gè)Enumeration 硕糊。其原理就是調(diào)用對(duì)應(yīng)的迭代器的方法峦嗤。
// Collections.enumeration 方法
public static <T> Enumeration<T> enumeration(final Collection<T> c) {
return new Enumeration<T>() {
// 構(gòu)造對(duì)應(yīng)的集合的迭代器
private final Iterator<T> i = c.iterator();
// 調(diào)用迭代器的 hasNext
public boolean hasMoreElements() {
return i.hasNext();
}
// 調(diào)用迭代器的 next
public T nextElement() {
return i.next();
}
};
}
1.4 Vector 與 ArrayList 的比較
- Vector 與 ArrayList 底層都是數(shù)組數(shù)據(jù)結(jié)構(gòu)蕊唐，都維護(hù)著一個(gè)動(dòng)態(tài)長(zhǎng)度的數(shù)組。
- Vector 對(duì)擴(kuò)容機(jī)制在沒(méi)有通過(guò)構(gòu)造指定擴(kuò)大系數(shù)的時(shí)候烁设，默認(rèn)增長(zhǎng)現(xiàn)有數(shù)組長(zhǎng)度的一倍替梨。而 ArrayList 則是擴(kuò)大現(xiàn)有數(shù)組長(zhǎng)度的一半長(zhǎng)度。
- Vector 是線程安全的, 而 ArrayList 不是線程安全的装黑，在不涉及多線程操作的時(shí)候 ArrayList 要比 Vector 效率高
- 對(duì)于 Vector 而言副瀑，除了 for 循環(huán)，高級(jí) for 循環(huán)恋谭，迭代器的迭代方法外糠睡，還可以調(diào)用 elements() 返回一個(gè) Enumeration 來(lái)遍歷內(nèi)部元素。
2 Stack 介紹
由開(kāi)始的繼承體系可以知道 Stack 繼承自 Vector疚颊，也就是 Stack 擁有 Vector 所有的增刪改查方法铜幽。
我們先來(lái)看下棧的定義：
棧（stack）又名堆棧滞谢，它是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算除抛。這一端被稱(chēng)為棧頂狮杨，相對(duì)地，把另一端稱(chēng)為棧底到忽。向一個(gè)棧插入新元素又稱(chēng)作進(jìn)棧橄教、入棧或壓棧喘漏，它是把新元素放到棧頂元素的上面护蝶，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱(chēng)作出楐媛酰或退棧持灰，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素负饲。
簡(jiǎn)單來(lái)說(shuō)堤魁，棧這種數(shù)據(jù)結(jié)構(gòu)有一個(gè)約定，就是向棧中添加元素和從棧中取出元素只允許在棧頂進(jìn)行返十，而且先入棧的元素總是后取出妥泉。 我們可以用數(shù)組和鏈表來(lái)實(shí)現(xiàn)棧的這種數(shù)據(jù)結(jié)構(gòu)的操作。
一般來(lái)說(shuō)對(duì)于棧有一下幾種操作：
- push 入棧
- pop 出棧
- peek 查詢棧頂
- empty 棧是否為空
Java 中的 Stack 容器是以數(shù)組為底層結(jié)構(gòu)來(lái)實(shí)現(xiàn)棧的操作的洞坑，通過(guò)調(diào)用 Vector 對(duì)應(yīng)的添加刪除方法來(lái)實(shí)現(xiàn)入棧出站操作盲链。
// 入棧
public E push(E item) {
addElement(item);//調(diào)用 Vector 定義的 addElement 方法
return item;
}
// 出棧
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);//調(diào)用 Vector 定義的 removeElementAt 數(shù)組末尾的元素的方法
return obj;
}
// 查詢棧頂元素
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);//查詢數(shù)組最后一個(gè)元素。
}
上邊簡(jiǎn)單介紹了 Java 容器中的 Stack 實(shí)現(xiàn)迟杂，但是事實(shí)上官方并不推薦在使用這些陳舊的集合容器類(lèi)刽沾。對(duì)于棧從數(shù)據(jù)結(jié)構(gòu)上而言，相對(duì)于線性表排拷，其實(shí)現(xiàn)也存在侧漓，順序存儲(chǔ)（數(shù)組），非連續(xù)存儲(chǔ)（鏈表）的實(shí)現(xiàn)方法攻泼。而我們文章最后看到的 Java容器類(lèi)框架分析(2)LinkedList源碼分析是可以取代 Stack來(lái)進(jìn)行棧操作的。
public class SimpleStack<E> {
//默認(rèn)容量
private static final int DEFAULT_CAPACITY = 10;
//棧中存放元素的數(shù)組
private Object[] elements;
//棧中元素的個(gè)數(shù)
private int size = 0;
//棧頂指針
private int top;
public SimpleStack() {
this(DEFAULT_CAPACITY);
}
public SimpleStack(int initialCapacity) {
elements = new Object[initialCapacity];
top = -1;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
@SuppressWarnings("unchecked")
public E pop() throws Exception {
if (isEmpty()) {
throw new EmptyStackException();
}
E element = (E) elements[top];
elements[top--] = null;
size--;
return element;
}
@SuppressWarnings("unchecked")
public E peek() throws Exception {
if (isEmpty()) {
throw new Exception("當(dāng)前棧為空");
}
return (E) elements[top];
}
public void push(E element) throws Exception {
//添加之前確保容量是否滿足條件
ensureCapacity(size + 1);
elements[size++] = element;
top++;
}
private void ensureCapacity(int minSize) {
if (minSize - elements.length > 0) {
grow();
}
}
private void grow() {
int oldLength = elements.length;
// 更新容量操作 擴(kuò)充為原來(lái)的1.5倍 這里也可以選擇其他方案
int newLength = oldLength + (oldLength >> 1);
elements = Arrays.copyOf(elements, newLength);
}
}
3 同步 vs 非同步
- 對(duì)于 Vector 和 Stack 從源碼上他們?cè)趯?duì)應(yīng)的增刪改查方法上都使用 synchronized關(guān)鍵字修飾了方法鉴象，這也就代表這個(gè)方法是同步方法忙菠，線程安全的。
- 不過(guò)我們?cè)诮榻B ArrayList 和 LinkedList 的時(shí)候提及到了我們可以使用Collections 的靜態(tài)方法纺弊，將一個(gè) List 轉(zhuǎn)化為線程同步的 List：
List<Integer> synchronizedArrayList = Collections.synchronizedList(arrayList);
List<Integer> synchronizedLinkedList = Collections.synchronizedList(linkedList);
那么這里又有一道面試題是這樣問(wèn)的：
請(qǐng)簡(jiǎn)述一下 Vector 和 SynchronizedList 區(qū)別牛欢，
SynchronizedList 即Collections.synchronizedList(arrayList); 后生成的List 類(lèi)型，它本身是 Collections 一個(gè)內(nèi)部類(lèi)淆游。
static class SynchronizedList<E>
extends SynchronizedCollection<E>
implements List<E> {
private static final long serialVersionUID = -7754090372962971524L;
final List<E> list;
SynchronizedList(List<E> list) {
super(list);
this.list = list;
}
SynchronizedList(List<E> list, Object mutex) {
super(list, mutex);
this.list = list;
}
.....
}
對(duì)于 SynchronizedList 構(gòu)造可以看到有一個(gè) Object 的參數(shù)傍睹，但是看到 mutex 這個(gè)單詞應(yīng)該就明白了這個(gè)參數(shù)的含義了隔盛，就是同步鎖，其實(shí)我們點(diǎn)擊 super 方法可以看到拾稳，單個(gè)參數(shù)的構(gòu)造函數(shù)鎖就是其對(duì)象自身吮炕。
SynchronizedCollection(Collection<E> c) {
this.c = Objects.requireNonNull(c);
mutex = this;
}
SynchronizedCollection(Collection<E> c, Object mutex) {
this.c = Objects.requireNonNull(c);
this.mutex = Objects.requireNonNull(mutex);
}
接下來(lái)我們看看增刪改查方法吧：
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
public int indexOf(Object o) {
synchronized (mutex) {return list.indexOf(o);}
}
public int lastIndexOf(Object o) {
synchronized (mutex) {return list.lastIndexOf(o);}
}
public boolean addAll(int index, Collection<? extends E> c) {
synchronized (mutex) {return list.addAll(index, c);}
}
//注意這里沒(méi)加 synchronized（mutex）
public ListIterator<E> listIterator() {
return list.listIterator(); // Must be manually synched by user
}
public ListIterator<E> listIterator(int index) {
return list.listIterator(index); // Must be manually synched by user
}
可以很清楚的看到，讓一個(gè)集合變成線程安全的访得，Collocations 只是包裝了參數(shù)集合的增刪改查方法龙亲，加了同步的限制。與 Vector 相比可以看出來(lái)悍抑，兩者第一個(gè)區(qū)別在于是同步方法還是同步代碼塊鳄炉，對(duì)于這兩個(gè)區(qū)別如下：
- 同步代碼塊在鎖定的范圍上可能比同步方法要小，一般來(lái)說(shuō)鎖的范圍大小和性能是成反比的搜骡。
- 同步塊可以更加精確的控制鎖的作用域（鎖的作用域就是從鎖被獲取到其被釋放的時(shí)間）拂盯，同步方法的鎖的作用域就是整個(gè)方法。
由上述兩個(gè)方法看出來(lái)记靡，``Collections.synchronizedList(arrayList);生成的同步集合看起來(lái)更高效一些谈竿，其實(shí)這種差異在 Vector 和 ArrayList上體現(xiàn)的很不明顯，因?yàn)槠?add 方法內(nèi)部實(shí)現(xiàn)大致相同簸呈。而從構(gòu)造參數(shù)上來(lái)看Vector不能像SynchronizedList` 一樣指定加鎖對(duì)象榕订。
而我們也看到了 SynchronizedList 并沒(méi)有給迭代器進(jìn)行加鎖，但是翻看 Vector 的迭代器方法確實(shí)枷鎖的蜕便，所以我們?cè)谑褂肧ynchronizedList的的迭代器的時(shí)候需要手動(dòng)做同步處理：
synchronized (list) {
Iterator i = list.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}
至此我們可以總結(jié)出 SynchronizedList與 Vector的三點(diǎn)差異：
- SynchronizedList 作為一個(gè)包裝類(lèi)劫恒，有很好的擴(kuò)展和兼容功能〗蜗伲可以將所有的 List 的子類(lèi)轉(zhuǎn)成線程安全的類(lèi)两嘴。
- 使用 SynchronizedList 的獲取迭代器，進(jìn)行遍歷時(shí)要手動(dòng)進(jìn)行同步處理族壳，而 Vector 不需要憔辫。
- SynchronizedList 可以通過(guò)參數(shù)指定鎖定的對(duì)象，而 Vector 只能是對(duì)象本身仿荆。
