Java中ArrayList和Vector解析

最近在恶补数据结构和算法，顺带着把ArrayList和Vector看了看，因此写了这篇文章记录下。我们知道ArrayList和Vector底层数据结构都是数组，而数组这种数据结构一旦创建它的容量就不可改变了，而我们平常使用的这两个类却一直能插入元素，这是为什么呢？下面我们开始按照API一个一个解析，注意我们不可能把每个API都面面俱到，因此只介绍一些常用的，其它的自行查看

目录

  • ArrayList
    • 构造
    • add
    • remove
    • clear
    • set
    • get
    • indexOf
    • lastIndexOf
    • contains
    • size
    • isEmpty
  • Vector
    • 构造
    • add
    • remove
    • clear
    • set
    • get
    • indexOf
    • lastIndexOf
    • contains
    • size
    • isEmpty
  • 总结

一、ArrayList

构造

transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final Object[] EMPTY_ELEMENTDATA = {};

public ArrayList() {
    //初始化一个没有容量数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        //传入的容量如果大于0，初始化一个自定义容量的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //传入的容量等于0，初始化一个没有容量的数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

add

假设我们使用的是无参的构造，即初始容量为0

//成员变量，默认值是0
private int size;

public boolean add(E e) {
    //扩充容量，size+1是我们需要的容量
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //按照下标存入数组，存入后数组中元素个数size就会加1
    elementData[size++] = e;
    return true;
}

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY = 10;

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    //添加第一个元素时，会直接把我们需要的容量改为10
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //决定是否需要扩充容量
    ensureExplicitCapacity(minCapacity);
}

//记录修改次数
protected transient int modCount = 0;

private void ensureExplicitCapacity(int minCapacity) {
    //modCount只是记录修改次数
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        //当我们需要的容量大于数组中现有的容量时，需要扩充
        grow(minCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    //获取当前数组的容量
    int oldCapacity = elementData.length;
    //扩充为当前数组容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //扩充后的容量还是小于我们需要的容量，就直接扩充为我们需要的容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //扩充后的容量大于Integer.MAX_VALUE - 8，就采用hugeCapacity方法中的策略扩充
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //该方法最终会复制旧的数组中的数据项到新的扩充后的数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

上面方法中，主要有hugeCapacity方法和Arrays.copyOf方法，我们先看hugeCapacity方法

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //判断我们需要的容量是否大于Integer.MAX_VALUE - 8
    //大于就扩充容量为Integer最大值，小于就扩充为Integer.MAX_VALUE-8
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

我们再看Arrays类的静态方法copyOf

public static <T> T[] copyOf(T[] original, int newLength) {
    //调另一个重载方法
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    //创建一个新的扩充容量后的数组
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    //将原始数组从0索引开始复制所有的数据项，到新的数组中，新的数组从0开始接收数据项
    //其实就是复制旧的数组的数据项到新的扩充后的数组中
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

从上面代码我们可以得到ArrayList的扩充容量机制，但是为什么要有这么一个扩容机制呢？其实这是由数组本身这种数据结构所决定的，数组一旦创建，它的容量就固定了，因此只能猜测它的大小，而我们却又不知道用户到底有多少数据项，猜大了浪费空间，猜小了又不能完全存储用户的数据。所以我们想到达到随着数据项的插入进行动态扩展的目的，就必须创建一个新的容量的数组，并且把旧的数组的数据项复制到新的数组中。ArrayList大体采用1.5倍扩容，并且并不是每次添加元素都要扩容，这是考虑到创建新数组，复制数据的效率问题，以空间换时间。具体的扩容策略见下表：

添加第N个元素 添加后的数组容量
只创建不添加 初始容量0
1 10
2 10
3 10
... 10
11 15
12 15
... 15
16 22
17 22
... ...
m Integer.MAX_VALUE - 8
... Integer.MAX_VALUE - 8
Integer.MAX_VALUE - 8 Integer.MAX_VALUE - 8
Integer.MAX_VALUE - 7 Integer.MAX_VALUE
... Integer.MAX_VALUE

remove

remove有两个重载的方法，一个是根据索引开始移除，一个是根据元素开始移除，其实归根到底都是根据索引移除，先看根据索引移除

public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //修改次数+1
    modCount++;
    //获取数组中对应索引的元素，最后直接返回
    E oldValue = (E) elementData[index];
    //需要移动的元素数量
    int numMoved = size - index - 1;
    //判断是否需要移动，比如index为最后一个元素时，只需要最后一个元素置为null即可，不需要移动
    if (numMoved > 0)
        //从数组中删除项的后一位开始复制之后的所有元素，复制到数组中，数组从删除项的那一位开始接收
        //即删除项后面的所有元素都向前移动一位
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //最后一个数据项置为null，尽快让GC回收，并且ArrayList的size减一
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

再看另外一个根据元素移除

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //注意这个数组是可以重复的，这里只是线性查找到元素的第一个索引，然后调fastRemove方法移除
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                //注意这个数组是可以重复的，这里只是线性查找到元素的第一个索引，然后调fastRemove方法移除
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    //修改次数+1
    modCount++;
    //需要移动的元素数量
    int numMoved = size - index - 1;
    //判断是否需要移动，比如index为最后一个元素时，只需要最后一个元素置为null即可，不需要移动
    if (numMoved > 0)
        //从数组中删除项的后一位开始复制之后的所有元素，复制到数组中，数组从删除项的那一位开始接收
        //即删除项后面的所有元素都向前移动一位
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //最后一个数据项置为null，尽快让GC回收，并且ArrayList的size减一
    elementData[--size] = null; // clear to let GC do its work
}

整体删除过程如下图

ArrayList.png

clear

public void clear() {
    //修改次数+1
    modCount++;
    //所有元素置为null，尽快让GC回收
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    //元素个数置为0
    size = 0;
}

set

public E set(int index, E element) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //获取数组中对应索引的旧元素，最后直接返回
    E oldValue = (E) elementData[index];
    //直接插入新的元素到数组中指定的索引
    elementData[index] = element;
    return oldValue;
}

get

public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //返回数组中对应索引的元素
    return (E) elementData[index];
}

indexOf

public int indexOf(Object o) {
    if (o == null) {
        //ArrayList中的元素是可以重复的，这里从0索引开始线性查找元素的第一个索引，直接返回
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        //ArrayList中的元素是可以重复的，这里从0索引开始线性查找元素的第一个索引，直接返回
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    //找不到就返回-1
    return -1;
}

lastIndexOf

public int lastIndexOf(Object o) {
    if (o == null) {
        //ArrayList中的元素是可以重复的，这里从最后一个索引开始线性查找元素，
        //找到第一个索引就直接返回，因此这里返回的是元素的最后一个索引
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        //ArrayList中的元素是可以重复的，这里从最后一个索引开始线性查找元素，
        //找到第一个索引就直接返回，因此这里返回的是元素的最后一个索引
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    //找不到就返回-1
    return -1;
}

contains

public boolean contains(Object o) {
    //ArrayList是否包含某个元素，其实就是看indexOf方法能否找到某个元素的索引
    return indexOf(o) >= 0;
}

size

private int size;

public int size() {
    //add、remove、clear等都会对元素个数修改
    return size;
}

isEmpty

public boolean isEmpty() {
    //ArrayList是否为空，即判断元素个数size是否等于0
    return size == 0;
}

二、Vector

由于Vector和ArrayList很多方法的实现都是一样的，部分只是在方法上加了同步，因此只介绍和ArrayList不同的API

构造

假设我们调的是无参构造

protected Object[] elementData;
//扩充容量时的增长量
protected int capacityIncrement;

public Vector() {
    //调一个参数的构造
    this(10);
}

public Vector(int initialCapacity) {
    //initialCapacity为10，调两个参数的构造
    this(initialCapacity, 0);
}

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    //第一个参数为10表示初始化数组的容量，第二个参数为0表示扩充容量时的增长量
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    //初始化容量为10的数组
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

可以看到Vector对象一创建就会初始化一个容量为10的数组，而ArrayList是初始化一个容量为0的数组，添加第一个元素才会扩充容量为10

add

protected int elementCount;

//加了同步修饰符
public synchronized boolean add(E e) {
    //修改次数+1
    modCount++;
    //扩充容量，elementCount+1是我们需要的容量，elementCount就是ArrayList中的size
    ensureCapacityHelper(elementCount + 1);
    //按照下标存入数组，存入后数组中元素个数elementCount就会加1
    elementData[elementCount++] = e;
    return true;
}

private void ensureCapacityHelper(int minCapacity) {
    //需要的容量比现有的容量大的话，需要扩充容量
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //由于我们调的是无参构造，这里扩充容量的增长量capacityIncrement为0，
    //所以这里是扩充为原来的2倍，而ArrayList是扩充1.5倍
    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);
}

Vector和ArrayList的扩容机制稍有不同，ArrayList不添加元素时容量为0，Vector不添加元素时容量为10，并且ArrayList是1.5倍扩容，Vector是2倍扩容，具体见下表：

添加第N个元素 添加后的数组容量
只创建不添加 10
1 10
2 10
3 10
... 10
11 20
12 20
... 20
21 40
22 40
... ...
m Integer.MAX_VALUE - 8
... Integer.MAX_VALUE - 8
Integer.MAX_VALUE - 8 Integer.MAX_VALUE - 8
Integer.MAX_VALUE - 7 Integer.MAX_VALUE
... Integer.MAX_VALUE

remove

一个根据索引移除，一个根据元素移除，这两个方法和ArrayList一样，只是加了synchronized修饰符

clear

和ArrayList一样，只是加了synchronized修饰符

set

和ArrayList一样，只是加了synchronized修饰符

get

和ArrayList一样，只是加了synchronized修饰符

indexOf

比ArrayList多了一个方法，并且加了同步，而且可以从指定索引向后开始查找，这种设计要比ArrayList要好

public int indexOf(Object o) {
    return indexOf(o, 0);
}

//加了同步，并且可以从指定索引向后开始查找
public synchronized int indexOf(Object o, int index) {
    if (o == null) {
        for (int i = index ; i < elementCount ; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = index ; i < elementCount ; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

lastIndexOf

比ArrayList多了一个方法，并且加了同步，而且可以从指定索引向前开始查找，这种设计要比ArrayList要好

public synchronized int lastIndexOf(Object o) {
    return lastIndexOf(o, elementCount-1);
}

//加了同步，可以从指定索引向前开始查找
public synchronized int lastIndexOf(Object o, int index) {
    if (index >= elementCount)
        throw new IndexOutOfBoundsException(index + " >= "+ elementCount);

    if (o == null) {
        for (int i = index; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = index; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

contains

和ArrayList一样，只是加了synchronized修饰符

size

和ArrayList一样，只是加了synchronized修饰符

isEmpty

和ArrayList一样，只是加了synchronized修饰符

三、总结

相同之处

  • 都实现了List接口
  • 底层数据结构都是数组
  • API的实现几乎都是一样的
  • 扩容机制是一样的，由于数组这种数据结构，在创建时它的容量就已经确定，因此想要随着数据项的插入数组容量发生动态变化，就需要创建一个新容量的数组，把旧数组中的所有元素拷贝到新容量的数组中，这就是扩容机制，但是它们的扩容策略稍有不同
  • 查询和修改都比较快，增删都比较慢。有索引的话查询和修改都会很快，但是扩容的话，需要创建新的数组并复制旧数组的元素到新数组中，因此添加会比较慢。移除元素的话，需要后面的元素前移，因此也比较慢

不同之处

  • 扩容策略稍有不同，ArrayList对象创建后会初始化一个容量为0的数组，添加第一个元素才会扩充容量为10，并且是1.5倍扩容，而Vector对象一创建后就会初始化一个容量为10的数组，并且是2倍扩容
  • ArrayList是线程不安全的，Vector是线程安全的
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 199,711评论 5赞 468
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 83,932评论 2赞 376
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 146,770评论 0赞 330
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 53,799评论 1赞 271
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 62,697评论 5赞 359
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,069评论 1赞 276
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,535评论 3赞 390
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,200评论 0赞 254
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,353评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,290评论 2赞 317
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,331评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,020评论 3赞 315
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,610评论 3赞 303
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,694评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,927评论 1赞 255
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,330评论 2赞 346
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 41,904评论 2赞 341

推荐阅读更多精彩内容

  • Java 集合类实现原理
    Collection & Map Collection 子类有 List 和 Set List --> Array...
    任教主来也阅读 3,140评论 1赞 9
  • java笔记
    java笔记第一天 == 和 equals ==比较的比较的是两个变量的值是否相等，对于引用型变量表示的是两个变量...
    jmychou阅读 1,480评论 0赞 3
  • Java 集合框架_Vector(源码解析)
    Vector集合是 jdk1.0 版本就提供的集合类，它的所有操作集合的方法，都进行了加锁(就是对方法使用sync...
    wo883721阅读 414评论 0赞 1
  • java 数据结构(3) ArrayList Vector
    转自Java中ArrayList类的使用方法ArrayList源码分析 一、什么是ArrayList ArrayL...
    合肥黑阅读 492评论 0赞 6
  • 我的新想法
    最近自己有时会处于纠结状态，不过经过一段时间的调整，好了很多。有些事情，慢慢的想清楚了。人有了些存量，彻底放弃，从...
    行者方圆阅读 317评论 0赞 0