Java collection detail solution!

preface

Data structure as an unavoidable problems, each developer and Java for the realization of the different data structure provides a very mature, this one is the difficulty in the interview, also is the indispensable tool for work, at this point, the author long, its branches, in this topic, only you opinion, If you can get it, then I am very happy, if there is doubt, I would like to seek it with you! This article has a total of 3.5W words and 25 pictures, and is expected to read for 2h. Bookmark this article in case you don’t find it when you use it. It’s probably the most detailed article you’ll ever see. Full version Java interview questions address: Java backend questions integration

1. Collection framework

The entire Java Collection framework is shown in the figure above (Map is not included here, and the structure of Map will be described after Collection). It can be seen that the top-level interface of all Collection implementation classes is Iterable and Collection interface, and Collection is divided into three different forms, namely List, Queue and Set, and then the different implementations.

1.1 Top-level Interface Iterable

/ / support import Java lambda function interface. The util. The function. The Consumer; Public interface Iterable<T> {//iterator() method iterator <T> iterator(); default void forEach(Consumer<? super T> action) { Objects.requireNonNull(action); for (T t : this) { action.accept(t); } } default Spliterator<T> spliterator() { return Spliterators.spliteratorUnknownSize(iterator(), 0); }} Copy the codeCopy the code

Iterable has only one interface method, iterator(). Iterator is also an interface. It has two main methods: hasNext() and next().

package java.util; import java.util.function.Predicate; import java.util.stream.Stream; import java.util.stream.StreamSupport; public interface Collection<E> extends Iterable<E> { int size(); boolean isEmpty(); boolean contains(Object o); Iterator<E> iterator(); Object[] toArray(); boolean add(E e); boolean remove(Object o); boolean containsAll(Collection<? > c); boolean removeAll(Collection<? > c); default boolean removeIf(Predicate<? super E> filter) { Objects.requireNonNull(filter); boolean removed = false; final Iterator<E> each = iterator(); while (each.hasNext()) { if (filter.test(each.next())) { each.remove(); removed = true; } } return removed; } boolean retainAll(Collection<? > c); void clear(); int hashCode(); @Override default Spliterator<E> spliterator() { return Spliterators.spliterator(this, 0); } default Stream<E> stream() { return StreamSupport.stream(spliterator(), false); } default Stream<E> parallelStream() { return StreamSupport.stream(spliterator(), true); }} Copy the codeCopy the code

The main interface methods for Collection are:

2, the List

A List is a List of ordered collections. Unlike the Collection interface, a List highlights the sense of order.

2.1 the List interface

package java.util; import java.util.function.UnaryOperator; public interface List<E> extends Collection<E> { <T> T[] toArray(T[] a); boolean addAll(Collection<? extends E> c); boolean addAll(int index, Collection<? extends E> c); default void replaceAll(UnaryOperator<E> operator) { Objects.requireNonNull(operator); final ListIterator<E> li = this.listIterator(); while (li.hasNext()) { li.set(operator.apply(li.next())); } } default void sort(Comparator<? super E> c) { Object[] a = this.toArray(); Arrays.sort(a, (Comparator) c); ListIterator<E> i = this.listIterator(); for (Object e : a) { i.next(); i.set((E) e); } } boolean equals(Object o); E get(int index); E set(int index, E element); void add(int index, E element); int indexOf(Object o); int lastIndexOf(Object o); ListIterator<E> listIterator(); List<E> subList(int fromIndex, int toIndex); @Override default Spliterator<E> spliterator() { return Spliterators.spliterator(this, Spliterator.ORDERED); }} Copy the codeCopy the code

Add, addAll, get,indexOf,set, etc., and index subscript is supported. What’s the difference between Collection and List? A. The biggest difference between a Collection and a List is that a Collection is unordered and does not support index operations, while a List is ordered. Collection has no concept of order. B. The Iterator in the List is ListIterator. C. The List interface supports the sort method. D. The Spliterator operation modes are different. ** Why does the subclass interface repeat the parent interface? ** Official explanation: The parent interface is repeatedly declared in the subinterface for ease of viewing documentation. For example, in Java Doc documents, you can also see the Collecion declared interface in the List interface.

2.2 List Implements ArrayList

ArrayList is one of the most common implementations of the List interface, supporting some of the List interface’s column operations.

2.2.1 Inheritance relationship of ArrayList

2.2.2 ArrayList composition

private static final Object[] EMPTY_ELEMENTDATA = {}; Private Static Final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} private static final Object[] elementData; // non-private to simplify nested class access private int size; Copy the codeCopy the code

Remember the transient Object[] elementData in ArrayList, which is the container that holds the elements. ArrayList is implemented based on arrays.

2.2.3 ArrayList constructor

>public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } Duplicate codeCopy the code

1. Object[] elementData is an array of data that an ArrayList actually holds.
2. ArrayList supports default size constructs, as well as empty constructs, where Object[] elementData is an empty array {}.

2.2.4 Adding elements to the ArrayList

>public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } Duplicate codeCopy the code

Note that the ArrayList has a modCount property that represents the number of times the instance has been modified. (All collections have a modCount property that records the number of changes.) Each increment increment increases the number of changes to the ArrayList, and the add(E E) method above adds the new element to the end of the list.

2.2.4 ArrayList expansion

private static int calculateCapacity(Object[] elementData, Int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//DEFAULT_CAPACITY is 10 return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } Duplicate codeCopy the code

If the initialized list is an empty ArrayList, DEFAULT_CAPACITY is directly expanded. The default value is 10. When the number of elements added to an ArrayList exceeds the size of the array, it expands. Notice this line of code

int newCapacity = oldCapacity + (oldCapacity >> 1); Copy the codeCopy the code

With the right shift operation, it is the original general, so it is expanded by 1.5 times. For example, the binary of 10 is 1010, and when you move it to the right, 101 is 5.

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } Duplicate codeCopy the code

2.2.5 copy an array

Java is not able to allocate its own space. It is the low-level IMPLEMENTATION of C and C++. Taking C as an example, we know that an array in C is a pointer to the head. For example, we allocate memory to an array in C. Java is the copying of arrays through the native method arrayCopy.

public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); Copy the codeCopy the code

p = (int *)malloc(len*sizeof(int)); Copy the codeCopy the code

What are the benefits of this? ** In Java, memory is managed by the JVM, and arrays are allocated contiguous memory, whereas an arrayList is not necessarily contiguous memory. Of course, the JVM does this for us, and the JVM has internal optimizations, which will be explained in conjunction with the following examples.

2.2.6 according to? ElementData is transient.

1. The effect of transient is that this property does not participate in serialization.

2. ArrayList inherits the Serializable interface that identifies serialization

3. Read and write security is controlled during arrayList serialization. How is serialization security implemented?

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // Write out all elements in the proper order. for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount ! = expectedModCount) { throw new ConcurrentModificationException(); } } /** * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // Read in size, and any hidden stuff s.defaultReadObject(); // Read in capacity s.readInt(); // ignored if (size > 0) { // be like clone(), allocate array based upon size not capacity int capacity = calculateCapacity(elementData, size); SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); ensureCapacityInternal(size); Object[] a = elementData; // Read in all elements in the proper order. for (int i=0; i<size; i++) { a[i] = s.readObject(); }}} copy the codeCopy the code

As you can see in the serialization method writeObject(), write size as the default, and write elementData as iterated. Since this variable is transient, write it manually so that it will be serialized. Is that redundant?

protected transient int modCount = 0; Copy the codeCopy the code

Of course not, there is a key modCount variable that counts the number of changes to the list. If the number of changes is not the same as before the serialization started, an exception will be thrown and the serialization will fail. This ensures that the serialization process is unmodified data, ensuring serialization security. (This is implemented in Java collections)

2.3 LinkedList

As we all know LinkedList is a LinkedList structure, how to implement LinkedList in Java?

2.3.1 LinkedList Inheritance relationship

As you can see, LinkedList is both the implementation of the List interface and the implementation of Queue (Deque), so it supports more functions than ArrayList. LinkedList can be used as a Queue. Of course, the implementation of Queue is not emphasized below.

2.3.2 Structure of LinkedList

transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item ! = null) */ transient Node<E> last; Copy the codeCopy the code

LinkedList consists of a head node and a tail node pointing to the head and tail of the list, respectively. The source code for Node in LinkedList is as follows, consisting of the current value item and Pointers to the previous Node prev and the next Node next. And contains only one constructor, constructed in order of arguments (prev, item, next).

private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; }} Copy the codeCopy the code

What is the structure of a Node in a LinkedList? LinkedList consists of a head node, a tail node, and a size that defaults to 0.

<pre style="margin: 0px; padding: 0px; max-width: 100%; background-image: none; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; box-sizing: border-box ! important; overflow-wrap: break-word ! important;" >transient int size = 0; transient Node<E> first; transient Node<E> last; Public LinkedList() {} Copies the codeCopy the code

LinkFirst and linkLast are the header and tail insertions of linked lists in data structures

/** * Links e as first element. */ private void linkFirst(E E) {final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } /** * Links e as last element. */ linkLast(E E) {final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } Duplicate codeCopy the code

2.3.3 LinkedList query method

Get a node ** : get to get the index node.

public E get(int index) { checkElementIndex(index); return node(index).item; } Duplicate codeCopy the code

How is the node(index) method implemented? Determine whether the index is closer to the head or the tail, and get the value from which section to traverse.

Node<E> node(int index) { // assert isElementIndex(index); If (index < (size >> 1)) {Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }} Copy the codeCopy the code

Query the index modification method, first find the corresponding node, replace the old value with the new value.

public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; } Duplicate codeCopy the code

This is also why ArrayList accesses randomly faster than LinkedList ** The LinkedList has to traverse to find the location to modify, whereas ArrayList is internal array operations are faster.

2.4.3 LinkedList modification method

To add a new node, you can see that the new node is inserted into the tail.

public boolean add(E e) { linkLast(e); return true; } Duplicate codeCopy the code

2.5 the Vector

Like ArrayList, Vector is an implementation class of the List interface. The main implementation classes of List interface include ArrayLIst, LinkedList, Vector and Stack, among which the latter two are rarely used.

2.5.1 vector composition

It’s basically the same thing as an ArrayList.

// Protected Object[] elementData; // Number of valid elements, less than or equal to the length of the array // Protected int capacityIncrement; Copy the codeCopy the code

2.5.2 Vector thread safety

Vector is a thread-safe, synchronized modified operation.

2.5.3 vector capacity

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); } Duplicate codeCopy the code

Capacity expansion When the structure does not have capacityIncrement, a capacity expansion array becomes twice the original, otherwise, each time increase capacityIncrement.

2.5.4 Classic example of vector method

Remove an element

public synchronized E remove(int index) { modCount++; if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); E oldValue = elementData(index); int numMoved = elementCount - index - 1; Arraycopy (elementData, index+1, elementData, index, numMoved); if (numMoved > 0); // Reference null, gc will handle elementData[--elementCount] = null; // Let gc do its work return oldValue; } Duplicate codeCopy the code

There is mainly one two-line code to note here, and the author has comments in the code. When an element is removed from an array and moved, be sure to set the end of the array to NULL and reduce the effective length by 1. In general, the vector implementation is fairly crude and rarely used, so just take a look.

2.6 the Stack

Stack is also one of the implementation classes of the List interface. Like Vector, the data structure Stack is rarely used in the development process for performance reasons. However, Stack is a very important data structure at the bottom of the computer.

2.6.1 Inheritance relationship of the Stack

Stack inherits from Vector, which is also the implementation class of the List interface. As mentioned earlier, Vector is thread-safe because its methods are synchronized modified, so the operations that Stack inherits from Vector are thread-safe as well.

2.6.2 Using the Stack

Just as Stack is the realization of Stack, its main operation is push on the Stack and pop off the Stack, and the biggest feature of the Stack is LIFO (Last In First Out).

Stack<String> strings = new Stack<>(); strings.push("aaa"); strings.push("bbb"); strings.push("ccc"); System.err.println(strings.pop()); Copy the codeCopy the code

As you can see from the code above, the string “CCC” that is pushed last is also pushed first.

2.6.3 Stack source

Public class Stack<E> extends Vector<E> {public Stack() {} public class Stack<E> extends Vector<E> {} public Stack() {} public class Stack<E> extends Vector<E> {} public E push(E item) { addElement(item); return item; } // unstack, find the last element of the array, remove and return. public synchronized E pop() { E obj; int len = size(); obj = peek(); removeElementAt(len - 1); return obj; } public synchronized E peek() { int len = size(); if (len == 0) throw new EmptyStackException(); return elementAt(len - 1); } public boolean empty() { return size() == 0; } public synchronized int search(Object o) { int i = lastIndexOf(o); if (i >= 0) { return size() - i; } return -1; } private static final long serialVersionUID = 1224463164541339165L; } Duplicate codeCopy the code

The push method uses the Vector addElement (E E) method, which places elements at the end of the collection, and the pop method uses the Vector removeElementAt(Index x) method. The push method uses the Vector addElement (E E) method, which places elements at the end of the collection. Remove and get the tail element of the set, so you can see that the Stack operates on the tail of the linear table.

3, the Queue

As described in data structures, queue is a first-in, first-out data structure, i.e., first in, first out. You can think of a queue as a container in which elements can only be inserted from one segment and taken from the other, as shown below, but it is important to note that the queue does not specify which end to insert and which segment to retrieve.

3.1 What is a Deque

A Deque is a Double ended queue, also known as a double-ended queue. That is, for the queue container, it can be inserted from the head or from the tail, and it can be fetched from the head or the tail, as shown below.

3.1.1 Queue interface in Java

Note that Java explicitly inserts queues from the tail and fetches them from the head, so Java implementations of queues are always fetches them from the head.

package java.util; Public interface Queue<E> extends Collection<E> {Boolean add(E E); Boolean offer(E E); // Remove the element. If the set is empty, throw an exception E remove(); // Remove the queue header element and return, if empty, null E poll(); // Query the first element of the collection. If it is empty, throw E element(); // Query the first element in the queue, if null, return null E peek(); } Duplicate codeCopy the code

The common methods used by Java Queues are shown in the table. The difference between the methods used for interfaces in the table and those not in the table is that queue operations do not throw exceptions because the queue is empty, whereas collection operations throw exceptions because the queue is empty.

3.1.2 Deque interface

package java.util; Public interface Deque<E> extends Queue<E> {void addFirst(E E); void addLast(E e); boolean offerFirst(E e); boolean offerLast(E e); E removeFirst(); E removeLast(); E pollFirst(); E pollLast(); E getFirst(); E getLast(); E peekFirst(); E peekLast(); boolean removeFirstOccurrence(Object o); boolean removeLastOccurrence(Object o); // *** Queue methods *** boolean add(E e); boolean offer(E e); E remove(); E poll(); E element(); E peek(); // omit a bunch of stack interface methods and collection interface methods} copy codeCopy the code

Just like methods in Queue, methods with names like First or Last operate from the head and Last from the tail.

3.1.3 Queue, implementation class of Deque

The implementation of Queue in Java mainly uses double-ended Queue, after all, the operation is more convenient and free. The implementation of Queue includes PriorityQueue and Deque. In Java.util, there are two main implementation classes ArrayDeque and LinkedList, one of which is an array-based implementation. One is an implementation based on linked lists. As mentioned in the previous LinkedList article, it is a bidirectional LinkedList on which the Deque interface is implemented.

3.2 PriorityQueue

PriorityQueue is the only direct implementation of the Queue interface in Java and, as its name suggests, a PriorityQueue, which internally supports ordering internal elements according to certain rules.

3.2.1 PriorityQueue Inheritance relationship

PriorityQueue is the implementation class of Queue. It is mainly used for the basic operations of queues. As mentioned before, the basic principle of Queue is FIFO (First In First Out). In Java, PriorityQueue is implemented in a queue-compliant manner, but with a slight difference in the priority of PriorityQueue. PriorityQueue is a queue that supports priority. When using its priority feature, it is not FIFO.

3.2.2 Use of PriorityQueue

Case 1:

PriorityQueue<Integer> queue = new PriorityQueue<>(); queue.add(20); queue.add(14); queue.add(21); queue.add(8); queue.add(9); queue.add(11); queue.add(13); queue.add(10); queue.add(12); queue.add(15); while (queue.size()>0){ Integer poll = queue.poll(); System.err.print(poll+"->"); } Duplicate codeCopy the code

The above code puts 10 ints into the Queue and poll() each of them using the poll() method of the Queue. The result is that each poll is the smallest value in the Queue. This shows that there is a certain order in PriorityQueue.

Case 2:

<pre style="margin: 0px; padding: 0px; max-width: 100%; background-image: none; background-position: Private static class Test implements Comparable<Test>{private int a; public Test(int a) { this.a = a; } public int getA() { return a; } public void setA(int a) { this.a = a; } @Override public String toString() { return "Test{" + "a=" + a + '}'; } @Override public int compareTo(Test o) { return 0; } } public static void main(String[] args) { PriorityQueue<Test> queue = new PriorityQueue<>(); queue.add(new Test(20)); queue.add(new Test(14)); queue.add(new Test(21)); queue.add(new Test(8)); queue.add(new Test(9)); queue.add(new Test(11)); queue.add(new Test(13)); queue.add(new Test(10)); queue.add(new Test(12)); queue.add(new Test(15)); while (queue.size()>0){ Test poll = queue.poll(); System.err.print(poll+"->"); }} Copy the codeCopy the code

The code above overrides the compareTo method to return 0, i.e., no precedence sorting. Found that we returned to the order for the Test} {a = 20 – > Test {a = 15} – > Test {12} a = – > Test {10} a = – > Test {} a = 13 – > Test {} a = 11 – > Test {} a = 9 – > Test {8} a = – > Test {} a = 21 – > Test Comparable {a=14}, and put in the same order, so we need to be aware that we need to implement the Comparable interface according to the rules of precedence. We will use the source code to analyze why the order of pull is not the same as that of put in.

3.2.3 PriorityQueue composition

Private static final int DEFAULT_INITIAL_CAPACITY = 11; private static final int DEFAULT_INITIAL_CAPACITY = 11; /** * transient Object[] queue; // Simplify nested class access /** * simplify nested class access */ private int size = 0; /** * A custom comparison rule that is preferred if it exists, otherwise the Comparable interface method implemented by the element is used. */ private final Comparator<? super E> comparator; /** * TRANSIENT int modCount = 0; // Non-private to simplify class accessCopy the code

As you can see, the PriorityQueue is simple: remember an array of elements and a Comparator.

3.2.4 PriorityQueue Operation Method

Offer method

public boolean offer(E e) { if (e == null) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) grow(i + 1); size = i + 1; If (I == 0) queue[0] = e; else siftUp(i, e); return true; } Duplicate codeCopy the code

The first thing you can see is that when the Queue is empty, the first element is placed at the top of the array, so the first element 20 in case 2 is placed at the top of the array. When the queue is not empty, the siftUp(I, e) method is used, passing in the number of elements in the queue and the number of new elements to be added. Now let’s see what siftUp(I, e) does.

private void siftUp(int k, E x) { if (comparator ! = null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); } Duplicate codeCopy the code

Remember that PriorityQueue is an array of elements and a Comparator. We use the element class to implement the compareTo method when there is no Comparator. The implication is that the custom comparison rule Comparator is used in preference to the Comparable interface method implemented by the element’s class.

private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; While (k > 0) {// why -1, think array positions 0, 1, 2. Int parent = (k-1) >>> 1; int parent = (k-1) >>> 1; Object e = queue[parent]; If (key.compareTo((E) E) >= 0) break; if (key.compareTo((E) E) >= 0) break; queue[k] = e; k = parent; } queue[k] = key; } Duplicate codeCopy the code

As you can see, when a new element is inserted into a PriorityQueue that is not empty, its new element will be heapsort (heapsort is not described here), so that the element will be heapsort every time it comes in, which ensures that the first element in the Queue is always the smallest (default rule sort).

The pool method

public E poll() { if (size == 0) return null; int s = --size; modCount++; E result = (E) queue[0]; X = (E) queue[s]; queue[s] = null; if (s ! = 0) siftDown(0, x); return result; } Duplicate codeCopy the code

Here we can see that when a value is fetched and siftDown is performed, the parameters passed in are index 0 and the last element in the queue.

private void siftDownComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1; // loop while a non-leaf while (k < half) { int child = (k << 1) + 1; // assume left child is least Object c = queue[child]; int right = child + 1; If (right < size && //c and right are two children of parent, find the smaller one to become the new c. ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) c = queue[child = right]; if (key.compareTo((E) c) <= 0) break; Queue [k] = c; // Queue [k] = c; k = child; } queue[k] = key; } Duplicate codeCopy the code

When there is no Comparator the siftDown method is used as above, because the index 0 position is retrieved, find the child node of index 0 that is smaller than it as the new parent and recurse within the loop. PriorityQueue is very simple, but I won’t go into any more details.

3.3 ArrayDeque

ArrayDeque is a two-ended queue based on an array implementation in Java. In Java, deques are implemented as LinkedList and ArrayDeque. As their names indicate their differences, LinkedList is implemented based on a bidirectional LinkedList. ArrayDeque is based on arrays.

3.3.1 Inheritance relationship of ArrayDeque

ArrayDeque is an implementation of the Deque interface. Unlike LinkedList, LinkedList is both a List interface and an implementation of the Deque interface.

3.3.2 rainfall distribution on 10-12 ArrayDeque use

case

ArrayDeque<String> deque = new ArrayDeque<>(); deque.offer("aaa"); deque.offer("bbb"); deque.offer("ccc"); deque.offer("ddd"); // The peek method gets system.err. Println (deque.peekfirst ()); System.err.println(deque.peekLast()); Copy the codeCopy the code

Case 2:

ArrayDeque<String> deque = new ArrayDeque<>(); deque.offerFirst("aaa"); deque.offerLast("bbb"); deque.offerFirst("ccc"); deque.offerLast("ddd"); String a; while((a = deque.pollLast())! =null){ System.err.print(a+"->"); } Duplicate codeCopy the code

PollLast (); pollLast(); DDD, BBB,aaa, CCC;

3.3.4 Internal composition of ArrayDeque

[] elements transient Object[] elements; // non-private to // TRANSIENT int head; // queue end index TRANSIENT int tail; Private static final int MIN_INITIAL_CAPACITY = 8; private static final int MIN_INITIAL_CAPACITY = 8; private static final int MIN_INITIAL_CAPACITY = 8; Copy the codeCopy the code

3.3.5 Length of array Elements

The elements array is always a power of 2. This is implemented as in hashMap, where the binary length is made up entirely of 1’s and then increments by 1 to 100… So it must be 2 to the power.

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; } Duplicate codeCopy the code

3.3.6 ArrayDeque implementation mechanism

As shown below:

The array should be treated as end to end. The initial head and tail indexes are 0, addLast goes to the right, addFirst goes to the left, so the middle of the array may be empty. When the head and tail Pointers meet, expand the array and adjust the element positions. Source:

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

Note the following line: head=head-1 if head-1 is greater than or equal to 0, otherwise head=elements. Length-1.

Head = (head - 1) & (elements. Length-1) Copies the codeCopy the code

Or another way to write it is down here, is that where the addFirst pointer is moving up here?

head = head-1>=0? Head-1 :elements. Length-1 Copies the codeCopy the code

This is the magic of bitwise operations, because any number with an all-binary 1 greater than it is equal to itself when ampersand, such as 1010&1111 = 1010, is not described here. Now look at the addLast method:

public void addLast(E e) { if (e == null) throw new NullPointerException(); elements[tail] = e; if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity(); } Duplicate codeCopy the code

Also notice that there’s a bunch of magic code.

(tail = (tail + 1) & (elements. Length-1)) copies the codeCopy the code

Tail = tail+1>element-1? 0:tail+1 a binary number consisting of all 1’s and a number greater than that will result in 0. For example, 10000&1111 = 0. Poll method and add method logic is opposite, here will not repeat, we all seek!

4. Set

If List adds orderliness to a Set, then Set adds uniqueness to a Set.

4.1 the Set interface

The Set interface in Java is exactly the same definition as Colletion.

package java.util; public interface Set<E> extends Collection<E> { // Query Operations int size(); boolean isEmpty(); Object[] toArray(); <T> T[] toArray(T[] a); // Modification Operations boolean add(E e); boolean remove(Object o); boolean containsAll(Collection<? > c); boolean addAll(Collection<? extends E> c); boolean retainAll(Collection<? > c); boolean removeAll(Collection<? > c); void clear(); boolean equals(Object o); int hashCode(); Spliterator<E> Spliterator () {return spliterators.spliterator (this, spliterator.distinct); }} Copy the codeCopy the code

4.2 HashSet

The Java HashSet, as its name suggests, is a collection of Hash implementations using the underlying structure HashMap.

4.2.1 HashSet Inheritance relationship

4.2.2 HashSet source

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { static final long serialVersionUID = -5024744406713321676L; private transient HashMap<E,Object> map; private static final Object PRESENT = new Object(); public HashSet() { map = new HashMap<>(); } public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); } public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); } HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } public Iterator<E> iterator() { return map.keySet().iterator(); } public int size() { return map.size(); } public boolean isEmpty() { return map.isEmpty(); } public boolean contains(Object o) { return map.containsKey(o); } public boolean add(E e) { return map.put(e, PRESENT)==null; } public boolean remove(Object o) { return map.remove(o)==PRESENT; } public void clear() { map.clear(); }} Copy the codeCopy the code

You can see that inside a HashSet is actually a HashMap.

4.2.3 How is a HashSet guaranteed to be non-repetitive?

As you can see in the Add method of a HashSet, the inserted value is used as the key of the HashMap, so the HashMap guarantees no repetition. Map’s PUT method returns null for adding a value that does not already exist, or the original value if it already exists. For details on how HashMap is implemented, see later!

4.3 LinkedHashSet

LinkedHashSet is also less used and is also based on a Set implementation.

4.3.1 LinkedHashSet Inheritance relationship

Like HashSet, it is an implementation class of the Set interface and is a subclass of HashSet.

4.3.2 LinkedHashSet source

package java.util; public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { private static final long serialVersionUID = -2851667679971038690L; Public LinkedHashSet(int initialCapacity, float loadFactor) {// Call the constructor of HashSet super(initialCapacity, loadFactor, true); } public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); } public LinkedHashSet() { super(16, .75f, true); } public LinkedHashSet(Collection<? extends E> c) { super(Math.max(2*c.size(), 11), .75f, true); addAll(c); } @Override public Spliterator<E> spliterator() { return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED); }} Copy the codeCopy the code

It operates exactly like a HashSet, so what’s the difference? First, LinkedHashSet is a subclass of HashSet. Second, the implementation of LinkedHashSet that stores values, LinkedHashMap, uses HashMap. The parent class constructor called in LinkedHashSet shows that the column is actually a LinkedHashMap.

HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } Duplicate codeCopy the code

The implementation of LinkedHashSet is simple, but a deeper understanding is needed to look at the implementation of LinkedHashMap, which will be resolved separately.

5, the Map

A Map is a key-value structure, often referred to as a key-value structure. A Map is composed of many k-V key-value pairs. A K-V structure is called Entry. The figure above shows one of the most basic constructs of the Map family (only in java.util). Full version Java interview questions address: Java backend questions integration

5.1 the Map interface

package java.util; import java.util.function.BiConsumer; import java.util.function.BiFunction; import java.util.function.Function; import java.io.Serializable; public interface Map<K,V> { // Query Operations int size(); boolean isEmpty(); boolean containsKey(Object key); boolean containsValue(Object value); V get(Object key); // Modification Operations V put(K key, V value); V remove(Object key); // Bulk Operations void putAll(Map<? extends K, ? extends V> m); void clear(); Set<K> keySet(); Collection<V> values(); Set<Map.Entry<K, V>> entrySet(); interface Entry<K,V> { K getKey(); V getValue(); V setValue(V value); boolean equals(Object o); int hashCode(); public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() { return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> c1.getKey().compareTo(c2.getKey()); } public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() { return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> c1.getValue().compareTo(c2.getValue()); } public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) { Objects.requireNonNull(cmp); return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey()); } public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) { Objects.requireNonNull(cmp); return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue()); } } // Comparison and hashing boolean equals(Object o); int hashCode(); default V getOrDefault(Object key, V defaultValue) { V v; return (((v = get(key)) ! = null) || containsKey(key)) ? v : defaultValue; } default void forEach(BiConsumer<? super K, ? super V> action) { Objects.requireNonNull(action); for (Map.Entry<K, V> entry : entrySet()) { K k; V v; try { k = entry.getKey(); v = entry.getValue(); } catch(IllegalStateException ise) { // this usually means the entry is no longer in the map. throw new ConcurrentModificationException(ise); } action.accept(k, v); } } default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { Objects.requireNonNull(function); for (Map.Entry<K, V> entry : entrySet()) { K k; V v; try { k = entry.getKey(); v = entry.getValue(); } catch(IllegalStateException ise) { // this usually means the entry is no longer in the map. throw new ConcurrentModificationException(ise); } // ise thrown from function is not a cme. v = function.apply(k, v); try { entry.setValue(v); } catch(IllegalStateException ise) { // this usually means the entry is no longer in the map. throw new ConcurrentModificationException(ise); } } } default V putIfAbsent(K key, V value) { V v = get(key); if (v == null) { v = put(key, value); } return v; } default boolean remove(Object key, Object value) { Object curValue = get(key); if (! Objects.equals(curValue, value) || (curValue == null && ! containsKey(key))) { return false; } remove(key); return true; } default boolean replace(K key, V oldValue, V newValue) { Object curValue = get(key); if (! Objects.equals(curValue, oldValue) || (curValue == null && ! containsKey(key))) { return false; } put(key, newValue); return true; } default V replace(K key, V value) { V curValue; if (((curValue = get(key)) ! = null) || containsKey(key)) { curValue = put(key, value); } return curValue; } default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { Objects.requireNonNull(mappingFunction); V v; if ((v = get(key)) == null) { V newValue; if ((newValue = mappingFunction.apply(key)) ! = null) { put(key, newValue); return newValue; } } return v; } default V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { Objects.requireNonNull(remappingFunction); V oldValue; if ((oldValue = get(key)) ! = null) { V newValue = remappingFunction.apply(key, oldValue); if (newValue ! = null) { put(key, newValue); return newValue; } else { remove(key); return null; } } else { return null; } } default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { Objects.requireNonNull(remappingFunction); V oldValue = get(key); V newValue = remappingFunction.apply(key, oldValue); if (newValue == null) { // delete mapping if (oldValue ! = null || containsKey(key)) { // something to remove remove(key); return null; } else { // nothing to do. Leave things as they were. return null; } } else { // add or replace old mapping put(key, newValue); return newValue; } } default V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) { Objects.requireNonNull(remappingFunction); Objects.requireNonNull(value); V oldValue = get(key); V newValue = (oldValue == null) ? value : remappingFunction.apply(oldValue, value); if(newValue == null) { remove(key); } else { put(key, newValue); } return newValue; }} Copy the codeCopy the code

The Map interface itself is a top-level interface, which consists of a bunch of Map interface methods and an Entry interface. The Entry interface defines some operations mainly about key-values, and the Map interface defines some attributes and some interface methods about attribute search and modification.

5.2 a HashMap

HashMap is the most commonly used K-V container in Java, which is implemented by hashing. HashMap stores key-value pairs one after another, which we call Entry. HashMap extends Entry (called Node). Make it a linked list or tree structure and store it in a HashMap container (which is an array).

5.2.1 Inheritance relationship of HashMap

5.2.2 Data stored in a HashMap

The Map interface has an Entry interface, which is implemented in HashMap. The implementation of Entry is the type of data stored in HashMap. The implementation of Entry in HashMap is Node. Node is a single-linked list structure, and TreeNode is a subclass of it, which is a red-black tree type. Its inheritance structure diagram is as follows:

What is the data in a HashMap? The code holds the following containers:

transient Node<K,V>[] table; Copy the codeCopy the code

The container is composed of one node after another, and there are three implementations of node. Therefore, the form of node stored in hashMap can be either Node or TreeNode.

5.2.3 Composition of a HashMap

With the above concepts in mind, let’s take a look at the components of a HashMap.

<K,V>[] table transient Node<K,V>[] static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // The maximum value of this array is 2^31 1. static final int MAXIMUM_CAPACITY = 1 << 30; Static final float DEFAULT_LOAD_FACTOR = 0.75f; static final float DEFAULT_LOAD_FACTOR = 0.75f; // The number of nodes stored in a position will be converted to a tree threshold, i.e. 8. For example, if there is a node in the array, the length of the node list will be converted to a red-black tree. static final int TREEIFY_THRESHOLD = 8; Static final int UNTREEIFY_THRESHOLD = 6; static final int UNTREEIFY_THRESHOLD = 6; Static final int MIN_TREEIFY_CAPACITY = 64; static final int MIN_TREEIFY_CAPACITY = 64; // A transient Node<K,V>[] table; Entry< k, v >> entrySet; entrySet < map. Entry< k, v >> entrySet; //size indicates the number of key/value pairs in the hashMap transient int size; // Transient int modCount; // loadFactor final float loadFactor; Copy the codeCopy the code

Bin refers to a node in a certain position in the table. A node can be understood as a batch/box of data.

5.2.4 Constructors * in HashMap

InitialCapacity public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); If (s > 0) {if (table == null) {// pre-size float ft = (float)s/loadFactor) + 1.0f; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); if (t > threshold) threshold = tableSizeFor(t); } else if (s > threshold) resize(); for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } } public HashMap(int initialCapacity, Float loadFactor) {if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity); // When the capacity is greater than 2^31, the maximum value is 1<<31; if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; // tableSizeFor Specifies that the current table size must be a power of 2. TableSizeFor specifies that the table size must be a power of 2. this.threshold = tableSizeFor(initialCapacity); } Duplicate codeCopy the code

TableSizeFor () ensures that the size of an array is a power of 2.

static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } Duplicate codeCopy the code

This method changes the first digit of a binary number to 1 and then increments it by 1, so that the binary number must be 100… It looks like this. The implementation here uses a similar approach to the implementation of ArrayDeque to ensure that the array length must be a power of two.

5.2.5 put method

Put methods used by developers:

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } Duplicate codeCopy the code

The real method for putting values used internally in a HashMap is:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // When the hash is null, If ((p = TAB [I = (n-1) & hash]) == null) TAB [I] = newNode(hash, key, value, null); else { Node<K,V> e; K k; / / the value of the first is to find the location to assign p e the if (p.h ash = = hash && ((k = p.k ey) = = key | | (key! = null && key.equals(k)))) e = p; // If it is a red-black tree, PutTreeVal (this, TAB, hash, key, value) else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p). PutTreeVal (this, TAB, hash, key, value); Else {// is the list, iterate, notice e = p.ext this keeps assigning the next node to e, all the way to the end, notice that it starts with ++binCount for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); If (binCount >= treeify_threshthreshold -1) // -1 for 1st treeifyBin(TAB, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) break; p = e; } } if (e ! = null) { // existing mapping for key V oldValue = e.value; if (! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } Duplicate codeCopy the code

5.2.6 Search methods

final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; If ((TAB = table)! = null && (n = tab.length) > 0 && // This line finds the location of the Key in the table, which is the array containing each Node in the HashMap. (first = tab[(n - 1) & hash]) ! = null) {// the root Node is the key to be queried. Convenient follow-up to traverse the Node spelled and / / for only the root Node of the Node directly determine the if (first. The hash = = hash && / / always check first Node ((k = first. Key) = = key | | (key! = null && key.equals(k)))) return first; If ((e = first.next)! If (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreenode (hash, key); Do {/ / chain table lookup the if (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) return e; } // loop through the list, while ((e = e.next)! = null); } } return null; } Duplicate codeCopy the code

5.3 HashTable

Unlike HashMap, HashTable is implemented in a completely different way, as can be seen from the class inheritance relationship between the two. Although both HashTable and HashMap implement the Map interface, HashTable inherits the DIctionary abstract class. HashMap inherits the AbstractMap abstract class.

5.3.1 Class inheritance diagram of HashTable

HashTable

HashMap

5.3.2 Dictionary interface

public abstract class Dictionary<K,V> { public Dictionary() { } public abstract int size(); public abstract boolean isEmpty(); public abstract Enumeration<K> keys(); public abstract Enumeration<V> elements(); public abstract V get(Object key); public abstract V put(K key, V value); public abstract V remove(Object key); } Duplicate codeCopy the code

The Dictionary class has a comment that throws a null pointer NullPointerException when the key is null, indicating that HashTabel does not allow a null key.

// Throws NullPointerException if the {@code key} is {@code null}.</pre> Copies the codeCopy the code

5.3.3 HashTable composition

/** * The hash table data. */ private TRANSIENT Entry<? ,? >[] table; /** * The total number of entries in the hash table. */ private transient int count; /** * The table is rehashed when its size exceeds this threshold. (The * value of this field is (int)(capacity * loadFactor).) * Rehash threshold * @serial */ private int threshold; /** * The load factor for the hashtable. * @serial */ private float loadFactor; Copy the codeCopy the code

The elements of HashTable exist in Entry[] table, which is an array of entries. The entries are the nodes where the entries are stored. Each Entry is a linked list.

5.3.4 Entries in a HashTable

final int hash; final K key; V value; Entry<K,V> next; Copy the codeCopy the code

Entry is a single linked list, the same structure as Node in HashMap, but TreeNode is a subclass of Node in HashMap.

5.3.5 put method

public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<? ,? > tab[] = table; int hash = key.hashCode(); // Position in array 0x7fffffff is 31 bits binary 1 int index = (hash & 0x7fffffff) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry ! = null ; Entry = entry.next) {// Replace the old value if traversing the list finds it and return if ((entry.hash == hash) && entry.key.equals(key)) {V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null; } Duplicate codeCopy the code

If the hash value and key are the same as the put key, replace the old value. Otherwise, use addEntry to add a new value into the table, because adding new elements involves changing the size of the element and may require expansion, etc. For details, see the addEntry method below.

private void addEntry(int hash, K key, V value, int index) { Entry<? ,? > tab[] = table; // If the expansion needs to recalculate the hash, If (count >= threshold) {// Rehash the table if the threshold is exceeded Rehash (); tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) tab[index]; TAB [index] = new Entry<>(hash, key, value, e); count++; modCount++; } Duplicate codeCopy the code

tab[index] = new Entry<>(hash, key, value, e); Copy the codeCopy the code

This line of code is the actual method of inserting a new element, using header interpolation, which is common for single-linked lists (fast).

5.3.6 get method

@SuppressWarnings("unchecked") public synchronized V get(Object key) { Entry<? ,? > tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry<? ,? > e = tab[index] ; e ! = null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return (V)e.value; } } return null; } Duplicate codeCopy the code

Get is a much simpler method that hashes, finds the index, traverses the list to find the value, and returns NULL if there is none. As you can see, methods in HashTable are modified with synchronized, so their operations are thread-safe, but inefficient.

The last

Recently in view of the Internet company interview asked knowledge points, summed up the Java programmer interview involves most of the interview questions and answers to share with you, I hope to help you review before the interview and find a good job, but also save you on the Internet to search for information time to learn.

Content covers: Java, MyBatis, ZooKeeper, Dubbo, Elasticsearch, Memcached, Redis, MySQL, Spring, SpringBoot, SpringCloud, RabbitMQ, Kafka, Linux and other technology stacks.

Full version Java interview questions address: Java backend questions integration