今天先看看有關(guān)集合的源碼.
既然是看集合那就從集合的最根接口Collection接口看起;
本人使用的 IntelliJ IDEA,所以也免去的導(dǎo)入源碼的過(guò)程,直接進(jìn)入Collection接口開搞.
Collection接口的一些注釋和實(shí)現(xiàn)結(jié)構(gòu)
簡(jiǎn)單的讀一下注釋.大意如下:
這是一個(gè)集合層次的根節(jié)點(diǎn),一個(gè)集合包含了一組對(duì)象,稱為元素.一些集合允許復(fù)制,一些不允許,一些是有序的,一些是無(wú)須的,JDK不提供任何直接的對(duì)于此接口的實(shí):提供了一些特殊的子接口像Set和List.
看Collection的實(shí)現(xiàn),熟悉的有List,Set,Queue基本的,咱們一個(gè)一個(gè)來(lái)看.都不放過(guò).
先看第一個(gè):
SynchronizedCollection 看名字同步的集合,
進(jìn)入SynchronizedCollection類內(nèi)部,發(fā)現(xiàn)他是一個(gè)內(nèi)部類,是在Collections類下的內(nèi)部類
看一下java對(duì)這個(gè)類的描述
/**
* Returns a synchronized (thread-safe) collection backed by the specified
* collection. In order to guarantee serial access, it is critical that
* <strong>all</strong> access to the backing collection is accomplished
* through the returned collection.<p>
*
* It is imperative that the user manually synchronize on the returned
* collection when iterating over it:
* <pre>
* Collection c = Collections.synchronizedCollection(myCollection);
* ...
* synchronized (c) {
* Iterator i = c.iterator(); // Must be in the synchronized block
* while (i.hasNext())
* foo(i.next());
* }
* </pre>
* Failure to follow this advice may result in non-deterministic behavior.
*
* <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt>
* and <tt>equals</tt> operations through to the backing collection, but
* relies on <tt>Object</tt>'s equals and hashCode methods. This is
* necessary to preserve the contracts of these operations in the case
* that the backing collection is a set or a list.<p>
*
* The returned collection will be serializable if the specified collection
* is serializable.
返回一個(gè)由指定集合支持的同步的(線程安全)集合.為了保證連續(xù)的數(shù)據(jù),重要的是，所有對(duì)后臺(tái)集合的訪問(wèn)是通過(guò)返回的集合完成的
當(dāng)遍歷這個(gè)集合的時(shí)候,用戶在返回的集合上手動(dòng)同步是必要的.
基本上SynchronizedCollection這個(gè)類的作用是創(chuàng)建一個(gè)線程安全的集合.
我們可以看到一個(gè)參數(shù)為Collection返回值為Collection的靜態(tài)方法synchronizedCollection
所以我們?cè)诔绦蛑兄苯诱{(diào)用Collections類的synchronizedCollection方法來(lái)獲取一個(gè)線程安全的集合
Collection collection= Collections.synchronizedCollection(new ArrayList<String>());
在Collections類中還可以看到其他類似的方法:
public static <T> Set<T> synchronizedSet(Set<T> s) {
return new SynchronizedSet<>(s);
}
獲取一個(gè)線程安全的Set集合.
public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
return new SynchronizedSortedSet<>(s);
}
獲取一個(gè)線程安全的SortSet.
public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<>(list) :
new SynchronizedList<>(list));
}
獲取一個(gè)線程安全的List集合
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
return new SynchronizedMap<>(m);
}
獲取一個(gè)線程安全的map等等.
哪為什么這些獲取的就是線程安全的集合呢,我們來(lái)看一下他的方法:
我們可以看到,他在所有方法里都加了synchronized關(guān)鍵字,而對(duì)應(yīng)的鎖,如果我們?cè)趧?chuàng)建集合的時(shí)候沒(méi)有傳入鎖對(duì)象,那么就是它本身,如果傳入了鎖對(duì)象就是這個(gè)對(duì)象.
下面重點(diǎn)研究一下List,Set,和Queue
一. List接口
接口中定義了一些操作集合的常用方法
下面看一下他的繼承關(guān)系
可以看到有許多類或者接口實(shí)現(xiàn)了List接口
我們主要看一下幾個(gè):ArrayList,Vector,LinkedList
(1)ArrayList
進(jìn)入ArrayList類中首先可以看到定義的一些常量和變量
DEFAULT_CAPACITY ArrayList默認(rèn)容量為10;
EMPTY_ELEMENTDATA 在調(diào)用無(wú)參構(gòu)造的時(shí)候默認(rèn)給的空數(shù)組
elementData 真正保存數(shù)據(jù)的數(shù)組
size 就和中真正元素的個(gè)數(shù)
構(gòu)造方法有三個(gè)
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
傳入一個(gè)int數(shù)定義一個(gè)數(shù)組
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
無(wú)參構(gòu)造默認(rèn)生成一個(gè)空的數(shù)組
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
傳入一個(gè)集合,將傳入集合的值copy到數(shù)組中,
下面主要看看ArrayList的主要方法;
1 add方法:add有兩個(gè)重載;
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
直接傳入一個(gè)元素,首先調(diào)用ensureCapacityInternal(size+1)這個(gè)方法,我們看一下這個(gè)方法;
//
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
判斷是否為一個(gè)空的數(shù)組,如果為空的數(shù)組那么將minCapacity賦值為默認(rèn)容量和元素個(gè)數(shù)加1中的最大的數(shù),然后執(zhí)行ensureExplicitCapacity(minCapacity);在ensureExplicitCapacity中首先判斷minCapacity和當(dāng)前集合長(zhǎng)度進(jìn)行比較(正常情況下都是minCapacity大),然后執(zhí)行g(shù)row(minCapacity);這個(gè)方法就是list擴(kuò)容的精髓了;請(qǐng)看:
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
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;
}
可以看到,新容量是舊容量的1.5倍,
而且在add方法中并沒(méi)有看到對(duì)插入元素的檢驗(yàn),所以ArrayList是一個(gè)有序可重復(fù)的集合,內(nèi)部實(shí)現(xiàn)了可擴(kuò)容的數(shù)組結(jié)構(gòu),再添加時(shí),調(diào)用add(E e)方法默認(rèn)是在末尾插入,這樣效率并沒(méi)有對(duì)什么影響,二如果調(diào)用add(int index, E element)這個(gè)方法在結(jié)合頭部插入元素時(shí),由于ArrayList內(nèi)部使用數(shù)組,則已有元素全部需要向后移動(dòng)一位,這樣就大大影響了效率;
2 remove 方法:remove方法也有兩個(gè)重載
(1)
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
(2)
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
可以看到,一個(gè)是按照索引去刪除元素,一個(gè)是按照元素去刪除,
按照索引去刪除最后會(huì)返回被刪除的那個(gè)元素,
按照元素刪除只會(huì)返回true或者false;
按照元素刪除最后調(diào)用了fastRemove
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
其實(shí)最后都是通過(guò)索引去刪除元素;
好ArrayList這部分就先寫這么多,之后會(huì)繼續(xù)進(jìn)行集合接口的源碼閱讀記錄.
