- 浏览: 293503 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
zh554275855:
1 接口是核心,其定义了要做的事情,包含了许多的方法,但没有定 ...
抽象类和接口的区别,使用场景 -
MeowPass:
[color=red][size=xx-large][alig ...
java 字符串split有很多坑,使用时请小心!! -
jayzc1234:
讲的很好 看头像还是个女的 真是牛逼
WEBX学习总结 -
wodexiang:
写的什么狗屎
jetty启动以及嵌入式启动 -
繁星水:
很好,感谢分享与总结,谢谢!
jetty启动以及嵌入式启动
ArrayList是List接口的一个可变长数组实现。实现了所有List接口的操作,并允许存储null值。除了没有进行同步,ArrayList基本等同于Vector。在Vector中几乎对所有的方法都进行了同步,但ArrayList仅对writeObject和readObject进行了同步,其它比如add(Object)、remove(int)等都没有同步。
1.存储
ArrayList使用一个Object的数组存储元素。
private transient Object elementData[];
ArrayList实现了java.io.Serializable接口,这儿的transient标示这个属性不需要自动序列化。下面会在writeObject()方法中详细讲解为什么要这样作。
2.add和remove
public boolean add(Object o)
{
ensureCapacity(size + 1);
// Increments modCount!! elementData[size++] = o;
return true;
}
注意这儿的ensureCapacity()方法,它的作用是保证elementData数组的长度可以容纳一个新元素。在“自动变长机制”中将详细讲解。
public Object remove(int index)
{
RangeCheck(index);
modCount++;
Object oldValue = elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // Let gc do its work return oldValue;
}
RangeCheck()的作用是进行边界检查。由于ArrayList采用一个对象数组存储元素,所以在删除一个元素时需要把后面的元素前移。删除一个元素时只是把该元素在elementData数组中的引用置为null,具体的对象的销毁由垃圾收集器负责。
modCount的作用将在下面的“iterator()中的同步”中说明。
注:在前移时使用了System提供的一个实用方法:arraycopy(),在本例中可以看出System.arraycopy()方法可以对同一个数组进行操作,这个方法是一个native方法,如果对同一个数组进行操作时,会首先把从源部分拷贝到一个临时数组,在把临时数组的元素拷贝到目标位置。
3.自动变长机制
在实例化一个ArrayList时,你可以指定一个初始容量。这个容量就是elementData数组的初始长度。如果你使用:
ArrayList list = new ArrayList();
则使用缺省的容量:10。
public ArrayList() { this(10); }
ArrayList提供了四种add()方法,
public boolean add(Object o)
public void add(int index, Object element)
public boolean addAll(Collection c)
public boolean addAll(int index, Collection c)
在每一种add()方法中,都首先调用了一个ensureCapacity(int miniCapacity)方法,这个方法保证elementData数组的长度不小于miniCapacity。ArrayList的自动变长机制就是在这个方法中实现的。
public void ensureCapacity(int minCapacity)
{ modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity)
{
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity) newCapacity = minCapacity;
elementData = new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}
从这个方法实现中可以看出ArrayList每次扩容,都扩大到原来大小的1.5倍。
每种add()方法的实现都大同小异,下面给出add(Object)方法的实现:
public boolean add(Object o)
{
ensureCapacity(size + 1);
// Increments modCount!! elementData[size++] = o;
return true;
}
4.iterator()中的同步
在父类AbstractList中定义了一个int型的属性:modCount,记录了ArrayList结构性变化的次数。
protected transient int modCount = 0;
在ArrayList的所有涉及结构变化的方法中都增加modCount的值,包括:add()、remove()、addAll()、removeRange()及clear()方法。这些方法每调用一次,modCount的值就加1。
注:add()及addAll()方法的modCount的值是在其中调用的ensureCapacity()方法中增加的。
AbstractList中的iterator()方法(ArrayList直接继承了这个方法)使用了一个私有内部成员类Itr,生成一个Itr对象(Iterator接口)返回:
public Iterator iterator() { return new Itr(); }
Itr实现了Iterator()接口,其中也定义了一个int型的属性:expectedModCount,这个属性在Itr类初始化时被赋予ArrayList对象的modCount属性的值。
int expectedModCount = modCount;
注:内部成员类Itr也是ArrayList类的一个成员,它可以访问所有的AbstractList的属性和方法。理解了这一点,Itr类的实现就容易理解了。
在Itr.hasNext()方法中:
public boolean hasNext() { return cursor != size(); }
调用了AbstractList的size()方法,比较当前光标位置是否越界。
在Itr.next()方法中,Itr也调用了定义在AbstractList中的get(int)方法,返回当前光标处的元素:
public Object next()
{
try
{
Object next = get(cursor);
checkForComodification();
lastRet = cursor++;
return next;
}
catch(IndexOutOfBoundsException e)
{
checkForComodification();
throw new NoSuchElementException();
}
}
注意,在next()方法中调用了checkForComodification()方法,进行对修改的同步检查:
final void checkForComodification()
{
if (modCount != expectedModCount) throw new ConcurrentModificationException(); }
现在对modCount和expectedModCount的作用应该非常清楚了。在对一个集合对象进行跌代操作的同时,并不限制对集合对象的元素进行操作,这些操作包括一些可能引起跌代错误的add()或remove()等危险操作。在AbstractList中,使用了一个简单的机制来规避这些风险。这就是modCount和expectedModCount的作用所在。
5.序列化支持
ArrayList实现了java.io.Serializable接口,所以ArrayList对象可以序列化到持久存储介质中。 ArrayList的主要属性定义如下:
private static final long serialVersionUID = 8683452581122892189L;
private transient Object elementData[];
private int size;
可以看出serialVersionUID和size都将自动序列化到介质中,但elementData数组对象却定义为transient了。也就是说ArrayList中的所有这些元素都不会自动系列化到介质中。为什么要这样实现?因为elementData数组中存储的“元素”其实仅是对这些元素的一个引用,并不是真正的对象,序列化一个对象的引用是毫无意义的,因为序列化是为了反序列化,当你反序列化时,这些对象的引用已经不可能指向原来的对象了。所以在这儿需要手工的对ArrayList的元素进行序列化操作。这就是writeObject()的作用。
private synchronized void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException
{
// Write out element count, and any hidden stuff s.defaultWriteObject();
// Write out array length s.writeInt(elementData.length);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) s.writeObject(elementData[i]);
}
这样元素数组elementData中的所以元素对象就可以正确地序列化到存储介质了。
对应的readObject()也按照writeObject()方法的顺序从输入流中读取:
private synchronized void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException
{
// Read in size, and any hidden stuff s.defaultReadObject();
// Read in array length and allocate array
int arrayLength = s.readInt();
elementData = new Object[arrayLength];
// Read in all elements in the proper order.
for (int i=0; i<size; i++) elementData[i] = s.readObject(); }
总结:知道了具体的实现机理之后就能了解了别人的设计思想,怎么来实现,性能并发等是怎么考虑的,学习算法数据结构的实际使用情况,最后就是你在用的时候会能把它用得最恰到好处,而且也可以在遇到问题的时候更快速定位,最后是能把它的一些思想用在后面编程中
1.存储
ArrayList使用一个Object的数组存储元素。
private transient Object elementData[];
ArrayList实现了java.io.Serializable接口,这儿的transient标示这个属性不需要自动序列化。下面会在writeObject()方法中详细讲解为什么要这样作。
2.add和remove
public boolean add(Object o)
{
ensureCapacity(size + 1);
// Increments modCount!! elementData[size++] = o;
return true;
}
注意这儿的ensureCapacity()方法,它的作用是保证elementData数组的长度可以容纳一个新元素。在“自动变长机制”中将详细讲解。
public Object remove(int index)
{
RangeCheck(index);
modCount++;
Object oldValue = elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // Let gc do its work return oldValue;
}
RangeCheck()的作用是进行边界检查。由于ArrayList采用一个对象数组存储元素,所以在删除一个元素时需要把后面的元素前移。删除一个元素时只是把该元素在elementData数组中的引用置为null,具体的对象的销毁由垃圾收集器负责。
modCount的作用将在下面的“iterator()中的同步”中说明。
注:在前移时使用了System提供的一个实用方法:arraycopy(),在本例中可以看出System.arraycopy()方法可以对同一个数组进行操作,这个方法是一个native方法,如果对同一个数组进行操作时,会首先把从源部分拷贝到一个临时数组,在把临时数组的元素拷贝到目标位置。
3.自动变长机制
在实例化一个ArrayList时,你可以指定一个初始容量。这个容量就是elementData数组的初始长度。如果你使用:
ArrayList list = new ArrayList();
则使用缺省的容量:10。
public ArrayList() { this(10); }
ArrayList提供了四种add()方法,
public boolean add(Object o)
public void add(int index, Object element)
public boolean addAll(Collection c)
public boolean addAll(int index, Collection c)
在每一种add()方法中,都首先调用了一个ensureCapacity(int miniCapacity)方法,这个方法保证elementData数组的长度不小于miniCapacity。ArrayList的自动变长机制就是在这个方法中实现的。
public void ensureCapacity(int minCapacity)
{ modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity)
{
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity) newCapacity = minCapacity;
elementData = new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}
从这个方法实现中可以看出ArrayList每次扩容,都扩大到原来大小的1.5倍。
每种add()方法的实现都大同小异,下面给出add(Object)方法的实现:
public boolean add(Object o)
{
ensureCapacity(size + 1);
// Increments modCount!! elementData[size++] = o;
return true;
}
4.iterator()中的同步
在父类AbstractList中定义了一个int型的属性:modCount,记录了ArrayList结构性变化的次数。
protected transient int modCount = 0;
在ArrayList的所有涉及结构变化的方法中都增加modCount的值,包括:add()、remove()、addAll()、removeRange()及clear()方法。这些方法每调用一次,modCount的值就加1。
注:add()及addAll()方法的modCount的值是在其中调用的ensureCapacity()方法中增加的。
AbstractList中的iterator()方法(ArrayList直接继承了这个方法)使用了一个私有内部成员类Itr,生成一个Itr对象(Iterator接口)返回:
public Iterator iterator() { return new Itr(); }
Itr实现了Iterator()接口,其中也定义了一个int型的属性:expectedModCount,这个属性在Itr类初始化时被赋予ArrayList对象的modCount属性的值。
int expectedModCount = modCount;
注:内部成员类Itr也是ArrayList类的一个成员,它可以访问所有的AbstractList的属性和方法。理解了这一点,Itr类的实现就容易理解了。
在Itr.hasNext()方法中:
public boolean hasNext() { return cursor != size(); }
调用了AbstractList的size()方法,比较当前光标位置是否越界。
在Itr.next()方法中,Itr也调用了定义在AbstractList中的get(int)方法,返回当前光标处的元素:
public Object next()
{
try
{
Object next = get(cursor);
checkForComodification();
lastRet = cursor++;
return next;
}
catch(IndexOutOfBoundsException e)
{
checkForComodification();
throw new NoSuchElementException();
}
}
注意,在next()方法中调用了checkForComodification()方法,进行对修改的同步检查:
final void checkForComodification()
{
if (modCount != expectedModCount) throw new ConcurrentModificationException(); }
现在对modCount和expectedModCount的作用应该非常清楚了。在对一个集合对象进行跌代操作的同时,并不限制对集合对象的元素进行操作,这些操作包括一些可能引起跌代错误的add()或remove()等危险操作。在AbstractList中,使用了一个简单的机制来规避这些风险。这就是modCount和expectedModCount的作用所在。
5.序列化支持
ArrayList实现了java.io.Serializable接口,所以ArrayList对象可以序列化到持久存储介质中。 ArrayList的主要属性定义如下:
private static final long serialVersionUID = 8683452581122892189L;
private transient Object elementData[];
private int size;
可以看出serialVersionUID和size都将自动序列化到介质中,但elementData数组对象却定义为transient了。也就是说ArrayList中的所有这些元素都不会自动系列化到介质中。为什么要这样实现?因为elementData数组中存储的“元素”其实仅是对这些元素的一个引用,并不是真正的对象,序列化一个对象的引用是毫无意义的,因为序列化是为了反序列化,当你反序列化时,这些对象的引用已经不可能指向原来的对象了。所以在这儿需要手工的对ArrayList的元素进行序列化操作。这就是writeObject()的作用。
private synchronized void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException
{
// Write out element count, and any hidden stuff s.defaultWriteObject();
// Write out array length s.writeInt(elementData.length);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) s.writeObject(elementData[i]);
}
这样元素数组elementData中的所以元素对象就可以正确地序列化到存储介质了。
对应的readObject()也按照writeObject()方法的顺序从输入流中读取:
private synchronized void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException
{
// Read in size, and any hidden stuff s.defaultReadObject();
// Read in array length and allocate array
int arrayLength = s.readInt();
elementData = new Object[arrayLength];
// Read in all elements in the proper order.
for (int i=0; i<size; i++) elementData[i] = s.readObject(); }
总结:知道了具体的实现机理之后就能了解了别人的设计思想,怎么来实现,性能并发等是怎么考虑的,学习算法数据结构的实际使用情况,最后就是你在用的时候会能把它用得最恰到好处,而且也可以在遇到问题的时候更快速定位,最后是能把它的一些思想用在后面编程中
评论
1 楼
Yinny
2011-08-17
1:根本不存在一个动态增长的容器供我们使用。所谓集合就是在内部定义一个一定大小的数组,这个数组的容量也就是Capacity属性,如果没有设置,默认是一个0长度的数组。当开始添加第一个数据时,数组的长度会被设为4。
2:当我们调用ADD方法为集合添加元素时,它会判断集合内部的数组是否已填充满,如果填充满了,就会实例化一个新的数组,数组容量为原数组容量的2倍。然后把原数组中的数据COPY到新的数组中,然后原数组会成为垃圾回收的对象被GC收集。
3:如果数据量不大或能基本能确定大小的情况下,尽量使用数组而不是集合,因为多次创建新数组并COPY数据会对性能造成损伤(虽然微乎其微)。
2:当我们调用ADD方法为集合添加元素时,它会判断集合内部的数组是否已填充满,如果填充满了,就会实例化一个新的数组,数组容量为原数组容量的2倍。然后把原数组中的数据COPY到新的数组中,然后原数组会成为垃圾回收的对象被GC收集。
3:如果数据量不大或能基本能确定大小的情况下,尽量使用数组而不是集合,因为多次创建新数组并COPY数据会对性能造成损伤(虽然微乎其微)。
发表评论
-
多线程重要方法的使用
2013-09-21 22:08 1445首先讲一下进程和线程的区别: 进程:每个进程都有 ... -
jetty启动以及嵌入式启动
2013-08-18 21:47 25132首先得下载jetty http:/ ... -
最容易被忽视的基础异常
2013-04-19 15:23 0result = getShopGroupDOList(req ... -
用java处理事务
2013-03-15 09:58 1011[size=medium]数据库的事务平时很少用到,只有评价线 ... -
servlet的单例多线程
2013-03-13 17:19 4166因为我们平时编程用到了servlet,而servlet的容器默 ... -
泛型的几个注意点!
2013-03-03 20:45 5293[size=medium]上周代码里碰 ... -
搜索切换dump之MapReduce讲解
2012-12-23 20:16 1544分享聚合dump的是评价的 ... -
java 字符串split有很多坑,使用时请小心!!
2012-12-19 11:13 84252System.out.println(":ab: ... -
SimpleDateFormat多线程问题
2012-12-12 11:04 979之前在写控制双12开关的函数时遇到了SimpleDateFor ... -
删除单条分享理由的日常总结
2012-08-15 14:32 1097上周总算把这个简单蕴 ... -
Apache 中RewriteRule 规则参数
2012-08-15 11:33 2021Apache 中RewriteRule 规则 ... -
Memcached installation under Windows and Java client calls
2012-07-23 00:42 12991、What is Memcached? Free & ... -
webx框架之RundataService
2012-07-12 22:37 1361之前对webx的学习都是有关响应和处理请求的流程和源码实现,配 ... -
一个简单的test
2012-06-25 21:46 1039public class UrlTest { publ ... -
java.io学习总结
2012-06-18 00:33 9650我将按照基类的顺序:InputStream、OutPutStr ... -
HashMap源码学习分享心得
2012-06-01 14:58 1391[size=medium]今早在团队内分享了<通过 Ha ... -
System.arraycopy
2012-05-28 18:43 1356在JAVA里面,可以用复制 ... -
System类解析
2012-05-24 16:18 0System类是final类,无法被继承,包含一些有用的类字段 ... -
一个简单的Java(string)截取图片的后缀程序
2012-05-03 16:05 9246Java代码 public static String ... -
jboss启动时异常
2012-03-15 14:01 1484今天在启动jboss之前改动了一下它的jboss-servic ...
相关推荐
Java Methods-java.util.ArrayList.ppt
详细介绍了java.util.logging.Logger的用法和结构,对如果扩展Logger起到抛砖引玉的作用!尊重劳动成果,亲下载了要给个评价!
1. java.util.concurrent - Java 并发工具包 2. 阻塞队列 BlockingQueue 3. 数组阻塞队列 ArrayBlockingQueue 4. 延迟队列 DelayQueue 5. 链阻塞队列 LinkedBlockingQueue 6. 具有优先级的阻塞队列 ...
Tomcat内存溢出的解决方法(java.util.concurrent.ExecutionException:java.lang.OutOfMemoryError),内附解决方案!
本文通过对数据压缩算法的简要介绍,然后以详细的示例演示了利用java.util.zip包实现数据的压缩与解压,并扩展到在网络传输方面如何应用java.util.zip包现数据压缩与解压
Exception in thread “main“ java.util.InputMismatchException
java并发工具包 java.util.concurrent中文版-带书签版
Java.util.ConcurrentModificationException 异常问题详解 ConcurrentModificationException 异常是 Java 中一个常见的异常,它发生在 Iterator 遍历集合时,集合同时被修改引起的异常。在 Java 中,集合类如 ...
java并发工具包 java.util.concurrent中文版pdf
"JDK1.5中的线程池(java.util.concurrent.ThreadPoolExecutor)使用" JDK1.5中的线程池(java.util.concurrent.ThreadPoolExecutor)使用是Java多线程编程中的一种重要概念。随着多线程编程的普及,线程池的使用变得...
java.util.concurrent - Java 并发工具包 2. 阻塞队列 BlockingQueue 3. 数组阻塞队列 ArrayBlockingQueue 4. 延迟队列 DelayQueue 5. 链阻塞队列 LinkedBlockingQueue 6. 具有优先级的阻塞队列 ...
Java.sql.Date与Java.util.Date的区别和转换 Java.util.Date和Java.sql.Date是Java中两种不同的日期和时间表示方式,虽然它们都是表示日期和时间,但是它们之间存在着一些重要的区别。 首先,Java.util.Date是Java...
Java并发编程工具包java.util.concurrent的UML类结构图 PDF
axis2解决 org.apache.axis2.util.JavaUtils.callStackToString问题
java-util-iterator.pdfjava-util-iterator.pdfjava-util-iterator.pdf
Android Base64Jar包及Java完整源码 包含:android android.util.Base64 类, BASE64编码、解码算法;包含该类的完整Jar包。 可以直接导入Jar包或者引用类及类中相关方法。 很不错的工具类。
java常用工具类,用于日常开发的。
java.util.concurrent系列文章(1) java.util.concurrent系列文章(1) java.util.concurrent系列文章(1) java.util.concurrent系列文章(1)
java.util.Date与java.sql.Date互转及字符串转换为日期时间格式.docx
字符串工具类,判定字符串是否为空等,封装各种字符串工具方法每个方法都有注释