先分析下ArrayList的源碼,
1、ArrayList源碼分析
1.1 類實現(xiàn)的接口
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
ArrayList繼承List接口，實現(xiàn)了List接口中所有方法
1.2、構(gòu)造方法
有三個構(gòu)造方法
- 無參構(gòu)造方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
看一下具體實現(xiàn)方法
1.這是類中定義好的節(jié)點數(shù)組
transient Object[] elementData; // non-private to simplify nested class access
2.定義好的靜態(tài)空數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
當調(diào)用無參構(gòu)造函數(shù)的時候，會把靜態(tài)數(shù)組賦給節(jié)點數(shù)組，數(shù)組大小為0
- 有參構(gòu)造方法（參數(shù)是集合的大?。?/li>
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);
}
}
看下具體實現(xiàn)
先檢查給的參數(shù)是否正確
如果參數(shù)大于0, new一個指定長度的數(shù)組
this.elementData = new Object[initialCapacity];
如果參數(shù)等于0，將類中定義的空數(shù)組賦給節(jié)點數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
this.elementData = EMPTY_ELEMENTDATA;
如果參數(shù)小于0，拋出異常
- 有參構(gòu)造方法（參數(shù)是集合）
public ArrayList(Collection<? extends E> c) {
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;
}
}
如果原來的數(shù)組的長度為空，就把節(jié)點數(shù)組指向空數(shù)組，
如果不為空，將值賦給節(jié)點數(shù)組
1.3 add方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
擴充
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);
}
添加元素：
1.檢查數(shù)組的長度，調(diào)用ensureCapacityInternal(int minCapacity)方法
?? 對數(shù)組進行擴充，保證可以存放數(shù)據(jù)，
2.調(diào)用ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
??將節(jié)點數(shù)組和傳入的長度進行判斷，
3.調(diào)用calculateCapacity(elementData, minCapacity)
??如果節(jié)點數(shù)組是默認數(shù)組，返回默認長度（10）和傳入值的最大值，
4.調(diào)用ensureExplicitCapacity(int minCapacity)方法
??判斷返回的長度，如果返回的長度大于節(jié)點數(shù)組的長度，就擴充，如果不大于，直接返回
5.調(diào)用grow擴充
例子：如果是剛創(chuàng)建的集合，添加數(shù)據(jù)，
1.調(diào)用ensureCapacityInternal(size + 1); size默認為0
2.調(diào)用ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
3.調(diào)用calculateCapacity(elementData, minCapacity)
elementData指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA
minCapacity等于1
判斷成立，返回默認值（10）和傳入值1的最大值10
4.調(diào)用ensureExplicitCapacity(10)，
節(jié)點數(shù)組現(xiàn)在為空，所以分組
5.調(diào)用grow方法
得到原本節(jié)點數(shù)組的長度，擴充原數(shù)組的一半大小，得到新長度，如果新長度小于傳入的長度，就將傳入的長度作為新長度，判斷新長度是否大于最大值（是否內(nèi)存溢出），執(zhí)行數(shù)組復(fù)制，得到一個長度為10的數(shù)組
6.添加數(shù)據(jù)
elementData[size++] = e;
把數(shù)據(jù)添加進數(shù)組
例子：擴容
如果添加的是第11個元素
1.重新分組，擴充原來數(shù)組的一半，15個，15比11大，將原數(shù)組的數(shù)據(jù)拷貝到新數(shù)組
1.4、size方法
public int size() {
return size;
}
返回定義好的長度，每次添加之后size都會自增
1.5 set方法
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
具體實現(xiàn)
為某個索引處，設(shè)置值
先判斷索引是否有效，
數(shù)組節(jié)點位置的值設(shè)為新傳入的值，返回原有的值
1.6、get方法
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
判斷索引是否有效，返回對應(yīng)節(jié)點處的數(shù)據(jù)
1.7 remove方法
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;
}
具體實現(xiàn)
1.移除指定位置的數(shù)據(jù)
2.判斷索引是否正確
3.移除
移除是使用數(shù)組復(fù)制實現(xiàn)的
System.arraycopy（提供數(shù)據(jù)數(shù)組，從那個位置拷貝，拷貝數(shù)據(jù)數(shù)組，從哪個位置放，拷多長）
4.移除之后，數(shù)組最后一個節(jié)點為null
1.8 addAll方法
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
先將集合轉(zhuǎn)成數(shù)組，得到數(shù)組長度，將節(jié)點數(shù)組擴充，將數(shù)組內(nèi)容拷貝節(jié)點數(shù)組，數(shù)組長度增加
1.9 toArray方法
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
其他方法就不說了，
2.自己手動實現(xiàn)
public class MyArrayList {
private int size;//集合的長度
private Object[] elementData;//集合數(shù)組
MyArrayList(){
this(10);
}
MyArrayList(int initialCapacity) {
if (initialCapacity>0){
this.elementData = new Object[initialCapacity];
}else {
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
}
MyArrayList(Collection c){
Object[] objects = c.toArray();
int length = objects.length;
if((size=length)!=0){
//如果數(shù)組長度不等于0
elementData = Arrays.copyOf(objects,size);
}
}
/**
* 返回集合長度
* @return
*/
int size(){
return size;
}
/**
* 將集合轉(zhuǎn)成數(shù)組
* @return
*/
Object[] toArray(){
return Arrays.copyOf(elementData,size);
}
/**
* 添加元素
* @param object
*/
boolean add(Object object){
ensureCapacityInternal(size + 1);//對數(shù)組擴容
elementData[size++] = object;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//判斷數(shù)組長度是否支持當前索引
if (minCapacity-elementData.length>0){
//如果傳入的索引比節(jié)點數(shù)組長度大，分組擴充節(jié)點數(shù)組大小，
//分組
//1.擴充數(shù)組長度為原數(shù)組的1.5倍
int oldCapacity = elementData.length;
int newCapacity= oldCapacity+(oldCapacity >> 1);
if (minCapacity - newCapacity >0)
newCapacity = minCapacity;
//2.新建數(shù)組，將原數(shù)組數(shù)據(jù)復(fù)制
elementData =Arrays.copyOf(elementData,newCapacity);
}
}
Object get(int index){
rangeIndex(index);
return elementData[index];
}
//判斷索引是否超標
private void rangeIndex(int index) {
if (index >= size || index<0){
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
}
/**
* 將某處的值設(shè)為object
* @param index
* @param object
*/
void set(int index,Object object){
rangeIndex(index);
elementData[index] = object;
}
}
更多詳情：qq群 552113611
