专栏首页呼延Vector源码阅读

Vector源码阅读

前言

前面已经学习过ArrayList和LinkedList的区别,今天再来学习一下List<E>接口的另一个实现类Vector.

Vector 可以实现可增长的对象数组。与数组一样,它包含可以使用整数索引进行访问的组件。不过,Vector 的大小是可以增加或者减小的,以便适应创建 Vector 后进行添加或者删除操作。

Vector与ArrayList没有太大区别,都具有List<E>的基础功能,重要的是:Vector是同步的.也就是说,Vector可以用于多线程环境下,但是性能相比Arraylist要低一些.

源码阅读

定义

首先看一下Vector类的定义.

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

Vector 实现 List 接口,继承 AbstractList 类,所以我们可以将其看做列表,支持相关的添加、删除、修改、遍历等功能。

Vector 实现 RandomAccess 接口,即提供了随机访问功能,提供快速访问功能。在 Vector 我们可以直接访问元素。

Vector 实现了 Cloneable 接口,支持 clone() 方法,可以被克隆。

成员变量

protected Object[] elementData;

protected int elementCount;

protected int capacityIncrement;

elementData是保存数据的数组

elementCount是当前元素的数量

capacityIncrement是容量增量,当它小于或者等于0时,则每次需要增大容量时,向量的容量将增大一倍.

构造方法

    public Vector(int initialCapacity, int capacityIncrement) {

    }

    public Vector(int initialCapacity) {
    }


    public Vector() {
    }

    public Vector(Collection<? extends E> c) {

    }

Vector有四个构造方法,参数分别制定初始容量及初始增量.

默认的构造方法,初始容量为10,初始增量为0,即每次扩容时容量翻倍.

常用方法

###1.添加元素

/**
* 数组末尾添加一个元素
*/
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}
/**
* 设置某个index上的元素为传入值
*/
public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
/**
* 在指定的index插入一个元素,后续元素向后顺移
*/
public void add(int index, E element) {
    insertElementAt(element, index);
}
public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

###2.获取元素

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

###3.移除元素

public boolean remove(Object o) {
    return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

由于Vector内部使用数组实现,因此简单的增加删除获取元素都是对数组的简单操作,这里就不细讲了.

扩容

既然Vector是一个可以动态改变自己大小的数组,那么我们来看一下他是怎么实现动态扩容的.

public synchronized void ensureCapacity(int minCapacity) {
    if (minCapacity > 0) {
        modCount++;
        ensureCapacityHelper(minCapacity);
    }
}

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

这是和扩容相关的几个方法,前两个方法是用来检验当前是否需要扩容.

在添加元素时,会用当前数组中元素的个数+1进行检验,如当前个数+1 > 数组长度,则需要扩容,调用grow方法.

grow方法中:

  1. 旧的大小为当前数组长度
  2. 计算扩容后的大小,(oldCapacity+capacity/oldCapacity)
  3. 判断扩容后的size是否合法
  4. 调用Arrays.copy将当前所有值copy到新的数组.

后话

由于Vector内部使用数组实现,因此源码并不复杂.

同时,在学习源码的过程中我们可以发现,很多对数组进行操作的方法使用synchronized修饰,因此可以保证线程安全性,同时,synchronized会加锁,因此效率可能会相对于ArrayList低一些,在单线程的情况下建议还是使用ArrayList.

参考链接

http://wiki.jikexueyuan.com/project/java-enhancement/java-twentynine.html

完。

ChangeLog

2018-12-23 完成

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com


本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Top K问题

    如果你对上述两者的原理有所了解,可以继续往下看.如果不了解,可以点击链接先看一下基础~.

    呼延十
  • 简易却高效的hashmap实现

    我们每天都在使用HashMap,有没有想过,在很多情景下,HashMap做的其实没有特别好,他是一个很通用的k-v数据结构,却不一定在各个小方面都适合.因此我们...

    呼延十
  • Redis系列(八)底层数据结构之紧凑列表

    Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?

    呼延十
  • ArrayList源码学习

    写文章要有一定的顺序,按照一定的模块进行学习是比较好的学习习惯。跳跃式的学习很容易导致心态的变化。这不仅是学习过程的事情更是生活上的事情。因此还是按部就班,今天...

    用户5602455
  • k 阶斐波那契序列的第 m 项值的函数算法—C语言

    汐楓
  • C# 继承 基类和派生类基类的初始化C# 多重继承

    继承是面向对象程序设计中最重要的概念之一。继承允许我们根据一个类来定义另一个类,这使得创建和维护应用程序变得更容易。同时也有利于重用代码和节省开发时间。

    酱紫安
  • 1004: Xi and Bo

    渔父歌
  • 谈谈面试中的异或操作

    最近一直在面试,也做了各种各样的手写算法题,大部分时候面试官想要考察的只是候选人对常见算法的了解程度。有些题很难,通过一些骚操作可以达到更高的性能,比如最长回文...

    写代码的阿宗
  • PAT 甲级 1025 PAT Ranking

    1025. PAT Ranking (25) 时间限制 200 ms 内存限制 65536 kB 代码长度限制 16000 B 判题...

    ShenduCC
  • 算法导论第六章优先队列(二)

    优先队列可以说是堆的一个非常重要的应用,和堆对应,优先队列也分最小优先队列和最大优先队列。 优先队列是一种用来维护由一组元素构成的集合S的数据结构,其中每一个元...

    CloudDeveloper

扫码关注云+社区

领取腾讯云代金券