当前位置 : 主页 > 编程语言 > 其它开发 >

【Java集合】ArrayDeque源码解读

来源:互联网 收集:自由互联 发布时间:2022-06-19
简介 双端队列是一种特殊的队列,它的两端都可以进出元素,故而得名双端队列。 ArrayDeque 是一种以循环数组方式实现的双端队列,它是非线程安全的。 它既可以作为队列也可以作为
简介

双端队列是一种特殊的队列,它的两端都可以进出元素,故而得名双端队列。
ArrayDeque是一种以循环数组方式实现的双端队列,它是非线程安全的。
它既可以作为队列也可以作为栈。

继承体系

ArrayDeque实现了 Deque接口,Deque接口继承自 Queue接口,它是对 Queue的一种增强。
同时实现了 SerializableCloneable接口,可以进行序列化和克隆。

源码解读 主要属性
// 存储元素的数组
transient Object[] elements; // non-private to simplify nested class access
// 队列头位置
transient int head;
// 队列尾位置
transient int tail;
// 最小初始容量
private static final int MIN_INITIAL_CAPACITY = 8;
// 序列号
private static final long serialVersionUID = 2340985798034038923L;

head指向头元素
tail指向尾元素的下一个位置
这里注意到,headtailelements属性都被 transient修饰,不会参与序列化。
可能会有疑问,elements要是不参与序列化,集合内的数据不就无法持久化吗。
这个问题先放在这里,讲完 ArrayDeque扩容原理之后再进行回答。

构造方法
// 默认构造方法,初始容量为16
public ArrayDeque() {
    elements = new Object[16];
}
// 指定元素个数初始化
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
// 将集合c中的元素初始化到数组中
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}
// 初始化数组
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}
// 计算容量,这段代码的逻辑是算出大于numElements的最接近的2的n次方且不小于8
// 比如,3算出来是8,9算出来是16,33算出来是64
private static int calculateSize(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
    }
    return initialCapacity;
}

通过构造方法,我们知道默认初始容量是16,最小容量是8。
这里比较有意思的是 calculateSize容量计算方法,本质是为了获取大于当前数值的最小的2的幂,比如 3 算出来是 8,9 算出来是 16,33 算出来是 64。
由于 2 的幂用二进制表示的特点就是只有一个二进位位是 1 ,其余数位都是 0,所以从二进制的角度,分为两步操作

  • 第一步:将该数二进制的最高位 1 之后的所有数位设置为 1(如果 numElements < 8 则直接返回 8)
// 第一步
0000 0001 0101 1110 1000 1111 0001 1010  // 原数
0000 0001 1111 1111 1111 1111 1111 1111  // 第一步完成
  • 第二步:原数加一(如果小于 0,说明超过最大容量,整体右移一位)
// 第二步
0000 0001 1111 1111 1111 1111 1111 1111  // 第一步完成
0000 0010 0000 0000 0000 0000 0000 0000  // 第二部完成,成为 2 的幂

对于calculateSize 一种直接的想法是使用循环加位运算,找到最高位的二进制 1(形成独立的一个 2 的幂),然后将该数位左移一位返回,时间复杂度 O(n),最坏情况下需要进行 31 次。

int tmp = 1 << 31;
int count = 31;
while ((numElements & tmp) == 0 && count > 0) {
    tmp >>>= 1;
    count--;
}
tmp <<= 1;
return tmp;

源码利用的是二分的思想,总共 32 位也就是 2 的 5 次方,只需要 5 次位运算即可,时间复杂度 O(logn)

0000 0001 0000 0000 0000 0000 0000 0000 
0000 0000 1000 0000 0000 0000 0000 0000  >>> 1
0000 0001 1000 0000 0000 0000 0000 0000  |=
0000 0000 0110 0000 0000 0000 0000 0000  >>> 2
0000 0001 1110 0000 0000 0000 0000 0000  |=
0000 0000 0001 1110 0000 0000 0000 0000  >>> 4
0000 0001 1111 1110 0000 0000 0000 0000  |=
0000 0000 0000 0001 1111 1110 0000 0000  >>> 8
0000 0001 1111 1111 1111 1111 0000 0000  |=
0000 0000 0000 0000 0000 0001 1111 1111  >>> 16
0000 0001 1111 1111 1111 1111 1111 1111  |=
扩容
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];
    // 将旧数组head之后的元素拷贝到新数组中
    System.arraycopy(elements, p, a, 0, r);
    // 将旧数组下标0到head之间的元素拷贝到新数组中
    System.arraycopy(elements, 0, a, r, p);
    // 赋值为新数组
    elements = a;
    // head指向0,tail指向旧数组长度表示的位置
    head = 0;
    tail = n;
}

扩容原理:集合满了之后,创建一个原数组容量 2 倍的集数组,然后把元素拷贝到新数组中。

数组拷贝使用的是 System.arraycopy函数

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);
// src – the source array.
// srcPos – starting position in the source array.
// dest – the destination array.
// destPos – starting position in the destination data.
// length – the number of array elements to be copied.

ok,讲完扩容之后补一下坑,elements不参与序列化是从空间的角度考虑的,ArrayDeque的容量始终为 2 的幂,始终不是满的,有位置没有存放元素,如果是刚刚扩容完,可能有接近一半的空间未使用,如果参与序列化,会造成大量空间的浪费,消耗网络传输或者数据库传输,降低吞吐量。
解决方案是把集合拆分成几部分进行传输,而不是作为一个整体,来节约空间和减少序列化的时间

// 将 ArrayDeque 实例的状态保存到流(即序列化它)
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    
    // 写出当前类的所有非静态字段(non-static)和非瞬态字段(non-transient)到ObjectOutputStream
    s.defaultWriteObject();  

    // Write out size
    // 将size写出到ObjectOutputStream
    s.writeInt(size());

    // Write out elements in order.
    int mask = elements.length - 1;
    
    // i = (i + 1) & mask 表示循环数组下标的移动
    for (int i = head; i != tail; i = (i + 1) & mask)
        s.writeObject(elements[i]);  // 有序的将elementData中已使用的元素读出到流中
}

// 从流中重构 ArrayDeque 实例(即,对其进行反序列化)
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    
    // 读入size和非transient非static属性
    s.defaultReadObject();

    // Read in size and allocate array
    // 读入容量
    int size = s.readInt();
    
    // 重新分配容量
    int capacity = calculateSize(size);
    SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
    allocateElements(size);
    head = 0;
    tail = size;

    // Read in all elements in the proper order.
    // // 按正确的顺序读入所有元素。
    for (int i = 0; i < size; i++)
        elements[i] = s.readObject();
}
入队
// 从队列头入队
public void addFirst(E e) {
    // 不允许null元素
    if (e == null)
        throw new NullPointerException();
    // 将head指针减1并与数组长度减1取模
    // 这是为了防止数组到头了边界溢出
    // 如果到头了就从尾再向前
    // 相当于循环利用数组
    elements[head = (head - 1) & (elements.length - 1)] = e;
    // 如果头尾挨在一起了,就扩容
    // 扩容规则也很简单,直接两倍
    if (head == tail)
        doubleCapacity();
}

// 从队列尾入队
public void addLast(E e) {
    // 不允许null元素
    if (e == null)
        throw new NullPointerException();
    // 在尾指针的位置放入元素
    // 可以看到tail指针指向的是队列最后一个元素的下一个位置
    elements[tail] = e;
    // tail指针加1,如果到数组尾了就从头开始
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}
  • 入队有两种方式,从队列头或者从队列尾;
  • 如果容量不够了,直接扩大为两倍;
  • 通过取模的方式让头尾指针在数组范围内循环;
  • x & (len - 1) = x % len,使用 &的方式更快;
public boolean add(E e) {
    addLast(e);
    return true;
}

public boolean offer(E e) {
    return offerLast(e);
}

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}
  • 剩下几种入队操作本质都是 addFirstaddLast ,不过是多了返回值。
出队
// 从队列头出队
public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    // 取队列头元素
    E result = (E) elements[h];
    // 如果队列为空,就返回null
    if (result == null)
        return null;
    // 将队列头置为空
    elements[h] = null;     // Must null out slot
    // 队列头指针右移一位
    head = (h + 1) & (elements.length - 1);
    // 返回取得的元素
    return result;
}

// 从队列尾出队
public E pollLast() {
    // 尾指针左移一位
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    // 取当前尾指针处元素
    E result = (E) elements[t];
    // 如果队列为空返回null
    if (result == null)
        return null;
    // 将当前尾指针处置为空
    elements[t] = null;
    // tail指向新的尾指针处
    tail = t;
    // 返回取得的元素
    return result;
}

  • 出队有两种方式,从队列头或者从队列尾;
  • 通过取模的方式让头尾指针在数组范围内循环;
  • 出队之后没有缩容
// 移除队头元素
public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

// 移除队尾元素
public E removeLast() {
    E x = pollLast();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

// 移除队头元素
public E remove() {
    return removeFirst();
}

// 移除队头元素
public E poll() {
    return pollFirst();
}

剩下几种出队操作本质是 pollFirstpollLast,区别就是 remove*操作可能抛出 NoSuchElementException异常。

入栈
public void push(E e) {
    addFirst(e);
}
出栈
public E pop() {
    return removeFirst();
}

入栈和出栈操作本质都是操作队列头。

容量
public int size() {
    return (tail - head) & (elements.length - 1);
}

用与运算取代取模运算,速度更快。

查看两端元素
public E peekFirst() {
    // elements[head] is null if deque empty
    return (E) elements[head];
}

@SuppressWarnings("unchecked")
public E peekLast() {
    return (E) elements[(tail - 1) & (elements.length - 1)];
}

如果元素不存在,返回 null

public E getFirst() {
    @SuppressWarnings("unchecked")
    E result = (E) elements[head];
    if (result == null)
        throw new NoSuchElementException();
    return result;
}

/**
     * @throws NoSuchElementException {@inheritDoc}
     */
public E getLast() {
    @SuppressWarnings("unchecked")
    E result = (E) elements[(tail - 1) & (elements.length - 1)];
    if (result == null)
        throw new NoSuchElementException();
    return result;
}

如果元素不存在,抛出 NoSuchElementException异常

是否为空
public boolean isEmpty() {
    return head == tail;
}

headtail相同时表示为空

清空
public void clear() {
    int h = head;
    int t = tail;
    
    // 如果 head == tail 则为空,直接返回,指向哪里无所谓,是循环数组
    if (h != t) { // clear all cells
        // 如果 head != tail 表示有元素,head 和 tail 都指向 0 
        head = tail = 0;
        int i = h;
        int mask = elements.length - 1;
        // 从头元素开始循环清空数组
        do {
            elements[i] = null;
            i = (i + 1) & mask;
        } while (i != t);
    }
}
性能测试 ArrayDeque 与 LinkedList

ArrayDeque 跟同样实现了 Deque 接口的 LinkedList 对比。

  • 二者都添加 200000 个数据。
long start = 0, end = 0;
start = System.currentTimeMillis();
LinkedList linkedList = new LinkedList();
for (int i=0; i<2000000; i++) {
    linkedList.addFirst(i);
}
end = System.currentTimeMillis();
System.out.println("LinkedList addFirst 2000000 cost time = " + (end-start) + "ms");

LinkedList addFirst 2000000 cost time = 351ms

long start = 0, end = 0;
ArrayDeque arrayDeque = new ArrayDeque();
start = System.currentTimeMillis();
for (int i=0; i < 2000000; i++){
    arrayDeque.addFirst(i);
}
end = System.currentTimeMillis();
System.out.println("ArrayDeque addFirst 2000000 cost time = " + (end-start) + "ms");

ArrayDeque addFirst 2000000 cost time = 20ms

可以看到,ArrayDequeLinkedList速度的 15 倍

  • 二者都移除 200000 个数据。
start = System.currentTimeMillis();
while (linkedList.size() != 0) {
    linkedList.removeFirst();
}
end = System.currentTimeMillis();
System.out.println("LinkedList removeFirst cost time = " + (end-start) + "ms");

LinkedList removeFirst cost time = 21ms

start = System.currentTimeMillis();
while (arrayDeque.size() != 0) {
    arrayDeque.removeFirst();
}
end = System.currentTimeMillis();
System.out.println("ArrayDeque removeFirst cost time = " + (end-start) + "ms");

ArrayDeque removeFirst cost time = 10ms

可以看到,ArrayDequeLinkedList速度的 2 倍

网友评论