美文网首页Android知识程序员Android技术知识
Java中ArrayList和Vector解析

Java中ArrayList和Vector解析

作者: Zeit丶 | 来源:发表于2017-12-25 20:42 被阅读0次

最近在恶补数据结构和算法，顺带着把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是线程安全的

相关文章

网友评论

    本文标题：Java中ArrayList和Vector解析

    本文链接：https://www.haomeiwen.com/subject/hbrrgxtx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    Android知识

    程序员

    Android技术知识

    Android开发

    Android开发经验谈

    关于我们|服务条款|联系我们|Java中ArrayList和Vector解析|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！