Osheep

时光不回头,当下最重要。

源码的魅力 - ArrayDeque 的工作原理

ArrayDeque 的工作原理(Android 7.1源码)

简介

ArrayDeque 是以循环数组形式实现的双向队列

运行原理

  1. ArrayDeque内部是使用的数组实现,并通过head以及tail两个索引来进行操作。
    ...
    transient Object[] elements;
    // non-private to simplify nested class access
    ...
    transient int head;
    ...
    transient int tail;
    ...
    public ArrayDeque() {
        //默认2的倍数
        elements = new Object[16];
    }
    //另一个指定大小的构造函数也是将elements的大小设置成2的倍数
    //由于函数太长就不再解释.
  1. offer函数的分析
  ...
  public boolean offer(E e) {
      return offerLast(e);
  }

  ...
  public boolean offerLast(E e) {
      addLast(e);
      return true
  }

  ...
  public void addLast(E e) {
     if (e == null)
         throw new NullPointerException();
     elements[tail] = e;
     if ( (tail = (tail + 1) & (elements.length - 1)) == head)
         doubleCapacity();
 }
  • 在tail位置插入数据

  • (tail + 1) 与 (elements.length – 1)相与,这一步是整个ArrayDeque设计本人认为最巧妙之处,大家可以借鉴到自己的项目中. (tail + 1) & (length – 1) 的作用就是获得tail的索引值,这一步就省去了判断是否索引越界的问题,首先ArrayDeque的大小是2的倍数,一般的Java数据结构都是这样设计的,方便计算与扩展。

  • 如何当前是数组的大小16,那么最大的索引值就是(length – 1)就是15, 如果此时(tail + 1) 正好超出索引值也就是最后位置增1 = 16,正常的结果应该是在数组的顶部也就是为0。

    tail = (1000 & 0111)
    
  • 如果tail值与head相等则翻倍扩展, 此处的位操作可以收入自己的项目中,n << 1 其实就是 n * 2。

    private void doubleCapacity() {
       assert head == tail;
       int p = head;
       int n = elements.length;
       // number of elements to the right of p
       int r = n - 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 = a;
       head = 0;
       tail = n;
     }
    
  1. addFirst函数分析

  public void addFirst(E e) {
      if (e == null)
          throw new NullPointerException();
      elements[head = (head - 1) & (elements.length - 1)] = e;
      if (head == tail)
          doubleCapacity();
  }

与上面的addLast的同理,只不过head是减1,tail是加1。

  1. pollFirst与pollLast函数分析
//从队列的顶部获取数据
public E pollFirst() {
     final Object[] elements = this.elements;
     final int h = head;
     @SuppressWarnings("unchecked")
     E result = (E) elements[h];
     // Element is null if deque empty
     if (result != null) {
         elements[h] = null; // Must null out slot
         head = (h + 1) & (elements.length - 1);
     }
     return result;
 }
  //从队列底部获取数组
  public E pollLast() {
      final Object[] elements = this.elements;
      final int t = (tail - 1) & (elements.length - 1);
      @SuppressWarnings("unchecked")
      E result = (E) elements[t];
      if (result != null) {
          elements[t] = null;
          tail = t;
      }
      return result;
  }

其实原理依旧和offer相似只是获取数据而已,pollFirst直接把head的数据返回并置为空(GC可以清理),然后将head下移。pollLast由于当前的tail是指向的尾部的下一位,所以尾部的数据是tail的上一位,返回上一位数据并置空,然后将tail上移。

点赞