JAVA有幾種常用的數(shù)據(jù)結構，主要是繼承Collection和Map這兩個主要接口的數(shù)據(jù)實現(xiàn)類
在jdk1.7和jdk1.8中，實現(xiàn)會有些許不同，之后會在注解中添加兩版本區(qū)別
下面分別介紹幾個常用的數(shù)據(jù)結構(按照繼承的接口分為兩類)，以下代碼截取自基于JAVA8的android SDK 28
Collection
Collection是最基本的集合接口，一個Collection代表一組Object，即Collection的元素Elements。一些Collection允許相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接繼承自Collection的類，Java SDK提供的類都是繼承自Collection的“子接口”如List和Set。
論Collection的實際類型如何，它都支持一個iterator()的方法，該方法返回一個迭代子，使用該迭代子即可逐一訪問Collection中每一個元素。典型的用法如下：
Iterator it = collection.iterator(); // 獲得一個迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一個元素
}
由Collection接口派生的兩個接口是List和Set。
List
List是有序的Collection，使用此接口能夠精確的控制每個元素插入的位置。用戶能夠使用索引（元素在List中的位置，類似于數(shù)組下標）來訪問List中的元素，這類似于Java的數(shù)組，與之后介紹的Set不一樣，List允許有相同的元素。實現(xiàn)List接口的常用類有LinkedList，ArrayList，Vector和Stack。
LinkedList（JAVA7/8中基本沒有改動）
雙向鏈表結構，適用于亂序插入、刪除。但指定序列操作性能不如ArrayList。
LinkedList的父類接口，以及內部有幾個主要的變量，如下：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
transient int size = 0;//鏈表尺寸
transient Node<E> first;//鏈表第一個節(jié)點指針
transient Node<E> last;//鏈表末尾節(jié)點指針
##注transient關鍵字：將不需要序列化的屬性前添加關鍵字transient，序列化對象的時候，這個屬性就不會被序列化。
注：實現(xiàn)了Cloneable接口，即實現(xiàn)clone()函數(shù)。代表能被克隆。
數(shù)據(jù)類Node的結構
private static class Node<E> {
E item;//節(jié)點數(shù)據(jù)
Node<E> next;//當前節(jié)點下一個節(jié)點
Node<E> prev;//當前節(jié)點上一個節(jié)點
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
構造方法
public LinkedList() {
}
//構造一個包含指定元素的列表
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
//可參考下方的addAll解析，就是在size(此時size = 0)后加入指定元素的列表的數(shù)據(jù)
return addAll(size, c);
}
以下是使用時的常用方法實現(xiàn)代碼以及分析:
注：modCount是父類AbstractList中定義的一個int型的屬性記錄了ArrayList結構性變化的次數(shù)。List中add()、remove()、addAll()、removeRange()及clear()這些方法每調用一次，modCount的值就加1。
add()/addLast(E)/add(int,E)
add(E)/addLast(E):將指定的元素添加到列表的末尾。
public boolean add(E e) {
linkLast(e);
return true;
}
public void addLast(E e) {
linkLast(e);
}
void linkLast(E e) {
final Node<E> l = last;//獲取末尾節(jié)點
final Node<E> newNode = new Node<>(l, e, null);//將傳入的數(shù)據(jù)封裝成 Node
last = newNode;
if (l == null)//判斷是否存在末尾節(jié)點
first = newNode;//不存在則說明鏈表為空，直接將節(jié)點賦值為 newNode
else
l.next = newNode;//否則將末尾節(jié)點的next賦值為 newNode
size++;
modCount++;
}
add(int,E):在列表的指定位置插入指定的元素。
public void add(int index, E element) {
//判斷index下標是否在鏈表范圍內(0=<index<=size),超出則拋出IndexOutOfBoundsException
checkPositionIndex(index);
if (index == size)
linkLast(element); //此時相當于插入末尾，與add(E)方法一致
else
linkBefore(element, node(index));//重點看這個方法，插入鏈表中間
}
/**
* 在節(jié)點index前插入新節(jié)點
*/
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;//獲得index位置節(jié)點的前置節(jié)點
//創(chuàng)建新節(jié)點，前置節(jié)點為index位置節(jié)點的前置節(jié)點，后置節(jié)點為index位置節(jié)點
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;//改變index位置節(jié)點的前置節(jié)點為新節(jié)點
if (pred == null) //判斷index位置節(jié)點的前置節(jié)點是否為空
first = newNode; //為空代表插在鏈表頭
else
pred.next = newNode; //不為空將節(jié)點的后置節(jié)點設置為新節(jié)點
size++;
modCount++;
}
remove(int)
remove(int)：刪除列表中指定位置的元素。
public E remove(int index) {
/**判斷index下標是否在鏈表索引范圍內(0=<index<size),超出則拋出IndexOutOfBoundsException**/
checkElementIndex(index);
return unlink(node(index));//node(index)獲取到了index下表的Node
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//判斷前置節(jié)點是否為null。
if (prev == null) {
first = next;//為空則代表是第一個節(jié)點，將后置節(jié)點設置為首位節(jié)點
} else {
//不為空則代表是中間節(jié)點，將前置節(jié)點的后置節(jié)點設置為自己的后直節(jié)點，斷開自己與前置節(jié)點的鏈接。
prev.next = next
x.prev = null;
}
//同樣的方式判斷后置
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;//當前節(jié)點的數(shù)據(jù)置null
size--;
modCount++;
return element;
}
get(int)
get(int):Returns the element at the specified position in this list.
public E get(int index){
/**判斷index下標是否在鏈表索引范圍內(0=<index<size),超出則拋出IndexOutOfBoundsException**/
checkElementIndex(index);
return node(index).item;
}
/**
* 返回指定元素索引處的(非空)節(jié)點。
*/
Node<E> node(int index) {
/**size >> 1相當于size/2**/
if (index < (size >> 1)) {
/**如果獲取index小于size/2，則從首位節(jié)點開始循環(huán)獲取**/
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
/**如果獲取index大于size/2，則從末尾節(jié)點開始循環(huán)獲取**/
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
set(int,E)
set(int,E):將列表中指定位置的元素替換為指定的元素。
public E set(int index, E element) {
/**判斷index下標是否在鏈表索引范圍內(0=<index<size),超出則拋出IndexOutOfBoundsException**/
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
addAll(Collection<? extends E>)/addAll(int , Collection<? extends E>)
addAll(Collection<? extends E>)/addAll(int , Collection<? extends E>)
：將指定集合中的所有元素添加到末尾/index節(jié)點之后
//本質上是調用同個方法
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);//傳入size,直接在末尾插入
}
public boolean addAll(int index, Collection<? extends E> c) {
//判斷插入位置index是否超出范圍
checkPositionIndex(index);
//將集合轉成數(shù)組
Object[] a = c.toArray();
int numNew = a.length;
//集合數(shù)為0，等于沒有數(shù)據(jù)
if (numNew == 0)
return false;
//predpred是插入節(jié)點集合的前置節(jié)點
//succ是插入位置節(jié)點，用于之后判斷是中間插入還是末尾插入
Node<E> pred, succ;
if (index == size) {
//index等于鏈表尺寸，代表是末尾插入
succ = null;
pred = last;
} else {
//中間插入，保留插入位置的節(jié)點
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
//前置節(jié)點為null,相當于插入鏈表頭
first = newNode;
else
//不為空，則從插入位置之后插入
pred.next = newNode;
pred = newNode;
}
//插入完成后，判斷插入位置succ
if (succ == null) {
//succ為null,代表末尾插入
last = pred;
} else {
//succ不為null,代表中間插入，設置插入全部數(shù)據(jù)后的最后一個數(shù)據(jù)節(jié)點后置節(jié)點為succ
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
clear()
clear():從列表中刪除所有元素。
public void clear() {
//將鏈表中間的節(jié)點內容都設置為null
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
//將首位節(jié)點和末尾節(jié)點設置為null，尺寸設置為0
first = last = null;
size = 0;
modCount++;
}
還有一些其他方法，但都是基于以上方法的邏輯，就不介紹了。
ArrayList（以下代碼基于JAVA8）
ArrayList是動態(tài)數(shù)組，底層就是一個數(shù)組, 因此按序查找快, 亂序插入, 刪除因為涉及到后面元素移位所以性能慢。
首先需要介紹一個ArrayList方法內常用的一個方法Arrays.copyOf(T[],int)，作用是復制數(shù)組，在ArrayList初始化，擴容時都會用到，代碼如下
//第一個參數(shù)是原始數(shù)組，第二個是返回數(shù)組的長度
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
////第一個參數(shù)是原始數(shù)組，第二個是返回數(shù)組的長度，第三個返回數(shù)組的類
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
//判斷返回數(shù)組的類是否是Object,是的話就創(chuàng)建一個Object數(shù)組，不是的話就創(chuàng)建一個特定類的數(shù)組
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
//將original從第0個下標開始的Math.min(original.length, newLength)的數(shù)據(jù)拷貝至copy數(shù)組的第0個下標
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
ArrayList的父類接口，以及內部有幾個主要的變量，如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
private static final int DEFAULT_CAPACITY = 10;//默認初始容量
private static final Object[] EMPTY_ELEMENTDATA = {};//用于空實例的共享空數(shù)組實例。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;//存儲數(shù)組列表元素的數(shù)組緩沖區(qū)。
private int size;//實際元素個數(shù)
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//要分配的數(shù)組的最大大小，超出的話可能會導致OutOfMemoryError
EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA都是空數(shù)組，區(qū)別主要是為了判斷是使用了哪種構造函數(shù)，無參構造創(chuàng)建時使用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，有參構造創(chuàng)建時，當initialCapacity == 0使用的是EMPTY_ELEMENTDATA。以便確認如何擴容(下面會分析)。
注：RandmoAccess接口，即提供了隨機訪問功能。
構造方法
構造方法:ArrayList構造方法分為三個：
//置為DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空列表，之后會在第一次添加元素時擴容成10容量。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 按照集合的迭代器返回元素的順序構造一個包含指定集合元素的列表。
*/
public ArrayList(Collection<? extends E> c) {
//將集合轉成數(shù)組直接賦值給elementData
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
- 空參構造方法：將elementData設置為DEFAULTCAPACITY_EMPTY_ELEMENTDATA，最后會初始化成一個容量為10的空數(shù)組；
- 帶int參數(shù)的構造方法：將elementData實例化成傳入的初始容量大小的數(shù)組，若傳入的值為0，則將elementData設置為EMPTY_ELEMENTDATA；
- 帶Collection參數(shù)的構造方法：按照傳入的集合構造一個包含指定元素的列表，r將集合轉成數(shù)組直接賦值給elementData，將元素個數(shù)賦值給size，若元素個數(shù)不為0，最后將elementData轉換成Object[]類的數(shù)組，若元素個數(shù)為0，則將elementData置為EMPTY_ELEMENTDATA；
總的來說：
- 無參構造:elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- 有參構造:
- initialCapacity==0, elementData = EMPTY_ELEMENTDATA
- initialCapacity > 0, elementData = new Object[initialCapacity];
以下是使用時的常用方法實現(xiàn)代碼以及分析:
add(E)/add(int,E)
add(E):將指定的元素添加到列表的末尾，調用過程如下。
public boolean add(E e) {
//判斷增加一個元素后的容量是否超出當前數(shù)組容量，超過擴容，不超過則不變
ensureCapacityInternal(size + 1); // Increments modCount!!
//將當前數(shù)組最后一個數(shù)據(jù)后的位置賦值為e
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//判斷當前elementData是否等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//將所需大小設置成DEFAULT_CAPACITY(10)和minCapacity中比較大的值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果所需的最小容量大于當前elementData的長度
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//根據(jù)minCapacity(需要的最小容量)擴容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//獲得當前數(shù)組長度
int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量為原容量的1.5倍
if (newCapacity - minCapacity < 0)
//如果新容量仍小于所需最小容量，直接將新容量置為需要的最小容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//判斷當前容量是否超出可分配的最大容量，超出則設置新容量為
//Integer.MAX_VALUE，保證數(shù)組容量不超過Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
//根據(jù)新容量創(chuàng)建新的數(shù)組賦值給elementData，此時minCapacity通常接近size
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//Integer.MAX_VALUE = MAX_ARRAY_SIZE + 8;
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add(int,E):在列表中的指定位置插入指定的元素。將當前位于該位置的元素(如果有的話)和隨后的元素向右移動(下標加1)。
public void add(int index, E element) {
//插入位置超過當前數(shù)據(jù)尺寸或者插入位置小于0
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//判斷插入數(shù)據(jù)后的數(shù)據(jù)是否超出數(shù)組范圍，超出則擴容，不超出則不變
ensureCapacityInternal(size + 1); // Increments modCount!!
//將elementData數(shù)組從index以及之后的數(shù)據(jù)拷貝至index+1的位置
//相當于騰出index這個下標的位置，用于存放插入的數(shù)據(jù)element
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
remove(int)
remove(int)::刪除列表中指定位置的元素。將所有后續(xù)元素向左移動(從它們的下標減去1)。
public E remove(int index) {
//判斷是否超出范圍
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
//獲得刪除位置的數(shù)據(jù)
E oldValue = (E) elementData[index];
//刪除后需要移動的數(shù)據(jù)數(shù)量。
//例共10個數(shù)據(jù)，刪除第5個數(shù)據(jù)(下標index = 4)，
//那么需要移動的數(shù)據(jù)是第五個數(shù)據(jù)后的數(shù)據(jù)。也就是10- 4 -1 =5 個數(shù)據(jù)
int numMoved = size - index - 1;
//需要移動的數(shù)據(jù)大于0
if (numMoved > 0)
//將elementData數(shù)組的第index+1位置開始的numMoved個數(shù)據(jù)復制到index(即數(shù)據(jù)往前移一位)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//最后一個數(shù)據(jù)置為null，同時size-1;
elementData[--size] = null; // clear to let GC do its work
//返回刪除的數(shù)據(jù)
return oldValue;
}
get(E)
get(E):返回列表中指定位置的元素。
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
set(int,E)
set(int,E):用指定的元素替換列表中指定位置的元素。
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
addAll(Collection<? extends E>)/addAll(int , Collection<? extends E>)
addAll(Collection<? extends E>):將指定集合中的所有元素追加到末尾
public boolean addAll(Collection<? extends E> c) {
//將集合轉成數(shù)組，并獲取數(shù)組長度
Object[] a = c.toArray();
int numNew = a.length;
//判斷追加后元素是否會超出數(shù)組范圍，超出則擴容
ensureCapacityInternal(size + numNew); // Increments modCount
//將追加數(shù)組a從0開始numNew(所有)數(shù)據(jù)拷貝至elementData的size下標后
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
//返回追加數(shù)組數(shù)據(jù)是否有數(shù)據(jù)
return numNew != 0;
}
addAll(int , Collection<? extends E>):將指定集合中的所有元素插入到此列表中，從指定位置開始。
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//將集合轉成數(shù)組，并獲取數(shù)組長度
Object[] a = c.toArray();
int numNew = a.length;
//判斷插入后元素是否會超出數(shù)組范圍，超出則擴容
ensureCapacityInternal(size + numNew); // Increments modCount
//插入數(shù)據(jù)后需要移動的數(shù)據(jù)量
int numMoved = size - index;
if (numMoved > 0)
//將elementData數(shù)組的第index位置開始的numMoved個數(shù)據(jù)復制到index+numNew(即數(shù)據(jù)往后移numNew位)，騰出numNew個位置存放插入元素
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//將a數(shù)組的數(shù)據(jù)復制至elementData剛才騰出的位置
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
clear()
clear():從列表中刪除所有元素。
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
ArrayList內部還有一個用于分頁查看的SubList的內部類，在subList(int,int)內部會調用，作用是返回一個List集合的其中一部分視圖。本質也是對elementData這個數(shù)組進行操作，這里就不展開。
注：在無參初始化ArrayList時，Java7是直接初始化10大小的數(shù)組，而JAVA8是初始化空數(shù)組，在第一次擴容時才按照10進行擴容
Vector
Vector是矢量隊列，與ArrayList不同，Vector中的操作是線程安全的。
Vector的父類接口，以及內部有幾個主要的變量，如下：
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
protected Object[] elementData;//存儲矢量組件的數(shù)組緩沖區(qū)。
protected int elementCount;//實際元素個數(shù)
protected int capacityIncrement;//capacityIncrement是每次Vector容量增加時的增量值，如果<=0，則每次擴容時容量翻倍，否則就擴容后容量就只是容量+增量。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//要分配的數(shù)組的最大大小，超出的話可能會導致OutOfMemoryError
構造方法
構造方法:Vector構造方法分為三個：
public Vector() {
//初始化容量為10
this(10);
}
public Vector(int initialCapacity) {
//初始化增量為0
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;
}
public Vector(Collection<? extends E> c) {
elementData = c.toArray();
elementCount = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
前三個構造方法本質是調用一個方法：初始化一個特定容量的數(shù)組，初始化特定增量值，具體的初始化參數(shù)看源碼；
帶Collection參數(shù)的構造方法：按照傳入的集合構造一個包含指定元素的列表，r將集合轉成數(shù)組直接賦值給elementData，將元素個數(shù)賦值給elementCount，最后將elementData轉換成Object[]類的數(shù)組；
add(E)/add(int,E)
add(E):將指定的元素添加到Vector的末尾。synchronized方法，線程安全。
public synchronized boolean add(E e) {
modCount++;
//容量判斷，容量不夠則擴容，不然則不變
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//如果設定的capacityIncrement增量大于0，則新容量為舊容量+增量，否則為雙倍舊容量
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
//判斷新容量是否大于所需的最小容量，小于則新容量改為minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判斷新容量是否超出
if (newCapacity - MAX_ARRAY_SIZE > 0)
//判斷當前容量是否超出可分配的最大容量，超出則設置新容量為
//Integer.MAX_VALUE，保證數(shù)組容量不超過Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add(int,E)：在Vector的指定位置插入指定元素。該方法內部調用的方法有synchronized，所以也是線程安全的。
public void add(int index, E element) {
insertElementAt(element, index);
}
/**
* 在指定的{@code index}處將指定的對象作為這個向量中的組件插入。
*這個向量中的每個索引值大于或等于指定的{@code index}的組件向上移動，使其索引值比之前的值大1。
*/
public synchronized void insertElementAt(E obj, int index) {
modCount++;
//判斷插入位置是否超出范圍
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
//容量判斷，容量不夠則擴容，不然則不變
ensureCapacityHelper(elementCount + 1);
//騰出數(shù)組中index下標位置
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
//將obj插入這個位置
elementData[index] = obj;
elementCount++;
}
remove(int)
remove(int):移除Vector中指定位置的元素。線程安全
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
//numMoved需要移動的數(shù)據(jù)數(shù)量
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
get(E)
get(E):返回該Vector中指定位置的元素。線程安全
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
set(int,E)
set(int,E):用指定的元素替換Vector中指定位置的元素。
public synchronized E set(int index, E element) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
addAll(Collection<? extends E>)/addAll(int , Collection<? extends E>)
addAll(Collection<? extends E>)：將指定集合中的所有元素追加到末尾，線程安全
public synchronized boolean addAll(Collection<? extends E> c) {
modCount++;
Object[] a = c.toArray();
int numNew = a.length;
//判斷容量
ensureCapacityHelper(elementCount + numNew);
//拷貝數(shù)據(jù)
System.arraycopy(a, 0, elementData, elementCount, numNew);
elementCount += numNew;
return numNew != 0;
}
addAll(int , Collection<? extends E>):將指定集合中的所有元素插入到Vector的指定位置。線程安全
public synchronized boolean addAll(int index, Collection<? extends E> c) {
modCount++;
if (index < 0 || index > elementCount)
throw new ArrayIndexOutOfBoundsException(index);
Object[] a = c.toArray();
int numNew = a.length;
//判斷容量
ensureCapacityHelper(elementCount + numNew);
//計算需要移動的元素數(shù)量
int numMoved = elementCount - index;
if (numMoved > 0)
//移動數(shù)據(jù)，騰出numNew個位置
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//拷貝數(shù)據(jù)至騰出的位置
System.arraycopy(a, 0, elementData, index, numNew);
elementCount += numNew;
return numNew != 0;
}
clear();
clear():從Vector中刪除所有元素。線程安全
public void clear() {
removeAllElements();
}
public synchronized void removeAllElements() {
modCount++;
// Let gc do its work
for (int i = 0; i < elementCount; i++)
elementData[i] = null;
elementCount = 0;
}
從代碼可以得知，其實Vector就是線程安全的ArrayList，方法內的代碼邏輯基本一致，就是多增加了synchronized關鍵字。同時因為Vector是同步的，當一個Iterator被創(chuàng)建而且正在被使用，另一個線程改變了Vector的狀態(tài)（例如，添加或刪除了一些元素），這時調用Iterator的方法時將拋出ConcurrentModificationException，因此必須捕獲該異常。
Stack
Stack繼承自Vector，實現(xiàn)一個后進先出的堆棧。Stack提供5個額外的方法使得Vector得以被當作堆棧使用。基本的push和pop方法，還有peek方法得到棧頂?shù)脑兀?strong>empty方法測試堆棧是否為空，search方法檢測一個元素在堆棧中的位置。Stack剛創(chuàng)建后是空棧。
構造方法
//創(chuàng)建一個空堆棧。
public Stack() {
}
push(E)
push(E):將E推到堆棧的頂部.
public E push(E item) {
addElement(item);
return item;
}
//Vector的方法
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
peek()
peek():查看堆棧頂部的對象，而不將其從堆棧中移除。
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
pop()
pop():刪除堆棧頂部的對象，并將該對象作為函數(shù)的值返回。
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
//Vector中的方法，移除指定位置的元素，并將之后的數(shù)據(jù)向前移動一位
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
}
empty()
empty():查看此堆棧是否為空。本質是看數(shù)據(jù)size是否為0
public boolean empty() {
return size() == 0;
}
search(Object)
search(Object):返回對象在堆棧中的基于1(即棧頂)的位置。
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
//Vector中的方法,返回Vector中指定元素最后一次出現(xiàn)的索引，如果vector中不包含該元素，則返回-1。
public synchronized int lastIndexOf(Object o) {
return lastIndexOf(o, elementCount-1);
}
//Vector中的方法,從index往回搜索值等于o的元素，返回Vector中指定元素最后一次出現(xiàn)的索引，如果沒有找到該元素則返回-1。
public synchronized int lastIndexOf(Object o, int index) {
if (index >= elementCount)
throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
if (o == null) {
for (int i = index; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = index; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Set
Set是一種不包含重復的元素的Collection，即任意的兩個元素e1和e2都有e1.equals(e2)=false，Set最多有一個null元素。
HashSet
HashSet這個類實現(xiàn)了Set集合，實際內部是使用HashMap的實例。HashSet中對重復元素的理解：和通常意義上的理解不太一樣！
兩個元素（對象）的hashCode返回值相同，并且equals返回值為true時（或者地址相同時），才稱這兩個元素是相同的。
HashSet的父類接口，以及內部有幾個主要的變量，如下：
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
private transient HashMap<E,Object> map;
//HashMap每個鍵值對應的value
private static final Object PRESENT = new Object();
可以看到HashSet內部其實是由HashMap組成，HashMap是一種存儲鍵值對的哈希表.
構造方法
//構造一個新的空集合;支持HashMap實例具有默認初始容量(16)和負載系數(shù)(0.75)。
public HashSet() {
map = new HashMap<>();
}
//構造一個包含指定元素的的新集合;創(chuàng)建的HashMap實例具有默認初始容量(16和c.size()/.75f(后者約為c.size()的1.3倍)兩者中的最大值)和負載系數(shù)(0.75)。
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
//構造一個新的空集合;內部構造指定初始容量的HashMap實例
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
//構造一個新的空集合;內部構造指定初始容量和指定負載系數(shù)的HashMap實例
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
//構造一個新的、空的鏈接哈希集。(這個包的私有構造函數(shù)僅由LinkedHashSet使用。)后備HashMap實例是具有指定初始容量和指定負載系數(shù)的LinkedHashMap。
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
add(E)/add(int,E)
add(E):如果E還不存在的話，將指定的元素添加到這個集合中。如果存在，則值不變直接返回false;
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
代碼可以看出
remove(int):如果指定的元素存在，則從集合中移除該元素。返回集合中是否包含此元素。
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
contains(Object)
contains(Object):返回HashSet中是否包含此元素
public boolean contains(Object o) {
return map.containsKey(o);
}
clear()
clear():從集合中刪除所有元素。
public void clear() {
map.clear();
}
總結
HashSet基本所有方法都是直接調用HashMap的方法，為了保證數(shù)據(jù)不重復，采用了存儲時用key存儲的方法，再HashMap中,key是不重復的，所以HashSet就不會有存儲重復的數(shù)據(jù)了。
HashSet是線程不同步的
TreeSet
TreeSet是一個有序的集合，它的作用是提供有序的Set集合。TreeSet的元素支持2種排序方式：自然排序或者根據(jù)提供的Comparator進行排序。
