菜鸡看不一样的Java集合源码-Vector源码分析

原文链接:blog.ouyangsihai.cn >> 菜鸡看不一样的Java集合源码-Vector源码分析

0 开篇

这篇文章应该是集合源码分析的开篇了,先从Vector开始主要是因为根据数据结构的顺序来的,大家也应该都知道,这也是集合中最简单的一种数据结构的实现了,因为Vetor的实现就是基于数组的,所以,对于大家都不陌生,从开始学习编程开始,最开始接触的应该就是数据这种最最简单的数据结构了。

因此,带着这种好奇心,看看最简单的数据结构,在Java的底层是怎么实现的呢?

1 问题

在开始之前, 我们可以想想几个关于数组的问题,看看Java是怎么解决的?

  • 数组怎么实现的复制?
  • 数组怎么实现的扩容?

这两个问题应该是在数组中经常都会遇到的,我们就带着这两个问题看看Java底层的实现。

2 菜菜源码分析

2.1 声明和属性

首先,我们看看Vetor这个类的声明,你可以先想想你理解的应该是怎么样的,是否跟Java底层的实现一样呢?

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

从这里可以发现,Vector集成自AbstractList,同时实现了List<E>, RandomAccess, Cloneable, java.io.Serializable这几个接口,同时,Vector也是用泛型来声明的。

我们看一下Vector的类图结构就更加的清楚了。

2.2 构造方法


    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }


    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }


    public Vector() {
        this(10);
    }


    public Vector(Collection<? extends E> c) {
        elementData = c.toArray();
        elementCount = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
    }

构造方法的实现非常的简单,有多个重载,可以直接创建空的Vector,也可以传入带有初始大小的Vector,或者直接从其他集合复制数据到Vetor生成。

2.3 扩容

在看其他方法之前,我们先看看扩容机制,因为其他的很多方法都需要用到这个机制。

首先传入最小的容量,调用下面的方法;

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

接着调用下面的方法判断传入的扩容容量是否比目前的Vetor容量大,如果更大,使用grow方法扩容;

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

capacityIncrement字段是在创建Vetor对象的时候可以选择传入,表示扩容增加的容量,这里的扩容方法是:如果capacityIncrement大于0,就增加这个容量,否则,加上原来Vector的容量;

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

    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;
    }

扩容机制知道了之后,我们就可以看其他的方法了。

2.4 添加元素

public synchronized void addElement(E obj) {
        //修改次数增加
        modCount++;
        //扩容
        ensureCapacityHelper(elementCount + 1);
        //添加元素
        elementData[elementCount++] = obj;
    }
  • 添加元素到指定位置
public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        //扩容
        ensureCapacityHelper(elementCount + 1);
        //复制:将elementData中的数据从index位置开始复制到elementData中去,位置是index + elementCount - index,所以正好腾出index位置插入元素
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        //插入元素
        elementData[index] = obj;
        elementCount++;
    }

System.arraycopy方法在这里解释一下。

方法原型是这样的;

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

这是一个native方法,作用:将原数组src从srcPos位置开始复制length长度的元素复制到dest目标数组的destPos位置开始的数组中,感觉有点绕口,举一个简单的例子。

System.arraycopy(users, 0, target, 0, users.length);/

这个意思是:将users中的0位置开始元素复制到target中,复制的长度为users.length。

2.5 删除指定位置元素

public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            //将原数组中的index + 1位置开始的元素复制到目标elementData中的index位置,长度为:j = elementCount - index - 1,说白了就是删除index位置的元素。
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        //数量减一,引用指向null,gc掉
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
    }

知道这个方法之后,你就会发现,其他的删除的方法都是基于这个方法,所以这里就不再做介绍了。

2.6 查找元素

//从index位置开始查找元素
public synchronized int indexOf(Object o, int index) {
        //如果元素为空,找到从index位置开始的第一个为null的元素的索引返回,如果不为空,找到第一个相等的元素的索引返回。
        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;
    }

知道这个方法之后,你就会发现,其他的查找的方法都是基于这个方法,所以这里就不再做介绍了。

3 小结

这里总结回到一下开篇的问题。

  • 数组怎么实现的复制?
    基本都是使用System.arraycopy方法实现。

  • 数组怎么实现的扩容?

如果capacityIncrement大于0,就增加这个容量,否则,加上原来Vector的容量。

4 Stack类简介

Stack是数据结构栈的实现的,因为是基于数组实现的,所以,在Java的集合中就是集成自Vetor类的,所以,Stack的实现就非常的简单了。

Stack类图

Stack类的方法

所以,下面我们简单的看一下这几个方法的实现。

Stack源码解析

  • push方法
public E push(E item) {
        addElement(item);

        return item;
    }

addElement方法继承自Vector类,这里就不再讲了。

  • peek方法

    public synchronized E peek() {
          int     len = size();
    
          if (len == 0)
              throw new EmptyStackException();
          return elementAt(len - 1);
      }
    
  • pop方法

    public synchronized E pop() {
          E       obj;
          int     len = size();
    
          obj = peek();
          removeElementAt(len - 1);
    
          return obj;
      }
    

removeElementAt方法集成自Vector类,上面已经讲过了。

stack比较简单,这里就将这么多!


 上一篇
java实现沙箱测试环境支付宝支付(demo)和整合微信支付和支付宝支付到springmvc+spring+mybatis环境全过程(支付宝和微信支付、附源码) java实现沙箱测试环境支付宝支付(demo)和整合微信支付和支付宝支付到springmvc+spring+mybatis环境全过程(支付宝和微信支付、附源码)
文章有不当之处,欢迎指正,如果喜欢微信阅读,你也可以关注我的微信公众号: 好好学java,获取优质学习资源。 源代码https://github.com/OUYANGSIHAI/sihai-maven-ssm-alipay 一、支付宝测
下一篇 
MySQL全文索引最强教程 MySQL全文索引最强教程
原文链接:blog.ouyangsihai.cn >> MySQL全文索引最强教程 MySQL全文索引支持三种模式,这三种模式的功能都不一样。 Natural Language 这种可以成为自然语言搜索,自然语言搜索将
  目录