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 something, I am very happy, if you have doubts, I am also willing to seek with you! This paper consists of 3.5w words and 25 pictures. It is expected to take 2h to read. Bookmark this article in case you don’t find it, it’s probably the most detailed article you’ll ever see. We’ve compiled the 2021 Java interview questions.
1. Set framework
The entire Java Collection framework is shown in the figure above (Map is not included here, the structure of Map will be described after the Collection). It can be seen that the top-level interface of all Collection implementation classes is Iterable and Collection interface, and then the 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 <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 codeThe Iterable interface has only iterator(), which is also an interface. There are 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 codeThe main interface methods visible to Collection are:
2, the List
List indicates a List of ordered collections. The meaning of the List interface is different from that of the Collection interface.
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 codeWe can see that List actually has more add methods than Collection add and addAll search methods get,indexOf,set and other methods, and support index subscript operation. What is the difference between Collection and List? A. The biggest difference between Collection and List is that Collection is unordered and does not support index operations, while List is ordered. Collection has no concept of order. B. ListIterator is ListIterator. C. The List interface supports the use of the sort method. D. The Spliterator operations are different. ** Why does a subclass interface repeatedly specify a parent interface? ** Official explanation: The parent interface is declared repeatedly in the subinterface for easy documentation. For example, in the Java Doc document, you can also see the Collecion declaration interface in the List interface.
2.2 List Implements ArrayList
ArrayList is one of the most common implementation classes of the List interface. It supports some of the column operations of the List interface.
2.2.1 ArrayList inheritance Relationship
2.2.2 ArrayList composition
private static final Object[] EMPTY_ELEMENTDATA = {}; Private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} Private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} // non-private to simplify nested class access private int size;Copy the codeIt is important to remember that the Transient Object[] elementData in ArrayList is the actual container for the elements, so ArrayList is 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;
}
Copy the code- Object[] elementData is the array in which ArrayList actually holds data.
- ArrayList supports a default size construct, as well as an empty construct, where Object[] elementData is an empty array {}.
2.2.4 Adding elements to ArrayList
>public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Copy the codeNote that ArrayList has a modCount attribute that indicates the number of times the instance has been modified. (All collections have a modCount attribute that keeps track of the number of changes). Each increment increases the number of changes to the ArrayList. 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; }Copy the codeIf the initialized list is an empty ArrayList, it is directly expanded to DEFAULT_CAPACITY, which is a default value of 10. When more elements are added to an ArrayList than the array can hold, it expands. Notice this line of code
int newCapacity = oldCapacity + (oldCapacity >> 1);
Copy the codeUsing the right shift operation, is the original general, so it is 1.5 times the expansion. Let’s say 10 in binary is 1010, and 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);
}
Copy the code2.2.5 copy an array
Java is not able to allocate its own space, is the underlying C and C++ implementation. For example, in C, we know that an array is a pointer to the head, so let’s say we allocate memory to an array in C. Java implements array replication through arrayCopy, a native method.
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
Copy the codep = (int *)malloc(len*sizeof(int));
Copy the codeWhat are the benefits? In Java, memory is managed by the JVM, and arrays are allocated contiguous memory. Arraylists are not necessarily contiguous memory. Of course, the JVM will do this for us.
2.2.6 according to? ElementData is transient.
-
The purpose of transient is that this property does not participate in serialization.
-
ArrayList inherits the Serializable interface that marks serialization
-
The arrayList is serialized with read and write security controls. 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 codeAs you can see in the serialization method writeObject(), we write out the default method, then write out size, and finally iterate out elementData. Since the variable is transient, we write it out manually so that it will also be serialized. Is that unnecessary?
protected transient int modCount = 0;
Copy the codeOf course not. There is a key modCount variable that keeps track of the number of changes to the list. If the number of changes is not the same as before the serialization was started, an exception will be thrown and the serialization will fail. This ensures unmodified data during serialization and ensures serialization security. (This is how Java collections are implemented)
2.3 LinkedList
We all know that LinkedList is a LinkedList structure, so how to implement LinkedList in Java?
2.3.1 LinkedList inheritance
LinkedList is an implementation of both the List interface and the Queue (Deque), so it supports more functionality than ArrayList. It can be used as a Queue, but the Queue implementation is not emphasized in the following sections.
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 codeA LinkedList consists of a head node and a tail node, pointing to the head and tail of the list, respectively. The Node source code in the LinkedList is as follows, consisting of the current value item and Pointers to the previous Node prev and the next Node next. It contains only one constructor, constructed in the order of arguments such as (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 codeWhat is the structure of Node in LinkedList? LinkedList consists of a head node, a tail node, and a size that defaults to 0, so it is bidirectional.
<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() { }Copy the codeData structure of the linked list of the head insert method linkFirst and the tail insert method linkLast
/** * 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. Void 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++; }Copy the code2.3.3 Querying LinkedList
** : the get method obtains the index of a node.
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Copy the codeHow is the node(index) method implemented? Determine whether the index is closer to the head or the tail, and which segment is closer to which traversal to get the value.
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 codeTo query the index modification method, find the corresponding node first and 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;
}
Copy the codeThis is also why ArrayList random access is faster than LinkedList **. LinkedList has to iterate to find the location to make changes, whereas ArrayList is an internal array, which is faster.
2.4.3 How to modify LinkedList
When you add a node, you can see that you put the new node in the tail by tail insertion.
public boolean add(E e) {
linkLast(e);
return true;
}
Copy the code2.5 the Vector
Like ArrayList, Vector is an implementation of the List interface. The main implementation classes of the List interface are ArrayLIst, LinkedList, Vector, and Stack, among which the latter two are especially seldom used.
2.5.1 vector composition
It’s basically the same as ArrayList.
// Protected Object[] elementData; // The number of valid elements is protected int elementCount; // Protected int capacityIncrement;Copy the code2.5.2 Vector thread safety
Vector is a thread-safe, synchronized operation method.
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); }Copy the codeIf no capacityIncrement is created, expand the array by two times; otherwise, add capacityIncrement each time.
2.5.4 Classic example of vector methods
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; If (numMoved > 0) System. Arraycopy (elementData, index+1, elementData, index, numMoved); ElementData [--elementCount] = null; // Let gc do its work return oldValue; }Copy the codeThere is one main two lines of code to note, and I have comments in the code. When an element is removed from an array and moved, make sure the original end is set to null and the effective length is reduced 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 Stack is rarely used in the development process because of performance reasons. However, Stack is a very important data structure at the bottom of the computer.
2.6.1 Stack Inheritance
Stack inherits from Vector and is an implementation of the List interface. As mentioned earlier, Vector is thread-safe because its methods are synchronized, so the operations that Stack inherits from Vector are also thread-safe.
2.6.2 Using Stack
Just as Stack is the implementation of the Stack, its main operations are push and pop, and the most important 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 code
As you can see from the above code, the string “CCC” that was pushed last on the stack was also pushed first.
2.6.3 Stack source
/** * Stack(Jdk8) */ public class Stack<E> extends Vector<E> {public Stack() {} public E push(E item) { addElement(item); return item; } // Exit the stack, find the last element of the array, remove it and return it. 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; }Copy the codeWe use the addElement (E E) method of the Vector to put the elements at the end of the collection. We use the removeElementAt(Index x) method of the Vector to removeElementAt(Index x). Remove and retrieve the end of the set, so that Stack operates on the end of the linear table.
3, the Queue
As described in the data structure, a queue is a first-in, first-out data structure, or first in first out. You can think of a queue as a container in which you can only put elements from one segment, and you can only take elements from the other end. The mechanism is shown below, but it is important to note that the queue does not specify which end to insert and which segment to pull from.
3.1 What is Deque
The full name of a Deque is a Double Ended queue. This means that the queue container can be inserted from either the head or the tail, and can be obtained from either the head or the tail, as shown in the following figure.
Queue interface in 3.1.1 Java
Notice here that in Java, queues are explicitly inserted from the tail and taken from the head, so all implementations of queues in Java are taken from the head.
package java.util; Public interface Queue<E> extends Collection<E> {Boolean add(E E); Boolean offer(E E); // Remove elements. If the collection is empty, throw an exception E remove(); // Remove the queue header element and return, if null, null E poll(); // Query the first element of the collection. If null, throw E element(); // Query the first element in the queue. If null, return null E peek(); }Copy the code
The common methods used by The Java Queue are shown in the table. The differences between the methods for interfaces in the table and those not in the table are as follows: queue operations do not throw an exception because the queue is empty, while collection operations do not throw an exception because the queue is empty.
3.1.2 Deque interface
package java.util; Public interface Deque<E> extends Queue<E> {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 the stack and collection interface methods}Copy the codeJust like the methods in Queue, the methods that end in First or Last, the methods that end in First are the methods that work from the head, and Last is the methods that work from the tail.
3.1.3 Queue, the implementation of Deque
Java implementations of Queue are mainly dual-ended queues, after all, more convenient and free operation, Queue implementation is PriorityQueue, Deque in Java.util, ArrayDeque and LinkedList are two implementations, one is based on the array implementation, One is based on a linked list implementation. As mentioned in the previous LinkedList article, it is a two-way LinkedList, on which the Deque interface is implemented.
3.2 PriorityQueue
PriorityQueue is the only direct implementation of the Queue interface in Java, as its name suggests, a PriorityQueue, with internal support for ordering internal elements according to certain rules.
3.2.1 PriorityQueue inheritance
First look at the inheritance of the PriorityQueue, we know that it is the implementation class of Queue, the main way to use the basic operation of Queue, and mentioned before the basic principle of Queue, its core is FIFO (First In First Out) principle. The Java implementation of PriorityQueue is also queue-compliant, but with a slight difference in the priority of the PriorityQueue, which is a priority-enabled queue and is not a FIFO when it uses the priority feature.
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+"->"); }Copy the code
What this code does is put 10 ints into the Queue, and then use the poll() method of Queue to fetch them one by one. The result is that each of the ints is the smallest value in the Queue, which shows that there are certain ordering rules within the 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 code
The above code overrides the compareTo method to return 0, i.e. no prioritization. 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 {a=14}, and the order in which we put it, so it’s important to note that when we implement the Comparable interface, we must prioritize it according to certain rules. We’ll look at the source code to see why the order in which we pull it is different from the order in which we put it.
3.2.3 PriorityQueue composition
Private static final int DEFAULT_INITIAL_CAPACITY = 11; private static final int DEFAULT_INITIAL_CAPACITY = 11; /** * Array of elements */ Transient Object[] queue; // private int size = 0; // private int size = 0; /** * a custom comparison rule that is preferred when available, otherwise use the Comparable interface method implemented by the element. */ private final Comparator<? super E> comparator; / / transient int modCount = 0; / / transient int modCount = 0; // non-private to simplify nested class accessCopy the codeAs you can see, the composition of a PriorityQueue is very simple, remembering an array of elements and a Comparator.
3.2.4 Operation method of PriorityQueue
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; if (I == 0) queue[0] = e; else siftUp(i, e); return true; }Copy the codeThe first thing you can see is that when the Queue is empty, the first element is placed directly at the beginning of the array, so the first 20 in case 2 is placed at the beginning of the array. When the queue is not empty, siftUp(I, e) is used, passing in the number of existing elements in the queue and the number of new elements to be put in. 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); }Copy the codeRemember that the PriorityQueue consists of an array of elements and a Comparator. When there is no Comparator, the compareTo method is implemented using the element class. The meaning is that the custom comparison rule Comparator is used first, or the Comparable interface method implemented by the element’s class is used.
private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; While (k > 0) {// why -1, think of array position 0, 1, 2. 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; }Copy the codeAs you can see, when a new element is inserted into a non-empty PriorityQueue, the new element is heap-sorted (heap-sorted is not described here), so that the element is heap-sorted every time you enter, which ensures that the first element in the Queue is always the smallest (the default rule is 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]; x = (E) queue[s]; queue[s] = null; if (s ! = 0) siftDown(0, x); return result; }Copy the codeHere we know that when a value is taken 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; k = child; } queue[k] = key; }Copy the codeWhen there is no Comparator the siftDown method is used as above, because the index 0 position is taken out, find the child node of index 0 which is smaller than it as the new parent node and recurse in the loop. Is the PriorityQueue simple? I won’t go into the details.
3.3 ArrayDeque
ArrayDeque is a dual-ended queue implemented in Java based on an array. There are two implementations of a Deque in Java, LinkedList and ArrayDeque. As the name indicates, LinkedList is based on a two-way LinkedList. And ArrayDeque is based on arrays.
3.3.1 Inheritance of an ArrayDeque
ArrayDeque is an implementation of the Deque interface, unlike LinkedList, which is an implementation of both the List interface and 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"); System.err. Println (deque.peekfirst ()); System.err.println(deque.peekLast());Copy 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+"->"); }Copy the code
PollLast () = “CCC”, “aaa”, “BBB”, “DDD”;
3.3.4 ArrayDeque Internal components
// The size of the array must be a power of 2 transient Object[] elements; // non-private to // Transient int head index; // Transient int index; // Transient int index; Private static final int MIN_INITIAL_CAPACITY = 8; private static final int MIN_INITIAL_CAPACITY = 8;Copy the code3.3.5 Length of Array Elements
Here the length of the elements array is always a power of 2. The implementation here is basically the same as in hashMap, that is, ensure that the length of the binary array consists of all 1’s, and then add 1 to make it 100… So it must be a power of 2.
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; }Copy the code3.3.6 ArrayDeque Implementation Mechanism
As shown in the figure below:
Here we should think of the array as end-to-end, with both the header and tail indexes 0 initially, addLast to the right and addFirst to the left, so the array might be empty in the middle. When the header and tail Pointers meet, we 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();
}
Copy the codeNote the following line of code: head=head-1 if head-1 is greater than or equal to 0, otherwise head=elements. Length -1.
head = (head - 1) & (elements.length - 1)
Copy the codeOr another way to write it is down here, is that the direction of the addFirst pointer up here?
head = head-1>=0? head-1:elements.length-1Copy the codeThis is the magic of bit operations, because any number that is ampersand to a number larger than it, which is all binary 1s, is equal to itself, such as 1010&1111 = 1010, which is not covered here. Look again 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();
}
Copy the codeThe same note has a string of magic code.
(tail = (tail + 1) & (elements.length - 1))
Copy the codeTail = tail+1>element-1? 0:tail+1, is not a very magical writing method, the principle is that a binary number consisting of all 1 and a number greater than it, the result of the &operation is 0, such as 10000&1111 = 0. The poll method and the add method are the opposite logic.
4. Set
If a List adds order to a Set, then a Set adds uniqueness to a Set.
4.1 the Set interface
The Set interface and Colletion interface in Java are exactly the same definition.
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 code4.2 HashSet
A HashSet in Java is, as its name suggests, a collection of Hash implementations using the underlying structure of a HashMap.
4.2.1 HashSet inheritance
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 codeYou can see that inside the HashSet is actually a HashMap.
4.2.3 How do Hashsets ensure that they are not repeated?
You can see that in the Add method of the HashSet, the value inserted will be the key of the HashMap, so it’s the HashMap that makes it unique. The map put method returns null if it adds a value that does not already exist, or the original value if it already exists. See below for details on how HashMap is implemented!
4.3 LinkedHashSet
LinkedHashSet is also used less, which is also based on the Set implementation.
4.3.1 LinkedHashSet inheritance
Like HashSet, it is an implementation class of the Set interface and 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, loadFactor) {public LinkedHashSet(int initialCapacity, loadFactor, float 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 codeIt works exactly the same way as a HashSet, so what’s the difference? 1. LinkedHashSet is a subclass of HashSet.2.LinkedHashSet implements LinkedHashMap for storing values, while HashSet uses HashMap. The superclass constructor called in the LinkedHashSet, you can see that the column is actually a LinkedHashMap.
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
Copy the codeThe implementation of The LinkedHashSet is very simple, a deeper understanding needs to look at the implementation of the LinkedHashMap, the analysis of the LinkedHashMap will be presented separately.
5, the Map
A Map is a key-value structure, often called a key-value structure. A Map is made up of a number of k-V key-value pairs. A K-V structure is called an Entry. The figure above shows one of the most basic constructs of the Map family (just in java.util). We’ve compiled the 2021 Java interview questions.
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 codeThe Map interface itself is a top-level interface, consisting of a bunch of Map interface methods and an Entry interface. The Entry interface defines some operations on key-value itself. The Map interface defines some attributes and some interface methods for attribute lookup and modification.
5.2 a HashMap
A HashMap is the most commonly used K-V container in Java. It is implemented in the form of a hash. A HashMap stores key-value pairs called entries. Make it a linked list or tree structure and store it in a HashMap container (which is an array).
5.2.1 HashMap inheritance
5.2.2 Data stored by 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 its subclass, which is a red-black tree type. The inheritance structure diagram is as follows:
What is the data that the HashMap holds the data? The container for storing the data in the code is as follows:
transient Node<K,V>[] table;
Copy the codeThis implies that the container is composed of one node after another, and there are three implementations of node, so the form of node stored in a hashMap can be either node or TreeNode.
5.2.3 Composition of HashMap
With these concepts in mind, let’s take a look at what constitutes a HashMap.
// The minimum capacity of the hashMap is 16. The capacity is the size of the array, i.e., the variable, transient Node<K,V>[] table. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // the maximum value of this array is 2^31. static final int MAXIMUM_CAPACITY = 1 << 30; Static final float DEFAULT_LOAD_FACTOR = 0.7f; static final float DEFAULT_LOAD_FACTOR = 0.7f; For example, if there is a node in an array, the list of nodes will be converted to a red-black tree only if it reaches this length. static final int TREEIFY_THRESHOLD = 8; Static final int UNTREEIFY_THRESHOLD = 6; 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; // Transient Node<K,V>[] table; Entry< k, v >> entrySet; // transient Set< map. Entry< k, v >> entrySet; // The number of transient int size keys stored in the hashMap; // Transient int modCount; // Final float loadFactor;Copy the codeTable refers to an array of data, bin refers to a node in a table, a node can be understood as a batch/box of data.
5.2.4 Constructor * in HashMap
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, take the maximum 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 array is a power of 2 and is greater than initialCapacity. this.threshold = tableSizeFor(initialCapacity); }Copy the codeThe tableSizeFor() method guarantees that the array size must be a power of 2. How does that work?
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;
}
Copy the codeThis method changes all digits after 1 to 1, and then adds 1, so that the binary number must be 100… It looks like this. The implementation here uses a similar approach in the ArrayDeque implementation to ensure that the length of the array must be a power of two.
5.2.5 put method
The put method used by developers:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
Copy the codeReal HashMap internal use of put value method:
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 to the position is null, If ((p = TAB [I = (n-1) & hash]) == null) TAB [I] = newNode(hash, key, value, hash) 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 a linked list, iterating, notice that e = p.ext this will assign 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_threshold_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; }Copy the code5.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 is used to find the position of the Key in the table, which is an array of each Node in the HashMap. (first = tab[(n - 1) & hash]) ! = null) {// The Node may be a linked list or tree. 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; } while ((e = e.ext)! = null); } } return null; }Copy the code5.3 HashTable
Unlike HashMap, HashTable is implemented in a completely different way. This can be seen in the class inheritance relationship between the two. Although both HashTable and HashMap implement the Map interface, HashTable inherits from the DIctionary abstract class. HashMap inherits from the AbstractMap abstract class.
5.3.1 Class inheritance diagram for 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);
}
Copy the codeThere is a comment in the Dictionary class that throws a NullPointerException when the key is null, which also indicates that HashTabel does not allow a null key.
//throws NullPointerException if the {@code key} is {@code null}.</pre>
Copy the code5.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).) * @serial */ private int threshold; /** * The load factor for the hashtable. * @serial */ private float loadFactor;Copy the codeHashTable elements are stored in Entry[] table, which is an array of entries. Each Entry is a linked list.
Entry in 5.3.4 HashTable
final int hash;
final K key;
V value;
Entry<K,V> next;
Copy the codeJust know that Entry is a single linked list. It has the same structure as a HashMap Node, but HashMap also has a subclass of Node called TreeNode.
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(); Int index = (hash & 0x7FFFFFFf) % tab.length; // In the array position 0x7FFFFFFf is a 31-bit 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) {// If ((entry.hash == hash) && entry.key.equals(key)) {V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null; }Copy the codeIf the hash value and key are the same as the put key, replace the old value. Otherwise, use the addEntry method to add a new value to the table. Adding a new element involves changing the element size, and may need to be expanded. See the addEntry method below.
private void addEntry(int hash, K key, V value, int index) { Entry<? ,? > tab[] = table; // If capacity expansion requires recalculating 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++; }Copy the codetab[index] = new Entry<>(hash, key, value, e);
Copy the codeThis line of code is the actual way to insert the new element, using the header method, which is usually used for singly 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; }Copy the codeThe get method is much simpler. It just hashes, finds the index, iterates through the list and finds the corresponding value. If not, it returns null. As you’ve already seen, HashTable methods are modified with synchronized, so their operations are thread-safe, but their efficiency is compromised.