Java集合源码分析(三)Vevtor和Stack

前言

  前面写了一篇关于的是LinkedList的除了它的数据结构稍微有一点复杂之外,其他的都很好理解的。这一篇讲的可能大家在开发中很少去用到。但是有的时候也可能是会用到的!

  注意在学习这一篇之前,需要有多线程的知识:

  1)锁机制:对象锁、方法锁、类锁

    对象锁就是方法锁:就是在一个类中的方法上加上synchronized关键字,这就是给这个方法加锁了。

    类锁:锁的是整个类,当有多个线程来声明这个类的对象的时候将会被阻塞,直到拥有这个类锁的对象被销毁或者主动释放了类锁。这个时候在被阻塞住的线程被挑选出一个占有该类锁,

        声明该类的对象。其他线程继续被阻塞住。例如:在类A上有关键字synchronized,那么就是给类A加了类锁,线程1第一个声明此类的实例,则线程1拿到了该类锁,线程2在想声明类A的对象,就会被阻塞。

  2)在本文中,使用的是方法锁。

  3)每个对象只有一把锁,有线程A,线程B,还有一个集合C类,线程A操作C拿到了集合中的锁(在集合C中有用synchronized关键字修饰的),并且还没有执行完,那么线程A就不会释放锁,

    当轮到线程B去操作集合C中的方法时 ,发现锁被人拿走了,所以线程B只能等待那个拿到锁的线程使用完,然后才能拿到锁进行相应的操作。

一、Vector简介

1.1、Vector概述

  通过API中可以知道:

    1)Vector是一个可变化长度的数组     2)Vector增加长度通过的是capacity和capacityIncrement这两个变量,目前还不知道如何实现自动扩增的,等会源码分析     3)Vector也可以获得iterator和listIterator这两个迭代器,并且他们发生的是fail-fast,而不是fail-safe,注意这里,不要觉得这个vector是线程安全就搞错了,具体分析在下面会说     4)Vector是一个线程安全的类,如果使用需要线程安全就使用Vector,如果不需要,就使用arrayList     5)Vector和ArrayList很类似,就少许的不一样,从它继承的类和实现的接口来看,跟arrayList一模一样。

  注意:现在的版本已经是jdk1.7,还有更高的jdk1.8了,在开发中,建议不用vector,原因在文章的结束会有解释,如果需要线程安全的集合类直接用java.util.concurrent包下的类。

二、Vector源码分析

2.1、继承结构和层次关系

  我们发现Vector的继承关系和层次结构和ArrayList中的一模一样,不懂的可以去前面的博客查看!

2.2、构造方法

  一共有四个构造方法。最后两个构造方法是collection Framwork的规范要写的构造方法。

  构造方法作用:

    1)初始化存储元素的容器,也就是数组,elementData,

    2)初始化capacityIncrement的大小,默认是0,这个的作用就是扩展数组的时候,增长的大小,为0则每次扩展2倍

  1)Vector():空构造

/**
     * Constructs an empty vector so that its internal data array
     * has size {@code 10} and its standard capacity increment is
     * zero.
     */
//看注释,这个是一个空的Vector构造方法,所以让他使用内置的数组,这里还不知道什么是内置的数组,看它调用了自身另外一个带一个参数的构造器
    public Vector() {
        this(10);
    }

  2)Vector(int)

/**
     * Constructs an empty vector with the specified initial capacity and
     * with its capacity increment equal to zero.
     *
     * @param   initialCapacity   the initial capacity of the vector
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
//注释说,给空的cector构造器用和带有一个特定初始化容量用的,并且又调用了另外一个带两个参数的构造器,并且给容量增长值(capacityIncrement=0)为0,查看vector中的变量可以发现capacityIncrement是一个成员变量
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

  3)Vector(int,int)

/**
     * Constructs an empty vector with the specified initial capacity and
     * capacity increment.
     *
     * @param   initialCapacity     the initial capacity of the vector
     * @param   capacityIncrement   the amount by which the capacity is
     *                              increased when the vector overflows
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
//构建一个有特定的初始化容量和容量增长值的空的Vector,
    public Vector(int initialCapacity, int capacityIncrement) {
        super();//调用父类的构造,是个空构造
        if (initialCapacity < 0)//小于0,会报非法参数异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];//elementData是一个成员变量数组,初始化它,并给它初始化长度。默认就是10,除非自己给值。
        this.capacityIncrement = capacityIncrement;//capacityIncrement的意思是如果要扩增数组,每次增长该值,如果该值为0,那数组就变为两倍的原长度,这个之后会分析到
    }

  4)Vector(Collection<? extends E> c)

/**
     * Constructs a vector containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this
     *       vector
     * @throws NullPointerException if the specified collection is null
     * @since   1.2
     */
//将集合c变为Vector,返回Vector的迭代器。
    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);
    }

2.3、核心方法

  2.3.1、add()方法

/**
     * Appends the specified element to the end of this Vector.
     *
     * @param e element to be appended to this Vector
     * @return {@code true} (as specified by {@link Collection#add})
     * @since 1.2
     */
//就是在vector中的末尾追加元素。但是看方法,synchronized,明白了为什么vector是线程安全的,因为在方法前面加了synchronized关键字,给该方法加锁了,哪个线程先调用它,其它线程就得等着,如果不清楚的就去看看多线程的知识,到后面我也会一一总结的。
    public synchronized boolean add(E e) {
        modCount++;
//通过arrayList的源码分析经验,这个方法应该是在增加元素前,检查容量是否够用
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

    ensureCapacityHelper(int)

/**
     * This implements the unsynchronized semantics of ensureCapacity.
     * Synchronized methods in this class can internally call this
     * method for ensuring capacity without incurring the cost of an
     * extra synchronization.
     *
     * @see #ensureCapacity(int)
     */
//这里注释解释,这个方法是异步(也就是能被多个线程同时访问)的,原因是为了让同步方法都能调用到这个检测容量的方法,比如add的同时,另一个线程调用了add的重载方法,那么两个都需要同时查询容量够不够,所以这个就不需要用synchronized修饰了。因为不会发生线程不安全的问题
    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
//容量不够,就扩增,核心方法
            grow(minCapacity);
    }

    grow(int)

//看一下这个方法,其实跟arrayList一样,唯一的不同就是在扩增数组的方式不一样,如果capacityIncrement不为0,那么增长的长度就是capacityIncrement,如果为0,那么扩增为2倍的原容量
    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);
    }

    感觉只要你能看的懂ArrayList,这个就是在每个方法上比arrayList多了一个synchronized,其他都一样。这里就不再分析了!

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

        return elementData(index);
    }

三、Stack

  现在来看看Vector的子类Stack,学过数据结构都知道,这个就是栈的意思。那么该类就是跟栈的用法一样了

  通过查看他的方法,和查看api文档,很容易就能知道他的特性。就几个操作,出栈,入栈等,构造方法也是空的,用的还是数组,父类中的构造,跟父类一样的扩增方式,并且它的方法也是同步的,所以也是线程安全。

四、总结Vector和Stack

4.1、Vector总结(通过源码分析)

  1)Vector线程安全是因为它的方法都加了synchronized关键字   2)Vector的本质是一个数组,特点能是能够自动扩增,扩增的方式跟capacityIncrement的值有关   3)它也会fail-fast,还有一个fail-safe两个的区别在下面的list总结中会讲到

4.2、Stack的总结

  1)对栈的一些操作,先进后出   2)底层也是用数组实现的,因为继承了Vector   3)也是线程安全的

五、List总结

5.1、arrayList和LinkedList区别

  arrayList底层是用数组实现的顺序表,是随机存取类型,可自动扩增,并且在初始化时,数组的长度是0,只有在增加元素时,长度才会增加。默认是10,不能无限扩增,有上限,在查询操作的时候性能更好

  LinkedList底层是用链表来实现的,是一个双向链表,注意这里不是双向循环链表,顺序存取类型。在源码中,似乎没有元素个数的限制。应该能无限增加下去,直到内存满了在进行删除,增加操作时性能更好。

  两个都是线程不安全的,在iterator时,会发生fail-fast。

5.2、arrayList和Vector的区别

  arrayList线程不安全,在用iterator,会发生fail-fast

  Vector线程安全,因为在方法前加了Synchronized关键字。也会发生fail-fast

5.3、fail-fast和fail-safe区别和什么情况下会发生

  简单的来说:在java.util下的集合都是发生fail-fast,而在java.util.concurrent下的发生的都是fail-safe。

  1)fail-fast

    快速失败,例如在arrayList中使用迭代器遍历时,有另外的线程对arrayList的存储数组进行了改变,比如add、delete、等使之发生了结构上的改变,

    所以Iterator就会快速报一个java.util.ConcurrentModificationException 异常(并发修改异常),这就是快速失败。

  2)fail-safe

    安全失败,在java.util.concurrent下的类,都是线程安全的类,他们在迭代的过程中,如果有线程进行结构的改变,不会报异常,而是正常遍历,这就是安全失败。

  3)为什么在java.util.concurrent包下对集合有结构的改变,却不会报异常?

    在concurrent下的集合类增加元素的时候使用Arrays.copyOf()来拷贝副本,在副本上增加元素,如果有其他线程在此改变了集合的结构,那也是在副本上的改变,而不是影响到原集合,

    迭代器还是照常遍历,遍历完之后,改变原引用指向副本,所以总的一句话就是如果在次包下的类进行增加删除,就会出现一个副本。所以能防止fail-fast,这种机制并不会出错,所以我们叫这种现象为fail-safe。   

  4)vector也是线程安全的,为什么是fail-fast呢?

    这里搞清楚一个问题,并不是说线程安全的集合就不会报fail-fast,而是报fail-safe,你得搞清楚前面所说答案的原理,出现fail-safe是因为他们在实现增删的底层机制不一样,就像上面说的,

    会有一个副本,而像arrayList、linekdList、verctor等,他们底层就是对着真正的引用进行操作,所以才会发生异常。

  5)既然是线程安全的,为什么在迭代的时候,还会有别的线程来改变其集合的结构呢(也就是对其删除和增加等操作)?

    首先,我们迭代的时候,根本就没用到集合中的删除、增加,查询的操作,就拿vector来说,我们都没有用那些加锁的方法,

    也就是方法锁放在那没人拿,在迭代的过程中,有人拿了那把锁,我们也没有办法,因为那把锁就放在那边。

5.4、举例说明fail-fast和fail-safe的区别

  1)fail-fast·

  2)fail-safe

    通过CopyOnWriteArrayList这个类来做实验,不用管这个类的作用,但是他确实没有报异常,并且还通过第二次打印,来验证了上面我们说创建了副本的事情。

    原理是在添加操作时会创建副本,在副本上进行添加操作,等迭代器遍历结束后,会将原引用改为副本引用,所以我们在创建了一个list的迭代器,结果打印的就是123444了,

    证明了确实改变成为了副本引用,后面为什么是三个4,原因是我们循环了3次,不久添加了3个4吗。如果还感觉不爽的话,看下add的源码。

5.5、为什么现在都不提倡使用vector了

  1)vector实现线程安全的方法是在每个操作方法上加锁,这些锁并不是必须要的,在实际开发中,一般都市通过锁一系列的操作来实现线程安全,也就是说将需要同步的资源放一起加锁来保证线程安全,

  2)如果多个Thread并发执行一个已经加锁的方法,但是在该方法中,又有vector的存在,vector本身实现中已经加锁了,那么相当于锁上又加锁,会造成额外的开销,

  3)就如上面第三个问题所说的,vector还有fail-fast的问题,也就是说它也无法保证遍历安全,在遍历时又得额外加锁,又是额外的开销,还不如直接用arrayList,然后再加锁呢。

  总结:Vector在你不需要进行线程安全的时候,也会给你加锁,也就导致了额外开销,所以在jdk1.5之后就被弃用了,现在如果要用到线程安全的集合,都是从java.util.concurrent包下去拿相应的类。

喜欢就点“推荐”哦!

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏王磊的博客

Java核心(四)面试必备—你不知道的数据集合

导读:Map竟然不属于Java集合框架的子集?队列也和List一样属于集合的三大子集之一?更有队列的正确使用姿势,一起来看吧!

12120
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——Set汇总

325120
来自专栏Java工程师日常干货

对HashMap的思考及手写实现前言对HashMap的思考通过写一个迷你版的HashMap来深刻理解

HashMap是Java中常用的集合,而且HashMap的一些思想,对于我们平时解决业务上的一些问题,在思路上有帮助,基于此,本篇博客将分析HashMap底层设...

10720
来自专栏Java职业技术分享

这几道Java集合框架面试题在面试中几乎必问

本文会同步更新在我开源的Java学习指南仓库 Java-Guide (一份涵盖大部分Java程序员所需要掌握的核心知识,正在一步一步慢慢完善,期待您的参与)中,...

19700
来自专栏数据结构与算法

洛谷P3380 【模板】二逼平衡树(树套树)

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

31530
来自专栏恰童鞋骚年

数据结构基础温故-1.线性表(上)

开篇:线性表是最简单也是在编程当中使用最多的一种数据结构。例如,英文字母表(A,B,C,D...,Z)就是一个线性表,表中的每一个英文字母都是一个数据元素;又如...

7710
来自专栏Java进阶架构师

对HashMap的思考及手写实现

HashMap是Java中常用的集合,而且HashMap的一些思想,对于我们平时解决业务上的一些问题,在思路上有帮助,基于此,本篇博客将分析HashMap底层设...

11420
来自专栏Java编程

Java HashMap那点事

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

44900
来自专栏一英里广度一英寸深度的学习

二叉树的深度优先遍历与广度优先遍历

先遍历子节点,再遍历兄弟节点。 从根节点开始递归,如果存在子节点,继续遍历子节点。

94330
来自专栏计算机视觉与深度学习基础

Leetcode 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth larg...

235100

扫码关注云+社区

领取腾讯云代金券