原创

它来了它来了,栈底层(Vector)源码解析

栈源码介绍

栈在java编程中算是用的比较多的一种数据结构了,栈是一种数组型态的数据结构,具有先进后出的特点,也就是后来进入的元素,在弹出的时候是优先弹出的。所以栈也经常被用作逆序输出,括号匹配等情况。

从内部的结构来看,栈是vector的子类,说到vector,大家可能不怎么熟悉,确实接触的不多,但是平时它常常拿来与ArrayList作比较,而比较的原因大部分也是因为ArrayList是线程不安全的,而vector是线程安全的。 Stack在Vector的基础上主要做了以下方法的增加

	//stack的添加功能,添加到数组的末尾,调用的是vector的addElement()方法,返回传入的对象
    public E push(E item) {
        addElement(item);

        return item;
    }
    
    //stack具体实现增加的方法  
    public synchronized void addElement(E obj) {
    	//修改后modCount+1 ,modCount类似于一个版本号标识符一样的存在,在使用interator进行初始化后
    	//中途使用外部方法对数组进行改变后,在调用iterator方法时与iterator初始化时设定的
    	//expectedModCount进行比较,如果不一致则会报ConcurrentModificationException
        modCount++;
        //判断是否需要扩容
        ensureCapacityHelper(elementCount + 1);
        //扩容完毕后,将对象存入数组,并使容量 + 1
        elementData[elementCount++] = obj;
    }
	//判断是否需要扩容
    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code 如果传入的最小容量>当前数组的长度,那么认为需要扩容
        if (minCapacity - elementData.length > 0)
        	//扩容方法
            grow(minCapacity);
    }

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
     //设定最大数组容量为2的31次 - 1 - 8;
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
	//扩容 传入需要判断扩容的容量
    private void grow(int minCapacity) {
        // overflow-conscious code
        //获取存放元素的数组容量大小
        int oldCapacity = elementData.length;
        //生成新的容量,旧的容量值 + (判断构造函数传入的自增容量是否 > 0,如果 <= 0 则使用旧的容量)
        //所以如果不指定自增容量,那么新的容量 = 2 * 旧的容量
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        //如果新的容量 - 旧的容量 < 0
        if (newCapacity - minCapacity < 0)
        	//那新的值就还是等于旧值(ps:那排除了负数的情况下 什么时候 2 * 旧的容量 < 旧的容量呢)?
        	//解答:旧容量超过或等于2的30次方的时候,2倍的旧容量就超过int最大值。会变为负数
            newCapacity = minCapacity;
        //如果新的容量已经超过了既定的数组最大容量值。
        if (newCapacity - MAX_ARRAY_SIZE > 0)
        	//这里是调用了方法进行判断旧值,如果大于了数组既定最大值,就设置为int最大值
            newCapacity = hugeCapacity(minCapacity);
        //将旧的数组中的元素赋值到新的扩容后数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    //pop()方法,将最后进入的元素进行弹出,通过synchronized进行对当前对象的方法进行同步
    //防止两个线程同时进行删除操作出现问题。
    public synchronized E pop() {
        E       obj;
        //调用size()函数,返回当前的容量大小
        int     len = size();
		//将栈顶的元素赋值给obj,也就是最后插入的元素
        obj = peek();
        //将栈中最后的元素进行删除
        removeElementAt(len - 1);
		//返回之前栈顶的元素
        return obj;
    }
    //返回栈顶的元素
    public synchronized E peek() {
        int     len = size();
		//如果长度为0,则报错
        if (len == 0)
            throw new EmptyStackException();
        //获取最后一个元素
        return elementAt(len - 1);
    }  
	
	//删除对应位置的元素,由于是public修饰符,需要进行较多的判断越界等。
    public synchronized void removeElementAt(int index) {
    	//操作版本号 + 1
        modCount++;
        //如果需要删除的元素的长度已经和数组长度一样甚至更长
        if (index >= elementCount) {
        	//报数组越界异常
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }//如果传入的index < 0 ,数组越界
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        //这一块的代码下面画了图,可以根据图一起看比较好理解
        // j代表的意思是移动了几个元素。因为我们是按照数组的下标进行删除,不一定只删除最后一个元素
        //也有可能删除中间的元素,那么势必要造成后面元素的迁移,j就代表后面需要迁移几个元素
        int j = elementCount - index - 1;
        //如果j大于0,就代表删除的不是最后一个元素,需要进行迁移
        if (j > 0) {
        	//1.elementData:源数组, index + 1:迁移开始的下标,2.elementData:目标数组
        	//index:被迁移的下标, j:迁移的数组长度
        	//将index + 1 后面的 j 个长度的元素 复制到 index 位置上,就相当于从index开始向前移动
        	//了 j 个元素  如果不是很明白可以看图..(可能看了之后就更不明白了) 
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        //将长度 - 1 
        elementCount--;
        //将最后一个元素设置为null,表示清除,并且清除它的引用,表示它可以被垃圾回收了。
        elementData[elementCount] = null; /* to let gc do its work */
    }

来贴一下System.arraycopy(elementData, index + 1, elementData, index, j); 方法的过程。

首先是要删除index = 3 的元素,正巧值也是3,所以我们要将下标为3后面的元素往前移动一格,具体要移动几个元素就得看删除的元素的位置了,所以就有 j = elementCount - index - 1; 然后将index + 1后面的元素一起拷贝到index的位置就行。最后将最后的元素置为null,表示删除。(字丑勿怪)

在这里插入图片描述

来看看剩下的栈的原生代码

	//判断当前的栈是否为空
    public boolean empty() {
    	//对内部的元素长度进行等于0的判断。
        return size() == 0;
    }    
	//进行搜索某个元素的位置,返回在栈中的数组下标
    public synchronized int search(Object o) {
    	//调用lastIndexOf(o)查看是否存在这个值
        int i = lastIndexOf(o);
		//如果得到的下标是>=0的
        if (i >= 0) {
        	//返回长度减去下标的值...没错..用当前的长度减去了传回来的下标值。然后返回..为啥不直接返回下标呢
            return size() - i;
        }
        //不然返回-1.
        return -1;
    }    
    //传入需要定位的元素
    public synchronized int lastIndexOf(Object o) {
    	//调用重载的方法,传入需要的元素和最大的下标。 表示是在整个数组中查询
        return lastIndexOf(o, elementCount-1);
    }
	//传入需要定位的元素和最大的下标  这也是个public方法,可以由我们直接调用
    public synchronized int lastIndexOf(Object o, int index) {
    	//如果传入的下标值>=总长度,则抛出异常
        if (index >= elementCount)
            throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
		
		//如果传入的元素是null
        if (o == null) {
        	//定位到需要定义的下标,从后往前遍历
            for (int i = index; i >= 0; i--)
            	//如果值为null
                if (elementData[i]==null)
                	//返回下标
                    return i;
        } else {
        	//如果不为null ,也是一样的遍历
            for (int i = index; i >= 0; i--)
            	//由于==比较的是引用地址,所以这里换成了equals比较
                if (o.equals(elementData[i]))
                	//如果相同,返回对应的下标值
                    return i;
        }
        //如果找不到。返回-1
        return -1;
    }

Stack老东家Vector介绍

要说Vector在哪里最常出现....我估计是在面试里..每每问到线程安全的问题,可能Vector就是其中之一。

Vector和ArrayList比较相似,内部都是通过一个容量能动态增长的数组来实现,但是Vector是线程安全的,内部几乎对所有对外开放的方法都进行Synchronized进行修饰,保证线程安全。 老规矩看看这个Vector是怎么构成的~

因为上面栈的大部分操作方法基本最终调用都是在Vector中调用,都已经介绍过来,就简单的介绍下Vector的构造和初始参数,有个更深的理解。

	//初始化定义数组,存放元素的数组
    protected Object[] elementData;
    //表示当前存放的元素个数
    protected int elementCount;
    //扩容的数量
    protected int capacityIncrement;
    //有参构造,指定初始的容量和扩容递增的容量
    public Vector(int initialCapacity, int capacityIncrement) {
    	//调用AbstractList的无参构造
        super();
        //如果传入的初始化容量<0,则报异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        //为定义的数组生成在堆中的实例,并设置初始容量
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
    
    //设置初始值
    public Vector(int initialCapacity) {
    	//调用上面的有参构造,当扩容增长参数<=0的时候,每次扩容都会变为原来的2倍。
        this(initialCapacity, 0);
    }
	//无参构造,默认10容量。
    public Vector() {
        this(10);
    }
    //传入对应的集合类,要求集合内部的元素需要继承外部定义的Vector存储的类型或者相同类型。
    public Vector(Collection<? extends E> c) {
    	//获取传入集合的数组
        elementData = c.toArray();
        //获取传入数组的容量
        elementCount = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //这里一般情况下获取到的数组都是object类型的,因为我们在创建的时候默认内部都是Object类型。
        //但是有一种情况,比如我们先生成的一个Integer[] nums = new Integer[1];
        //然后通过Arrays.asList();生成的列表,传入后生成的数组,就是Integer类型的。
        //所以因为这个bug,需要将原本不是Object类型的数组重新转换为Object类型。(1)可以看看下面的试验
        if (elementData.getClass() != Object[].class)
        	//将旧的数组中的值赋值到新的Object数组中。
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
    }

举个public Vector(Collection<? extends E> c) 构造的例子,可以存入集合类并且是继承了当前Vector类型的子类或者本身。如图中,因为ArrayList的父类继承了Collections类,所以ArrayList可以直接转化为Vector,ThreadKKK 继承了 exam1 这个类,元素也就变成父类的exam1元素。

在这里插入图片描述

主要来验证下上面的if (elementData.getClass() != Object[].class) 的结果。可以看到结果,生成的是Integer类型,而我们生成的List,则是Object类型。 所以源码中需要进行转换。

在这里插入图片描述

再来介绍一些平时使用不多的方法。虽然用的不多,但多了解一点可能对代码的设计有很大提升

	//设置Vector的长度,传入新的长度
    public synchronized void setSize(int newSize) {
    	//序列号+1,代表修改次数
        modCount++;
        //如果新的长度大于原来的长度
        if (newSize > elementCount) {
        	//那就进行扩容的处理,具体看上方实现的方法
            ensureCapacityHelper(newSize);
        } else {
        	//如果小于现在的长度,那么就代表是缩容,需要删除多余的元素
        	//从新的长度开始,到原来的长度
            for (int i = newSize ; i < elementCount ; i++) {
            	//将这些值都设置为null,代表清除
                elementData[i] = null;
            }
        }
        //将原有的长度设置为新的长度。
        elementCount = newSize;
    }
    
    //这个方法应该比较常用到,判断一个元素是否在数组中存在
    public boolean contains(Object o) {
    	//调用indexOf()进行判断,indexOf如果不存在会返回-1,所以与>=0进行判断
    	//传入查询对象和开始的下标
        return indexOf(o, 0) >= 0;
    }
 	//定位查看元素是否存在,如果存在返回下标,不存在返回-1
     public int indexOf(Object o) {
        return indexOf(o, 0);
    }   
	//对应着前两个方法的实现,index代表开始查询的位置
    public synchronized int indexOf(Object o, int index) {
    	//如果传入查询的对象是null
        if (o == null) {
        	//通过遍历对null使用==判断,使用equals()会报错
            for (int i = index ; i < elementCount ; i++)
                if (elementData[i]==null)
                	//如果找到对应的下标后返回下标
                    return i;
        } else {
            for (int i = index ; i < elementCount ; i++)
            	//通过equals对对应的值进行判断是否相同
            	//使用==直接判断的是目标对象的地址。
            	//举个例子,Integer在-128到127之间使用的是常量池中的引用,但是如果超过127
            	//那么则是一个新的地址对象,即使是相同的值,使用==也会返回false。
            	//这也是个坑,往往在项目中,总是忽略这些,埋雷。
                if (o.equals(elementData[i]))
                    return i;
        }
        //如果没有找到则返回-1.
        return -1;
    }
	//将一个对应的属性存入到目标位置
    public synchronized void setElementAt(E obj, int index) {
    	//如果所定的目标位置大于现有的元素长度,则报数组越界异常
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        //设置对应数组的位置为新元素
        elementData[index] = obj;
    }
    //和上面方法几乎是一样的,只是会返回原来的元素。并设置新的元素
    public synchronized E set(int index, E element) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
	//在指定的位置插入指定的元素
    public synchronized void insertElementAt(E obj, int index) {
    	//序列号+1, 代表指定的次数
        modCount++;
        //如果插入位置的元素大于元素总长度,则报数组越界异常
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        //首先进行数组扩容判断,如果到达数组长度的临界值,则进行扩容处理
        ensureCapacityHelper(elementCount + 1);
        //系统调用将原来数组的index位置后面的数据,复制到index+1往后。具体可以看之前的图解
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        //将index的位置赋值给新值
        elementData[index] = obj;
        //元素个数+1
        elementCount++;
    }
	//这个方法和上面的方法最大的区别是这个方法只能在末尾进行添加,所以不会涉及到数组移动的情况
    public synchronized void addElement(E obj) {
        modCount++;
        //检查扩容
        ensureCapacityHelper(elementCount + 1);
        //当前的位置赋值并且长度+1
        elementData[elementCount++] = obj;
    }
    //最后再来看一下clone方法
    //Vector的clone方法重写了Object类的clone方法,并对其做了改装
    public synchronized Object clone() {
        try {
            @SuppressWarnings("unchecked")
            	//首先是根据父类Object的clone方法进行浅拷贝了一个对象
            	//浅拷贝的对象虽然也是一个新的对象,但是内部的引用还是指向的原对象
                Vector<E> v = (Vector<E>) super.clone();
            //所以将原来的数组复制一份传给新拷贝出来的Vector的数组。
            v.elementData = Arrays.copyOf(elementData, elementCount);
            //将新vector的modCount值设置为0
            v.modCount = 0;
            //返回新Vector
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }
    //这里Vector的clone方法相当于是一个深拷贝了,不仅创建了新的对象,还将内部的引用也重新创建。

这里也再复习一次浅拷贝,我们重新创建一个缩略的集合类,用来验证浅拷贝。

public class CopyList implements Cloneable {

    Integer[] nums;
    int count;
    public CopyList(){
        nums = new Integer[10];
    }

    public void add(Integer num){
        nums[count++] = num;
    }

    public void set(int index, Integer num){
        nums[index] = num;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for(int i = 0; i < count; i++){
            if(i == count - 1){
                sb.append(nums[i]);
                break;
            }
            sb.append(nums[i]);
            sb.append(", ");
        }
        sb.append(']');
        return sb.toString();
    }

    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }
}

可以看见调用的结果,克隆后,修改原列表的内容,新克隆的内容也会被修改,因为数组的引用是同一个。

在这里插入图片描述

我们再来看看Vector做的深拷贝,Vector直接将内部的数组进行重新new了一个,所以克隆对象内部的数组和原来对象的数组不是同一个,但是数组内部的元素引用,却是同一个,可能看到这里会有点晕。我们直接上代码图。

    public static void main(String[] args) {
        //新建Vector列表,用来存我们自定义的CopyList列表
        Vector<CopyList> vector = new Vector<>();
        //创建copyList
        CopyList copyList = new CopyList();
        //往copyList中加值
        copyList.add(3);
        copyList.add(5);
        //将copyList添加到vector中
        vector.add(copyList);
        System.out.println("初始化的vector:" + vector);
        //生成一个克隆的对象
        Vector<CopyList> clone = (Vector<CopyList>) vector.clone();
        //输出克隆对象
        System.out.println("这是克隆的数组!" + clone);
        //然后往生成的copyList中加值
        copyList.set(0, 100);
        //输出两个列表
        System.out.println("我是旧的:" + vector);
        System.out.println("我是新的:" + clone);
        //可以发现内部的元素没有被新建
        //再新建一个copyList
        CopyList copy2 = new CopyList();
        //传值
        copy2.add(44);
        //老的列表添加copy2
        vector.add(copy2);
        //输出结果,可以发现,数组是新建的,两个不一样了。但是数组里的值是复制的,还是引用的同一个对象
        System.out.println("我是老的:" + vector);
        System.out.println("我是新的:" + clone);
    }

在这里插入图片描述

只能说Vector克隆的不太彻底把。如果一定要生成两个全新的对象,那要是内部的对象无限套娃(数组套数组),那需要保证效率的情况下设计难度肯定也很大。

结束语

栈和vector的解析差不多就到这了,这篇主要解析的还是内部方法的如何实现与原理,栈或vector的应用层面没有太多的涉及。

虽然讲的没多深,并没有涉及到设计思想这一方面,功力不够,主要还是希望做个记录,在以后复习的时候可以查阅,毕竟每次都从头看还是很累的O(∩_∩)O哈哈~。 老样子哪里写错了评论直接指出就行(痛骂)。

ps:招聘季来辣,如果哪家厂还有招人....可以给小弟一个内推嘛...(卑微).

java
Vector

  • 作者:LinJy(联系作者)
  • 发表时间:2020-09-01 22:12
  • 版权声明:自由转载-非商用-非衍生-保持署名(null)
  • undefined
  • 评论

    留言