2007-01-16 | java的ArrayList源码解读【转】
上一篇 / 下一篇 2007-04-27 22:03:38 / 个人分类:编程基础
Java 2源码解读:java.util.ArrayList |
-mu1m v(E qX`0ArrayList是List接口的一个可变长数组实现。实现了所有List接口的操作,并允许存储null值。除了没有进行同步,ArrayList基本等同于Vector。在Vector中几乎对所有的方法都进行了同步,但ArrayList仅对writeObject和readObject进行了同步,其它比如add(Object)、remove(int)等都没有同步。
5Y,\ iD;Y6[t051Testing软件测试网]OS?4b
1.存储
ArrayList使用一个Object的数组存储元素。51Testing软件测试网 rb/ysJ^#UD4yprivate transient Object elementData[];51Testing软件测试网,g5\LE,K2upj
ArrayList实现了java.io.Serializable接口,这儿的transient标示这个属性不需要自动序列化。下面会在writeObject()方法中详细讲解为什么要这样作。
,b2vU0d3AcfxI3_0
2.add和remove
51Testing软件测试网q_*e#A1@hpublic boolean add(Object o) {51Testing软件测试网"R)F'yi&C|
ensureCapacity(size + 1); // Increments modCount!!51Testing软件测试网(m Blx:P:A
elementData[size++] = o;
H&qte#^2i-Y![0T0 return true;
Z7Kl!w&lD|w0 }51Testing软件测试网 i)Z_*a:s"?&\
51Testing软件测试网A+T2]zI2Iz&T
注意这儿的ensureCapacity()方法,它的作用是保证elementData数组的长度可以容纳一个新元素。在“自动变长机制”中将详细讲解。
xn@ lXI8yH;n0 public Object remove(int index) {51Testing软件测试网k([vl[euXS
RangeCheck(index);
d%S!}h/qK Z0 modCount++;
w6y#^5V-i0 Object oldValue = elementData[index];
weJs#N:O)U%b0 int numMoved = size - index - 1;
9pU8I O D:i0 if (numMoved > 0)51Testing软件测试网%hy+A W#iH*h2N
System.arraycopy(elementData, index+1, elementData, index,51Testing软件测试网:vQ_l?0H
numMoved);
.P R-U:r(T2D0 elementData[--size] = null; // Let gc do its work51Testing软件测试网Q b G8O5u\;X/|[]S
return oldValue;51Testing软件测试网8sS,o;c3b(vS
}
d/PP4Z,hja0
$]Y&qGY0RangeCheck()的作用是进行边界检查。由于ArrayList采用一个对象数组存储元素,所以在删除一个元素时需要把后面的元素前移。删除一个元素时只是把该元素在elementData数组中的引用置为null,具体的对象的销毁由垃圾收集器负责。51Testing软件测试网`ZKKg
modCount的作用将在下面的“iterator()中的同步”中说明。51Testing软件测试网%y C;B%GK u/H
注:在前移时使用了System提供的一个实用方法:arraycopy(),在本例中可以看出System.arraycopy()方法可以对同一个数组进行操作,这个方法是一个native方法,如果对同一个数组进行操作时,会首先把从源部分拷贝到一个临时数组,在把临时数组的元素拷贝到目标位置。
Eau7Hon [/w0
3.自动变长机制
在实例化一个ArrayList时,你可以指定一个初始容量。这个容量就是elementData数组的初始长度。如果你使用:51Testing软件测试网H-j!?b:zg4J~0dArrayList list = new ArrayList();51Testing软件测试网PJ-K]4iK
51Testing软件测试网4B-m n9o!]SnlQ+u
则使用缺省的容量:10。
*QF@e``z0 public ArrayList() {51Testing软件测试网1[0b|Y jW
this(10);
q4i@?;h C7s0 }51Testing软件测试网9_Mq'NP:Naq
zu _,D1R0ArrayList提供了四种add()方法,51Testing软件测试网Xi;Z H$ljJ0oF
- public boolean add(Object o)51Testing软件测试网8It(yC&fy.w h,^
- public void add(int index, Object element)
(O(]3`o8]Zc ~7u3Z0 - public boolean addAll(Collection c)
1i,L+U3bVK0 - public boolean addAll(int index, Collection c)
在每一种add()方法中,都首先调用了一个ensureCapacity(int miniCapacity)方法,这个方法保证elementData数组的长度不小于miniCapacity。ArrayList的自动变长机制就是在这个方法中实现的。
'E H:Y)n'V:W!g"A0 public void ensureCapacity(int minCapacity) {51Testing软件测试网%o c]$C't
modCount++;51Testing软件测试网?k5z&[fb
int oldCapacity = elementData.length;51Testing软件测试网*W}ZV:myc/xm u
if (minCapacity > oldCapacity) {51Testing软件测试网ZrlN*C@7B8E#d9`
Object oldData[] = elementData;51Testing软件测试网`T'\,M7VXCH8H1H,n y
int newCapacity = (oldCapacity * 3)/2 + 1;51Testing软件测试网4J#H PF:n0CHvP
if (newCapacity < minCapacity)51Testing软件测试网0j(} I fD\
newCapacity = minCapacity;
5Qw_'eA6Ia9d0 elementData = new Object[newCapacity];
V!c"l4J;Yo0 System.arraycopy(oldData, 0, elementData, 0, size);
uKE.?gGjdL$|/E0 }51Testing软件测试网xb9~w4\k7|)i
}51Testing软件测试网EY3xz$_A w.F`q
51Testing软件测试网m u0bn)GU4h.iJV
从这个方法实现中可以看出ArrayList每次扩容,都扩大到原来大小的1.5倍。51Testing软件测试网i3uRr`
每种add()方法的实现都大同小异,下面给出add(Object)方法的实现:
4W ay-rG"tv4Q0 public boolean add(Object o) {51Testing软件测试网\B3{3FD(I$B
ensureCapacity(size + 1); // Increments modCount!!
jAUx2k4x0 elementData[size++] = o;51Testing软件测试网Vp6n'uhx
return true;51Testing软件测试网`$SN,SG1Q
}51Testing软件测试网b.Fn(G`N
5Kap!LW0
4.iterator()中的同步
在父类AbstractList中定义了一个int型的属性:modCount,记录了ArrayList结构性变化的次数。v,KP1p6fn0 protected transient int modCount = 0;51Testing软件测试网%|PWxZ&h(M)Ve7\
51Testing软件测试网6D0w6LC/nDSy{
在ArrayList的所有涉及结构变化的方法中都增加modCount的值,包括:add()、remove()、addAll()、removeRange()及clear()方法。这些方法每调用一次,modCount的值就加1。51Testing软件测试网NfO*sRYU!r1z:HK&J
注:add()及addAll()方法的modCount的值是在其中调用的ensureCapacity()方法中增加的。51Testing软件测试网6dq6Bj(|P5L
51Testing软件测试网(~ q0_cF-h:UY
AbstractList中的iterator()方法(ArrayList直接继承了这个方法)使用了一个私有内部成员类Itr,生成一个Itr对象(Iterator接口)返回:
6rrT GWA/U E1@0 public Iterator iterator() {
Ec*t6l9N(K/{b+L p0 return new Itr();51Testing软件测试网nJu9K0oo
}51Testing软件测试网4jI8R d:Q7y5j1h0{
!A7rk&xw0l5Z0Itr实现了Iterator()接口,其中也定义了一个int型的属性:expectedModCount,这个属性在Itr类初始化时被赋予ArrayList对象的modCount属性的值。51Testing软件测试网fhYFX:_
int expectedModCount = modCount;51Testing软件测试网qpO$Y3p;{0Vw k4i
h/H'X!O:V0注:内部成员类Itr也是ArrayList类的一个成员,它可以访问所有的AbstractList的属性和方法。理解了这一点,Itr类的实现就容易理解了。
7g.l$oK!@yG"z0
rTfLG_#wz+}#Sr0在Itr.hasNext()方法中:51Testing软件测试网"EJO H%up
public boolean hasNext() {
sL$k0k)A5mi?0 return cursor != size();
|n?Y?A0 }51Testing软件测试网 PJ7V+o/d_t'W
51Testing软件测试网&d#E*f ^wC^I
调用了AbstractList的size()方法,比较当前光标位置是否越界。
Eh*xa"s|Z"]t0
xG W1JNI1B oH0在Itr.next()方法中,Itr也调用了定义在AbstractList中的get(int)方法,返回当前光标处的元素:51Testing软件测试网8MZ_4\Z
public Object next() {
4}"~:ay5wjv,fx'zV0 try {51Testing软件测试网G-O#}#nR
Object next = get(cursor);
J K5A6Ss t w0 checkForComodification();
0H5v-D%u V0 lastRet = cursor++;51Testing软件测试网mGA-p~2etL'j
return next;51Testing软件测试网"x,H&M@#qX8Uqx
} catch(IndexOutOfBoundsException e) {
Y9ECE3]^;\0 checkForComodification();
(\~'J(H lHr0S5}d0 throw new NoSuchElementException();
E'a${4CCU*mE`o0 }51Testing软件测试网3J[?$a@ wK
}
d kJ`-Cv1|9eR051Testing软件测试网Vt0Vr#}
注意,在next()方法中调用了checkForComodification()方法,进行对修改的同步检查:51Testing软件测试网"h2mr"SnT~;p3[xQ
final void checkForComodification() {51Testing软件测试网 Cf'@ugOD
if (modCount != expectedModCount)51Testing软件测试网A8V AGf$Du7eU
throw new ConcurrentModificationException();
U.]$v|#ny8co0 }51Testing软件测试网)X\W LI
F/K?gc.NY0现在对modCount和expectedModCount的作用应该非常清楚了。在对一个集合对象进行跌代操作的同时,并不限制对集合对象的元素进行操作,这些操作包括一些可能引起跌代错误的add()或remove()等危险操作。在AbstractList中,使用了一个简单的机制来规避这些风险。这就是modCount和expectedModCount的作用所在。
4a;a8T6tcBY-MZ0
5.序列化支持
ArrayList实现了java.io.Serializable接口,所以ArrayList对象可以序列化到持久存储介质中。ArrayList的主要属性定义如下:RJ;tFDG0
- private static final long serialVersionUID = 8683452581122892189L;
a9GOI-u9v0 - private transient Object elementData[];
%y)b]e4G0 - private int size;
9lim]V+x/k0可以看出serialVersionUID和size都将自动序列化到介质中,但elementData数组对象却定义为transient了。也就是说ArrayList中的所有这些元素都不会自动系列化到介质中。为什么要这样实现?因为elementData数组中存储的“元素”其实仅是对这些元素的一个引用,并不是真正的对象,序列化一个对象的引用是毫无意义的,因为序列化是为了反序列化,当你反序列化时,这些对象的引用已经不可能指向原来的对象了。所以在这儿需要手工的对ArrayList的元素进行序列化操作。这就是writeObject()的作用。
Gc!GdH L0 private synchronized void writeObject(java.io.ObjectOutputStream s)51Testing软件测试网PiJ!b e*bK6Q2{I]
throws java.io.IOException{
"g+dxB8^`!i3G2pH'{0 // Write out element count, and any hidden stuff