文档章节

源码之ArrayList和Vector

yimingkeji
 yimingkeji
发布于 01/06 20:56
字数 1372
阅读 25
收藏 4

父类介绍

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

说明:

  • 继承AbstractList,实现List接口,提供了add、remove、indexOf、get等相关方法
  • 实现RandomAccess接口,提供了随机访问功能。在ArrayList中,我们即可以通过元素的序号快速获取元素对象;这就是快速随机访问。RandomAccess接口是一个标记接口,它并未定义方法。其目的是用于指示实现类具有随机访问特性,在遍历时使用下标访问较迭代器更快
  • 实现Cloneable,提供了克隆方法
  • 实现Serializable,支持序列化

属性

默认属性

//数组默认大小10
private static final int DEFAULT_CAPACITY = 10;
//默认数据 空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

其他属性

数据

transient Object[] elementData;

这里用transient修饰,是为了防止自动序列化。原因:

由于 ArrayList 是基于动态数组实现的,所以并不是所有的空间都被使用。因此使用了 transient 修饰,可以防止被自动序列化。

所以,ArrayList也自定义了序列化和反序列化方法,只序列化当前存放的数据

    private void writeObject(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) {
            throw new ConcurrentModificationException();
        }
    }

    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;
        s.defaultReadObject();
        s.readInt(); 

        if (size > 0) {
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // 反序列化,读取数据
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

大小

private int size;//ArrayList的数组大小

修改次数与快速失败

//修改次数 父类AbstractList所有
protected transient int modCount = 0;
//期望修改次数 父类AbstractList的内部类Itr所有
int expectedModCount = modCount;

说明

ArrayList的所有关于结构变化的操作(add、remove、addAll、removeRange和clear),都会让modCount++

而在私有内部类迭代器Itr中定义了变量expectedModCount和checkForComodification方法
private class Itr implements Iterator<E> {
    //期望的修改次数
    int expectedModCount = modCount;
    //修改检查方法()
    final void checkForComodification() {
        //如果修改数和期望修改数不一致,抛出异常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

好处:快速失败

如果在多线程环境中,使用迭代器操作ArrayList的时候可能造成修改次数不一致,每次迭代器更新数据前检查,来保证数据安全和一致,如果不一致能让迭代快速失败

添加元素

add(obj) 在数组尾部添加

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 扩容(如果必要),并且 modCount++
        elementData[size++] = e;//数组尾部添加元素
        return true;
    }

add(index, obj) 复制数组,效率很差

//在指定位置添加元素
public void add(int index, E element) {
    rangeCheckForAdd(index);//校验index是否大于数组长度或者小于0

    ensureCapacityInternal(size + 1);  // 扩容(如果必要),并且 modCount++
    //对数据进行复制,目的是把 index 位置空出来放本次插入的数据,并将后面的数据向后移动一个位置
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;//将插入的值放到指定位置index
    size++;//将 size + 1 
}

添加集合 addAll(),效率较差

public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);
		//数组复制和移动
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

修改元素 set

在指定位置设置新的值,并返回旧值

public E set(int index, E element) {
    rangeCheck(index);//检查index是否超过数组大小

    E oldValue = elementData(index);//获取到之前的值
    elementData[index] = element;//设置新值
    return oldValue;//返回之前的值
}

扩容

//扩容检测
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 当数组容量不足,调用grow进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//扩容
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;//获取当前容量大小
    int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量=当前容量的1.5倍
    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);
}

快速随机访问 get

public E get(int index) {
    rangeCheck(index);//检查index是否超过数组大小
    return elementData(index);//返回数组指定位置的元素
}

移除元素 remove 效率较差

给定位置移除

移除指定位置元素,返回被移除位置上的元素值

public E remove(int index) {
    rangeCheck(index);//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; //清除数组,让gc收集
    return oldValue;
}

给定元素值移除

public boolean remove(Object o) {
        if (o == null) {//移除null值
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {//移除非null值
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
	
	//快速移除,数组复制和移动
	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
    }

Vector

线程安全

Vector类似于ArrayList,是一个动态数组,只是它是一个线程安全的数组容器。它的add、set、remove方法都是用synchronized来修饰的。

扩容

//Vector的扩容,不是按1.5倍,二是1倍
private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //按原来的1倍扩容
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

© 著作权归作者所有

yimingkeji
粉丝 14
博文 47
码字总数 30840
作品 0
杭州
私信 提问
集合——Vector和ArrayList的比较

今天研究了一下Vector和ArrayList的源码,又加深了对这两个类的理解。 List接口下一共实现了三个类:ArrayList,Vector,LinkedList。LinkedList就不多说了,它一般主要用在保持数据的插入顺...

亚特兰缇斯
2015/03/16
20
0
java中List接口的实现类 ArrayList,LinkedList,Vector 的区别 list实现类源码分析

java面试中经常被问到list常用的类以及内部实现机制,平时开发也经常用到list集合类,因此做一个源码级别的分析和比较之间的差异。 首先看一下List接口的的继承关系: list接口继承Collectio...

分享达人
2016/03/13
0
0
Vector及LinkedList源码解析

1、本文主要内容 Vector及LinkedList介绍 Vector源码解析 LinkedList源码解析 总结 java容器这个系列,虽然较为简单,但本着有始有终的原则,还是必须要写下去。同时感觉一篇只写一个容器,实...

某昆
2018/07/22
0
0
Java集合-08之 再看 List

0.概要 之前已经了解了的全部内容(ArrayList, LinkedList, Vector, Stack)。 接下来再看 第1部分 List概括 先回顾一下List的框架图 List 是一个接口,它继承于Collection的接口。它代表着有序...

xidiancoder
2017/09/04
0
0
关于Android中Intent传递Serialzilable数据的问题

之前写程序,如果是队列数据的话,一般都是用ArrayList来作为存储介质,但是现在接手公司的新项目,因为之前这个公司是在windows mobile上实现的(也就是C写的),他们可能更习惯使用Vector,...

小小_小小
2014/05/20
423
0

没有更多内容

加载失败,请刷新页面

加载更多

MongoDB复制集

MongoDB复制集 2017年07月09日 19:36:01 zzm_ 阅读数 1 原文链接:http://blog.51cto.com/dreamlinux/1945705 MongoDB目前的高可用架构主要有主从、复制集、以及分片,单纯的主从技术几乎被淘...

linjin200
14分钟前
5
0
高防CDN是如何保障互联网安全?

DDoS攻击,一直是剪不断理还乱,而如何防御DDoS,也一直是网络安全的世纪难题。虽然CDN技术在不断增强,但更可怕的是DDoS攻击手段也在不断升级多元化,攻击渠道甚至更多种,所以普通的CDN加速...

云漫网络Ruan
15分钟前
5
0
springcloud 配置 springboot admin详解

1.配置pom 引入相关依赖 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-jetty</artifactId> </dependenc......

spirngbootcloudssm
16分钟前
3
0
Mockito 2 关于打标(stubbing)

请参考下面有关于打标的代码。 //You can mock concrete classes, not just interfaces LinkedList mockedList = mock(LinkedList.class); //stubbing when(mockedList.get(0)).thenReturn("......

honeymoose
18分钟前
4
0
kafka安装和启动

kafka的背景知识已经讲了很多了,让我们现在开始实践吧,假设你现在没有Kafka和ZooKeeper环境。 Step 1: 下载代码 下载1.1.0版本并且解压它。 > tar -xzf kafka_2.12-2.3.0.tgz> cd kafka_...

roockee
21分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部