今天先看看有關集合的源碼.
既然是看集合那就從集合的最根接口Collection接口看起;
本人使用的 IntelliJ IDEA,所以也免去的導入源碼的過程,直接進入Collection接口開搞.
Collection接口的一些注釋和實現結構
簡單的讀一下注釋.大意如下:
這是一個集合層次的根節(jié)點,一個集合包含了一組對象,稱為元素.一些集合允許復制,一些不允許,一些是有序的,一些是無須的,JDK不提供任何直接的對于此接口的實:提供了一些特殊的子接口像Set和List.
看Collection的實現,熟悉的有List,Set,Queue基本的,咱們一個一個來看.都不放過.
先看第一個:
SynchronizedCollection 看名字同步的集合,
進入SynchronizedCollection類內部,發(fā)現他是一個內部類,是在Collections類下的內部類
看一下java對這個類的描述
/**
* 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.
返回一個由指定集合支持的同步的(線程安全)集合.為了保證連續(xù)的數據,重要的是莫换，所有對后臺集合的訪問是通過返回的集合完成的
當遍歷這個集合的時候,用戶在返回的集合上手動同步是必要的.
基本上SynchronizedCollection這個類的作用是創(chuàng)建一個線程安全的集合.
我們可以看到一個參數為Collection返回值為Collection的靜態(tài)方法synchronizedCollection
所以我們在程序中直接調用Collections類的synchronizedCollection方法來獲取一個線程安全的集合
Collection collection= Collections.synchronizedCollection(new ArrayList<String>());
在Collections類中還可以看到其他類似的方法:
public static <T> Set<T> synchronizedSet(Set<T> s) {
return new SynchronizedSet<>(s);
}
獲取一個線程安全的Set集合.
public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
return new SynchronizedSortedSet<>(s);
}
獲取一個線程安全的SortSet.
public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<>(list) :
new SynchronizedList<>(list));
}
獲取一個線程安全的List集合
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
return new SynchronizedMap<>(m);
}
獲取一個線程安全的map等等.
哪為什么這些獲取的就是線程安全的集合呢,我們來看一下他的方法:
我們可以看到,他在所有方法里都加了synchronized關鍵字,而對應的鎖,如果我們在創(chuàng)建集合的時候沒有傳入鎖對象,那么就是它本身,如果傳入了鎖對象就是這個對象.
下面重點研究一下List,Set,和Queue
一. List接口
接口中定義了一些操作集合的常用方法
下面看一下他的繼承關系
可以看到有許多類或者接口實現了List接口
我們主要看一下幾個:ArrayList,Vector,LinkedList
(1)ArrayList
進入ArrayList類中首先可以看到定義的一些常量和變量
DEFAULT_CAPACITY ArrayList默認容量為10;
EMPTY_ELEMENTDATA 在調用無參構造的時候默認給的空數組
elementData 真正保存數據的數組
size 就和中真正元素的個數
構造方法有三個
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
傳入一個int數定義一個數組
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
無參構造默認生成一個空的數組
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);
}
傳入一個集合,將傳入集合的值copy到數組中,
下面主要看看ArrayList的主要方法;
1 add方法:add有兩個重載;
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
直接傳入一個元素,首先調用ensureCapacityInternal(size+1)這個方法,我們看一下這個方法;
//
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);
}
判斷是否為一個空的數組,如果為空的數組那么將minCapacity賦值為默認容量和元素個數加1中的最大的數,然后執(zhí)行ensureExplicitCapacity(minCapacity);在ensureExplicitCapacity中首先判斷minCapacity和當前集合長度進行比較(正常情況下都是minCapacity大),然后執(zhí)行grow(minCapacity);這個方法就是list擴容的精髓了;請看:
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方法中并沒有看到對插入元素的檢驗,所以ArrayList是一個有序可重復的集合,內部實現了可擴容的數組結構,再添加時,調用add(E e)方法默認是在末尾插入,這樣效率并沒有對什么影響,二如果調用add(int index, E element)這個方法在結合頭部插入元素時,由于ArrayList內部使用數組,則已有元素全部需要向后移動一位,這樣就大大影響了效率;
2 remove 方法:remove方法也有兩個重載
(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;
}
可以看到,一個是按照索引去刪除元素,一個是按照元素去刪除,
按照索引去刪除最后會返回被刪除的那個元素,
按照元素刪除只會返回true或者false;
按照元素刪除最后調用了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
}
其實最后都是通過索引去刪除元素;
好ArrayList這部分就先寫這么多,之后會繼續(xù)進行集合接口的源碼閱讀記錄.
