Java collection source code parsing series:
- Unpacking decoding Java collection source code overview
- Decoding Java Collection source code Collection of three systems
- Iterator for decoding Java collection source code
- Unpacking Java collection source code ArrayList
- Unpack the LinkedList of Java collection source code
- Decode HashMap of Java collection source code
- Decode Java collection source code Hashtable
- Unlink decode Java collection source code LinkedHashMap
- Decode Java collection source code PriorityQueue
- ArrayDeque decoding Java collection source code
features
-
Ring queue.
-
Initial Capacity 16
When you specify a capacity, because it is a ring queue, there must be a space at the end of the array, which can be used to determine whether the head and tail are empty or full.
(numElements < 1)?1 : (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE : numElements + 1 Copy the code -
Save two-end indexes: head and tail.
- Null: 0 <= head = tail < elements. Length
- Full: length-head = tail
- Elements [tail] is always null
-
Default capacity expansion :(oldCapacity < 64)? OldCapacity + 2: (oldCapacity >> 1).
You can expand the capacity only after adding one.
-
The key point is to maintain the relationship between head and tail.
The constructor
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable.Serializable {
transient Object[] elements;
/** * empty :0 <= head = tail < elements. Length * full: elements. Length - head = tail */
transient int head;
/** * elements[tail] Must be null */ after any operation
transient int tail;
public ArrayDeque(a) {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
// Try to keep an empty slot
elements =
new Object[(numElements < 1)?1 :
(numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
numElements + 1];
}
public ArrayDeque(Collection<? extends E> c) {
this(c.size()); copyElements(c); }}Copy the codeMaintenance of header and tail indexes
Modulus = elements. Length.
/** * Circularly increments i, mod modulus. * Precondition and postcondition: 0 <= i < modulus. */
static final int inc(int i, int modulus) {
if (++i >= modulus) i = 0;
return i;
}
/** * Circularly decrements i, mod modulus. * Precondition and postcondition: 0 <= i < modulus. */
static final int dec(int i, int modulus) {
if (--i < 0) i = modulus - 1;
return i;
}
/**
* Circularly adds the given distance to index i, mod modulus.
* Precondition: 0 <= i < modulus, 0 <= distance <= modulus.
* @return index 0 <= i < modulus
*/
static final int inc(int i, intdistanceint modulus) {
if ((i += distance) - modulus >= 0) i -= modulus;
return i;
}
/**
* Subtracts j from i, mod modulus.
* Index i must be logically ahead of index j.
* Precondition: 0 <= i < modulus, 0 <= j < modulus.
* @return the "circular distance" from j to i; corner case i == j
* is disambiguated to "empty", returning 0.
*/
static final int sub(int i, int j, int modulus) {
if ((i -= j) < 0) i += modulus;
return i;
}
/** * Returns element at array index i. * This is a slight abuse of generics, accepted by javac. */
@SuppressWarnings("unchecked")
static final <E> E elementAt(Object[] es, int i) {
return (E) es[i];
}
Copy the codeadd
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
es[head = dec(head, es.length)] = e;
if (head == tail)
// Expand the capacity after adding
grow(1);
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
es[tail] = e;
if (head == (tail = inc(tail, es.length)))
// Expand the capacity after adding
grow(1);
}
public boolean addAll(Collection<? extends E> c) {
final int s, needed;
if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0)
grow(needed);
copyElements(c);
return size() > s;
}
private void copyElements(Collection<? extends E> c) {
c.forEach(this::addLast);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
Copy the coderemove
public E removeFirst(a) {
E e = pollFirst();
if (e == null)
throw new NoSuchElementException();
return e;
}
/ * * *@throws NoSuchElementException {@inheritDoc} * /
public E removeLast(a) {
E e = pollLast();
if (e == null)
throw new NoSuchElementException();
return e;
}
public E pollFirst(a) {
final Object[] es;
final int h;
E e = elementAt(es = elements, h = head);
if(e ! =null) {
es[h] = null;
head = inc(h, es.length);
}
return e;
}
public E pollLast(a) {
final Object[] es;
final int t;
E e = elementAt(es = elements, t = dec(tail, es.length));
if(e ! =null)
es[tail = t] = null;
return e;
}
Copy the codecapacity
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int needed) {
// overflow-conscious code
final int oldCapacity = elements.length;
int newCapacity;
// Double capacity if small; else grow by 50%
int jump = (oldCapacity < 64)? (oldCapacity +2) : (oldCapacity >> 1);
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump);
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// Exceptionally, here tail == head needs to be disambiguated
if (tail < head
Tail == head; tail == head;|| (tail == head && es[head] ! =null)) {
// wrap around; slide first leg forward to end of array
/ / + + + + + + tail -- -- -- -- -- -- -- head++ + + + + | -- -- -- -- -- - or + + + + + + + + + + + + + + + + + + | head&tail -- -- -- -- -- -
int newSpace = newCapacity - oldCapacity;
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
for (int i = head, to = (head += newSpace); i < to; i++)
es[i] = null;
/ / after processing: + + + + + + tail -- -- -- -- -- -- -- -- -- -- -- -- -- head++ + + + + or + + + + + + + + + + + + tail -- -- -- -- -- - head++ + + + +}}/** Capacity calculation for edge conditions, especially overflow. */
private int newCapacity(int needed, int jump) {
final int oldCapacity = elements.length, minCapacity;
if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
if (minCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
return Integer.MAX_VALUE;
}
if (needed > jump)
return minCapacity;
return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)? oldCapacity + jump : MAX_ARRAY_SIZE; }Copy the codeSpecify the delete
It involves the maintenance of elements moving forward and backward, as well as the maintenance of header and tail indexes.
Strive to remove the least element.
Batch delete
Use bitmap, batch query meet the conditions, batch delete.
Avoid double-counting of header and tail indexes.