• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

Java集合之ArrayList源码解析(下)

技术杂谈 勤劳的小蚂蚁 3个月前 (01-25) 78次浏览 已收录 0个评论 扫描二维码

接上篇…..

修改元素

// 将指定位置的元素改为指定的值
public E set(int index, E element){
 rangeCheck(index);    
 // 检查index是否越界

 E oldValue = elementData(index);
 elementData[index] = element;
 return oldValue;
}

查找元素

//判断ArrayList中是否包含Object(o)
public boolean contains(Object o) {
 return indexOf(o) >= 0;
}

//返回一个值在数组首次出现的位置,会根据是否为null使用不同方式判断。
//不存在就返回-1。时间复杂度为O(N)
publicintindexOf(Object o) {
 if (o == null) {
   for (int i = 0; i < size; i++)                
     if (elementData[i]==null)
       return i;
 } else {
   for (int i = 0; i < size; i++)
     if (o.equals(elementData[i]))
       return i;
 }
 return-1;
}

//返回一个值在数组最后一次出现的位置,不存在就返回-1。时间复杂度为O(N)
publicintlastIndexOf(Object o) {
 if (o == null) {
   for (int i = size-1; i >= 0; i–)
     if (elementData[i]==null)
       return i;
 } else {
   for (int i = size-1; i >= 0; i–)
     if (o.equals(elementData[i]))
       return i;
 }
 return-1;
}

//返回指定位置的值,因为是数组,所以速度特别快
@SuppressWarnings(“unchecked”)
E elementData(int index) {
 return (E) elementData[index];
}

//返回指定位置的值,但是会检查这个位置数否超出数组长度
public E get(int index) {
 rangeCheck(index);

 return elementData(index);
 //实质上return (E) elementData[index]

}


序列化

//保存数组实例的状态到一个流(即它序列化)。写入过程数组被更改会抛出异常
privatevoidwriteObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
 int expectedModCount = modCount;
 s.defaultWriteObject();
 //执行默认的反序列化/序列化过程。将当前类的非静态和非瞬态字段写入此流
 // 写入大小
 s.writeInt(size);
 // 按顺序写入所有元素
 for (int i=0; i<size; i++) {
   s.writeObject(elementData[i]);
 }
 if (modCount != expectedModCount) {
   thrownew ConcurrentModificationException();
 }
}
//上面是写,这个就是读了。
privatevoidreadObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
 elementData = EMPTY_ELEMENTDATA;
 // 执行默认的序列化/反序列化过程
 s.defaultReadObject();
 // 读入数组长度
 s.readInt();
 if (size > 0) {
   ensureCapacityInternal(size);
   Object[] a = elementData;
   //读入所有元素
   for (int i=0; i<size; i++) {
     a[i] = s.readObject();
   }
 }
}

为什么要自定义序列化、反序列化机制呢?
由于ArrayList实质上是一个动态数组,往往数组中会有空余的空间,如果采用默认的序列化机制,那些空余的空间会作为null写入本地文件或者在网络中传输,耗费了不必要的资源。所以,ArrayList使用自定义序列化机制,仅写入索引为【0,size)的有效元素以节省资源。

迭代器

//返回ListIterator,开始位置为指定参数
public ListIterator<E> listIterator(int index){
 if (index < 0 || index > size)
   thrownew IndexOutOfBoundsException(“Index: “+index);
 returnnew ListItr(index);
}

//返回ListIterator,开始位置为0
public ListIterator<E> listIterator(){
 returnnew ListItr(0);
}

//返回普通迭代器
public Iterator<E> iterator(){
 returnnew Itr();
}

//通用的迭代器实现
privateclassItrimplementsIterator<E> {
 int cursor;      
 //游标,下一个元素的索引,默认初始化为0
 int lastRet = –1;
 //上次访问的元素的位置
 int expectedModCount = modCount;
 //迭代过程不允许修改数组,否则就抛出异常
 //是否还有下一个
 publicbooleanhasNext(){
   return cursor != size;
 }
 //下一个元素
 @SuppressWarnings(“unchecked”)
 public E next(){
   checkForComodification();//检查数组是否被修改
   int i = cursor;
   if (i >= size)
     thrownew NoSuchElementException();
   Object[] elementData = ArrayList.this.elementData;
   if (i >= elementData.length)
     thrownew ConcurrentModificationException();
   cursor = i + 1; //向后移动游标
   return (E) elementData[lastRet = i];    
   //设置访问的位置并返回这个值
 }
 //删除元素
 publicvoidremove(){
   if (lastRet < 0)
     thrownew IllegalStateException();
   checkForComodification();//检查数组是否被修改
   try {
     ArrayList.this.remove(lastRet);
     cursor = lastRet;
     lastRet = –1;
     expectedModCount = modCount;
   } catch (IndexOutOfBoundsException ex) {
     thrownew ConcurrentModificationException();
   }
 }
 @Override
 @SuppressWarnings(“unchecked”)
 publicvoidforEachRemaining(Consumer<? super E> consumer){
   Objects.requireNonNull(consumer);
   finalint size = ArrayList.this.size;
   int i = cursor;
   if (i >= size) {
     return;
   }
   final Object[] elementData = ArrayList.this.elementData;
   if (i >= elementData.length) {
     thrownew ConcurrentModificationException();
   }
   while (i != size && modCount == expectedModCount) {
     consumer.accept((E) elementData[i++]);
   }
   cursor = i;
   lastRet = i – 1;
   checkForComodification();
 }
 //检查数组是否被修改
 finalvoidcheckForComodification(){
   if (modCount != expectedModCount)
     thrownew ConcurrentModificationException();
 }
}

//ListIterator迭代器实现
privateclassListItrextendsItrimplementsListIterator<E> {
 ListItr(int index) {
   super();
   cursor = index;
 }
 publicbooleanhasPrevious(){
   return cursor != 0;
 }
 publicintnextIndex(){
   return cursor;
 }
 publicintpreviousIndex(){
   return cursor – 1;
 }
 @SuppressWarnings(“unchecked”)
 public E previous(){
   checkForComodification();
   int i = cursor – 1;
   if (i < 0)
     thrownew NoSuchElementException();
   Object[] elementData = ArrayList.this.elementData;
   if (i >= elementData.length)
     thrownew ConcurrentModificationException();
   cursor = i;
   return (E) elementData[lastRet = i];
 }
 publicvoidset(E e){
   if (lastRet < 0)
     thrownew IllegalStateException();
   checkForComodification();
   try {
     ArrayList.this.set(lastRet, e);
   } catch (IndexOutOfBoundsException ex) {
     thrownew ConcurrentModificationException();
   }
 }
 publicvoidadd(E e){
   checkForComodification();
   try {
     int i = cursor;
     ArrayList.this.add(i, e);
     cursor = i + 1;
     lastRet = –1;
     expectedModCount = modCount;
   } catch (IndexOutOfBoundsException ex) {
     thrownew ConcurrentModificationException();
   }
 }

}


Iterator与ListIterator的区别:
  1. Iterator可以应用于所有的集合,Set、List和Map和这些集合的子类型。而ListIterator只能用于List及其子类型;
  2. Iterator只能实现顺序向后遍历,ListIterator可实现顺序向后遍历和逆向(顺序向前)遍历;
  3. Iterator只能实现remove操作,ListIterator可以实现remove操作,add操作,set操作。

其他方法

//返回ArrayList的大小(元素个数)
publicintsize(){
 return size;
}

//判断ArrayList是否为空
publicbooleanisEmpty(){
 return size == 0;
}

//返回此 ArrayList实例的浅拷贝
//(元素本身没有被复制,复制过程数组发生改变会抛出异常)
public Object clone(){
 try {
   ArrayList<?> v = (ArrayList<?>) super.clone();
   v.elementData = Arrays.copyOf(elementData, size);
   v.modCount = 0;
   return v;
 } catch (CloneNotSupportedException e) {
   thrownew InternalError(e);
 }
}
/*
浅克隆就是我们所看到的Arrays.copyOf, System.arraycopy,
数组是新的,但是里面N个元素全是引用的旧的。
浅拷贝(影子克隆):只复制基本类型。

深拷贝(深度克隆):基本类+对象。
*/

//返回一个包含ArrayList中所有元素的数组
public Object[] toArray() {
 return Arrays.copyOf(elementData, size);
}

// 返回一个数组,使用运行时确定类型,该数组包含在这个列表中的所有元素
//(从第一到最后一个元素)
// 返回的数组容量由参数和本数组中较大值确定
@SuppressWarnings(“unchecked”)
public <T> T[] toArray(T[] a) {
 if (a.length < size)
   // Make a new array of a’s runtime type, but my contents:
   return (T[]) Arrays.copyOf(elementData, size, a.getClass());
 System.arraycopy(elementData, 0, a, 0, size);
 if (a.length > size)
   a[size] = null;
 return a;
}

ArrayList相关问题

Integer.MAX_VALUE – 8 这里为什么要减去8?

主要是考虑到不同的JVM,有的VM会在加入一些数据头,当扩容后的容量大于MAX_ARRAY_SIZE,我们会去比较最小需要容量和MAX_ARRAY_SIZE做比较,如果比它大, 只能取Integer.MAX_VALUE,否则是Integer.MAX_VALUE -8。
这个是从jdk1.7开始才有的。

jdk1.8的无参构造函数和之前版本的构造函数有什么区别?

jdk1.6
publicArrayList(){    
   this(10);    
}

jdk1.7
publicArrayList(){    
   super();    
   this.elementData = EMPTY_ELEMENTDATA;    
}

jdk1.8
publicArrayList(){    
   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    

}


对比下可以看出:jdk1.6的无参构造方法(默认构造方法)构造的ArrayList的底层数组elementData大小(容量)默认为10;从1.7开始,无参构造方法构造的ArrayList的底层数组elementData大小默认为0。

java集合类在jdk1.7版本基本上都有一种改动:懒初始化。懒初始化指的是默认构造方法构造的集合类,占据尽可能少的内存空间(对于ArrayList来说,使用空数组来占据尽量少的空间,不使用null是为了避免null判断),在第一次进行包含有添加语义的操作时,才进行真正的初始化工作。

1.7开始的ArrayList,默认构造方法构造的实例,底层数组是空数组,容量为0,在进行第一次add/addAll等操作时才会真正给底层数组赋非empty的值。如果add/addAll添加的元素小于10,则把elementData数组扩容为10个元素大小,否则使用刚好合适的大小(例如,第一次addAll添加6个,那么扩容为10个,第一次添加大于10个的,比如24个,扩容为24个,刚好合适)

1.8版本,默认构造的实例这个行为没有改变,只是用的数组名字变了。

jdk1.6中扩容算法的缺陷

(由于jdk1.7和jdk1.8在扩容算法方面差别不大,所以下面没有严格区分)
//jdk1.6
publicvoidensureCapacity(int minCapacity){  
   modCount++;  
   int oldCapacity = elementData.length;  
   if (minCapacity > oldCapacity) {  
       Object oldData[] = elementData;  
       int newCapacity = (oldCapacity * 3)/2 + 1;  
       if (newCapacity < minCapacity)  
           newCapacity = minCapacity;  
       // minCapacity is usually close to size, so this is a win:  
       elementData = Arrays.copyOf(elementData, newCapacity);  
   }  
}

从上面的代码可以看出jdk1.6的ensureCapacity方法只是简单进行了逻辑上的操作,没有过多考虑int型溢出的问题,从1.7开始对这个进行了完善。

而且没考虑入参minCapacity可能因为int溢出变为负数。这个方法可以外部手动调用,手动扩容传入负数这个肯定是应该拦截掉的。但是自动扩容会因为int溢出产生负数,碰到这种情况时应该特殊处理,而不是什么都不做,等着后面抛出一个ArrayIndexOutOfBoundsException。

还有就是下面这句代码会造成过早溢出
int newCapacity = (oldCapacity * 3)/2 + 1;

虽然上面这行代码和1.7开始的oldCapacity + (oldCapacity >> 1) 差不多,都是相当于1.5倍,但实际上是有区别的。

这里主要有两个区别
第一个区别是jdk1.6的乘除运算的数学结果比后面一个大1比如oldCapacity=10,1.6的算法得到16,1.7开始的算法得到15,这个影响不大;
第二个区别就是两者在数字比较大时运算结果不一样,比如oldCapacity=10^9,这个数和Integer.MAX_VALUE位数一样,用1.6的算法得到的会是错误的-647483647,用1.7的则是正确的1500000000,这时候明明可以1.5倍扩容,但是jdk1.6却用的是按需扩容。

ensureCapacity(称之为手动,是因为此方法是public的,可以外部手动调用)。
在1.6版本是只有这个手动的方法,内部自动操作也是调用这个方法,1.7开始进行了区分,并且进一步改进了扩容操作。
  • 从1.7开始将内部扩容和外部可以调用的扩容方法分开了,通过源码可以看出:外部调用的手动扩容方法ensureCapacity要多一个判断条件 minCapacity > minExpand,这个判断条件拦截掉负数的minCapacity,这样调用内部扩容ensureCapacityInternal方法时,minCapacity一定是正数;内部扩容方法直接就用minCapacity – elementData.length > 0判断,此条件可以检测出int型溢出,碰到溢出最后会抛出一个OOM错误。jdk1.7用OOM,这比jdk1.6用ArrayIndexOutOfBoundsException更好,因为此时数组大小超出了虚拟机对数组的限制,虚拟机无法处理这种情况了,抛出一个ERROR是合理的。
  • 使用这行代码
newCapacity = oldCapacity + (oldCapacity >> 1);

这行代码不仅仅是使用位运算加快执行速度,上面说了,这种做法才是对的,是真正的1.5倍。不仅仅因为那一个大小的差别,更重要的是避免过早出现int溢出的情况,保证了内部自动扩容会尽量按规定的策略执行。同时整个扩容处理流程中多增加了几处if判断,对各种情况处理更加完善。

为什么ArrayList自动容量扩充选择扩充1.5倍?

这种算法构造出来的新的数组长度的增量都会比上一次大( 而且是越来越大) ,避免频繁newInstance 的情况。

为什么ArrayList 不适合频繁插入和删除操作?

由上面分析的增加删除方法可以看出在ArrayList中经常会调用 System.arraycopy 这个效率很低的操作来复制数组,所以导致ArrayList在插入和删除操作中效率不高。


丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:Java集合之ArrayList源码解析(下)
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00