当前位置:首页 > 开发 > 编程语言 > Java > 正文

Java-Collections Framework学习与总结-ArrayDeque

发表于: 2013-08-12   作者:BrokenDreams   来源:转载   浏览:
摘要:         表、栈和队列是三种基本的数据结构,前面总结的ArrayList和LinkedList可以作为任意一种数据结构来使用,当然由于实现方式的不同,操作的效率也会不同。         这篇要看一下java.util.ArrayDeque。从命名上看
        表、栈和队列是三种基本的数据结构,前面总结的ArrayList和LinkedList可以作为任意一种数据结构来使用,当然由于实现方式的不同,操作的效率也会不同。
        这篇要看一下java.util.ArrayDeque。从命名上看,它是一个由数组实现的双端队列。还是先看一下它实现了哪些接口。
public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{

        这些接口都总结过了,不说了。不过我猛然发现了
@author  Josh Bloch and Doug Lea

        为什么其他的是这样
@author  Josh Bloch
@author  Neal Gafter

        这一切的一切究竟是为什么!!我仿佛听到了中国梦之声现场观众呐喊在一起。。。嘎嘎,开个玩笑。看来这个类是大师们的联手之作喽,赶紧鉴赏下:)
        先读了一下类注释,大概是说,java.util.ArrayDeque是Deque接口的动态数组实现,容量会按需扩展,线程不安全。作为栈使用比java.util.Stack快,作为队列使用比java.util.LinkedList快。大多数的操作消耗常数时间。主要特性就是这些。
        在读源码之前,还是先想一下,如果自己实现会怎么做。首先一定是有一个内部数组用来保存数据;既然是队列,那内部应该有2个指针分别指向首尾,对队列两端的操作可以通过首尾指针的移动来快速进行,可以通过首位指针的位置来算出队列的元素个数等等,大概想法是这样,当然一些细节问题还没考虑。有了大体上的思路,来看下java.util.ArrayDeque的源码吧。
    /**
     * The array in which the elements of the deque are stored.
     * The capacity of the deque is the length of this array, which is
     * always a power of two. The array is never allowed to become
     * full, except transiently within an addX method where it is
     * resized (see doubleCapacity) immediately upon becoming full,
     * thus avoiding head and tail wrapping around to equal each
     * other.  We also guarantee that all array cells not holding
     * deque elements are always null.
     */
    private transient E[] elements;

    /**
     * The index of the element at the head of the deque (which is the
     * element that would be removed by remove() or pop()); or an
     * arbitrary number equal to tail if the deque is empty.
     */
    private transient int head;

    /**
     * The index at which the next element would be added to the tail
     * of the deque (via addLast(E), add(E), or push(E)).
     */
    private transient int tail;

    /**
     * The minimum capacity that we'll use for a newly created deque.
     * Must be a power of 2.
     */
    private static final int MIN_INITIAL_CAPACITY = 8;

        可以看到,基本上是这样。最后一个常量表示初始化的最小容量,注释说明这个值必须是2的幂,这是为什么??先记住这个问题,继续往下看。
    /**
     * Constructs an empty array deque with an initial capacity
     * sufficient to hold 16 elements.
     */
    public ArrayDeque() {
        elements = (E[]) new Object[16];
    }

    /**
     * Constructs an empty array deque with an initial capacity
     * sufficient to hold the specified number of elements.
     *
     * @param numElements  lower bound on initial capacity of the deque
     */
    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }

    /**
     * Constructs a deque containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.  (The first element returned by the collection's
     * iterator becomes the first element, or <i>front</i> of the
     * deque.)
     *
     * @param c the collection whose elements are to be placed into the deque
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

        一共有3个构造方法。无参的构造方法会创建长度为16的内部数组。接受一个集合的构造方法不用多说了,看一下接受“元素数量”的构造方法,里面会调一个分配内部数组空间的方法。
    /**
     * Allocate empty array to hold the given number of elements.
     *
     * @param numElements  the number of elements to hold
     */
    private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = (E[]) new Object[initialCapacity];
    }

        这个方法是根据给定numElements来进行内部数组空间的分配。这里有一个前提, 容量必须是2的幂,尽管现在还不知道为什么必须是2的幂,但先往下看。可以看到如果numElements小于最小容量8的话,就会按最小容量来分配数组空间。如果大于等于8,会到一个条件语句中做一些操作,看下这些操作是干嘛的。我们知道如果一个2进制数是2的幂,那么它的特点就是只有一位是1。
2^0 = 1
2^1 = 10
2^n = 10000...(n个0)

        观察代码里有个initialCapacity++,我们可以想到如果一个二进制数+1得到的数是2的幂,如果这个数不是0,那么它的所有位一定都是1。
2^1 = 1 + 1
2^3 = 111 + 1
2^n = 111...(n个1) + 1

        所以看下前面的操作,numElements和numElements逻辑右移1位后的数进行与操作,然后赋给numElements。如果把numElements用二进制来表示,相当于把numElements中是1的最高位右边的一位变成1;接下来和numElements逻辑右移2位后的数进行与操作,相当于把最初numElements后面的第三位第四位变成1。。。依次类推,最终会将最高位1右边的31位都变成1(如果有这么多位的话)。
10000000000000000000000000000000
经过上面操作变成
11111111111111111111111111111111

        总之上面的操作是要得到大于numElements的最小的2的幂。当然要考虑溢出情况,所以当处理后的numElements小于0时(其实只有一种情况就是10000000000000000000000000000000),将numElements逻辑右移1位,变成2的30次方。
        接下来看下操作方法。
    // The main insertion and extraction methods are addFirst,
    // addLast, pollFirst, pollLast. The other methods are defined in
    // terms of these.

    /**
     * Inserts the specified element at the front of this deque.
     *
     * @param e the element to add
     * @throws NullPointerException if the specified element is null
     */
    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }

        看一下最上面的注释,看来只要重点瞅瞅addFirst,addLast, pollFirst, pollLast这几个方法就行了。
        先看看addFirst方法,这方法里最怪异就是head = (head - 1) & (elements.length - 1)这句了。仔细分析一下,既然head相当于一个指针,那么不管head向那个方向移动,它总会移动到内部数组的一端,那么下一次移动它应该绕回到另一端,形成一个回环。幸运的是,当插入第一个值的时候,正好是“绕回”的逻辑。因为这时head默认值是0,head-1就是-1,看到-1我们马上回想到一大串1吧(除非你不知道Java是用补码的。。),-1和一个数做“与”操作结果就是那个数喽,所以这里的结果就是elements.length - 1。
        看到这里会发现,head指针是从后往前的。继续,假设elements.length等于8,elements.length - 1就是7,插入第二个元素的时候,head是7了。再算一下刚才那个表达式,(7-1)&7=6,果然是这样,head又从后往前行进一位。考虑一下为什么要这样写,因为head要从后往前移动,所以每次减1。设想一下,如果head大于1,那么head-1%elements.length也能完成上面的工作。再想一下,如果elements.length是2的幂,那么elements.length-1的二进制形式不就是一串0就加上一串1么,head-1再和这个数做&操作不正好就是head-1(当head>1时)。其实当a是2的幂的时候,b%a可以写成b&(a-1),而且&操作要比%操作性能好一点点。况且,这样写也正好能使得当head=0时移动到数组尾部。
        好了,再看看addLast方法。
    /**
     * Inserts the specified element at the end of this deque.
     *
     * <p>This method is equivalent to {@link #add}.
     *
     * @param e the element to add
     * @throws NullPointerException if the specified element is null
     */
    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

        addLast先赋值,后移动指针。这点和addFirst不一样。具体的移动方式类似。可以想象,head是从后往前移动,tail从前往后移动。当他们相遇的时候,说明内部数组里已经放满了元素。这时候该扩容啦。
    /**
     * Double the capacity of this deque.  Call only when full, i.e.,
     * when head and tail have wrapped around to become equal.
     */
    private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = (E[])a;
        head = 0;
        tail = n;
    }

        基本上就是内部数组的容量扩充到之前的2倍,还能保证长度是2的幂。然后是数组的拷贝及指针的重定位。
        有了前面addFirst和addLast的分析,pollFirst和pollLast也很容易看懂了,只是逆过程而已。
        ok,代码分析到这里,其他部分也应该很容易看懂。看来程序中如果有用到简单的栈或者队列的地方,可以考虑下这个类喽!
       

Java-Collections Framework学习与总结-ArrayDeque

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
开发中有时会遇到这样的情况。要求某个调度器去调度一些任务,这些任务放在队列里。任务本身有优先
ArrayDeque是一个基于数组的,非线程安全的,没有容量大小限制的双端队列实现 下面这张图就是添加了
System.Data.EntityClient EntityClient 提供程序使用存储特定的 ADO.NET 数据提供程序类和映射元数
介绍 LINQ to Entities 使开发人员能够通过使用 LINQ 表达式和 LINQ 标准查询运算符,直接从开发环
POCO Entity Framework 4.0 为实体提供了简单传统 CLR 对象( Plain Old CLR Object / POCO )支持
另:Java多线程(6)之Deque与LinkedBlockingDeque深入分析(转) 其他源码分析 ArrayDeque类实现Qu
另:Java多线程(6)之Deque与LinkedBlockingDeque深入分析(转) 其他源码分析 ArrayDeque类实现Qu
System.Data.Objects (System.Data.Entity.dll) 该命名空间包含一些类,用于提供对 对象服务 的核心
Entity SQL Language 简介 什么是 Entity SQL Entity SQL 类似 SQL 语言,它的存在是为了查询 ADO.N
Entity SQL 基本查询 SWFGHO 是什么? SELECT-FROM-WHERE-GROUP BY-HAVING-ORDER BY 的首字母缩写,
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号