From the beginning of this article, a new series will be released, the name is “Follow me to DACHang-Interview series”, in this topic, I will collect the knowledge of interviews in mainstream dachang-interview with answer analysis. In addition, both large and small factories require handwriting algorithm for interviews. I will also provide two algorithm questions in the form of special topics in each article of this series. You can review the corresponding interview questions and then brush through the algorithm, so that you can gradually accumulate. So without further ado, let’s start our interview questions – Basics section.

Common collection classes

The Map and Collection interfaces are the parent interfaces of all collections frameworks:

  • The subinterfaces of the Collection interface include Set interface and List interface
  • The Map interface implementation classes include HashMap, TreeMap, Hashtable, ConcurrentHashMap, and Properties
  • The main implementation classes of Set interface are: HashSet, TreeSet, LinkedHashSet and so on
  • List interface implementation classes are: ArrayList, LinkedList, Stack and Vector, etc

List the differences between the three subclasses of the interface

  • ArrayList 

Is a resizable array. As more elements are added to the ArrayList, their size grows dynamically. The internal elements can be accessed directly through the GET and set methods, because an ArrayList is essentially an array.

  • LinkedList 

Is a double-linked list that performs better than ArrayList when adding and deleting elements. However, it is weaker than ArrayList in terms of GET and set. Of course, these comparisons are in the case of a large amount of data or a very frequent operation. If the amount of data and computation is small, then the comparison will be meaningless.

  • Vector 

Similar to ArrayList, but in a strongly synchronized class. If your program itself is thread-safe (thread-safe, not sharing the same collection/object across multiple threads), then ArrayList is a better choice. Vector and ArrayList request more space as more elements are added. Vector requests double its size at a time, whereas ArrayList increases its size by 50% at a time. The LinkedList also implements the Queue interface, which provides more methods than List, including Offer (),peek(),poll(), and so on. Note: The initial capacity of an ArrayList is very small by default, so it is best practice to allocate a large initial value if you can predict the amount of data to reduce resizing overhead.

How do YOU make an ArrayList thread-safe

  1. The JDK utility classes provide it for us. Collections. SynchronizedList () method actually bottom also is in the collection of all the methods above, plus the synchronized (defaults to using the same monitor object, can you specify).
  2. Copy On Write is also an important idea. In the scenario of less Write and more read, in order to ensure the thread safety of the collection, we can get a Copy of the original data in the current thread and then operate it. The JDK collections framework provides an implementation of ArrayList: CopyOnWriteArrayList.

HashMap1.7 with 1.8

JDK1.8 mainly addresses or optimizes the following issues:

  1. Resize Capacity expansion optimization
  2. Red black tree is introduced to avoid the query efficiency caused by the excessively long single list
  3. It solves the problem of multi-threaded dead-loop, but it is still non-thread-safe

What is a red-black tree

Red-black tree is a special binary search tree. Each node of a red-black tree has a memory bit to indicate the color of the node, which can be Red or Black.

  • Every node of a red-black tree is black or red
  • If a node is red, its children must be black.
  • Each node passes through the same number of black nodes to the leaf node

Why is the HashMap initial value 2 to the NTH power

Key.hashcode () and key.hashcode ()>>>16 are xor operations. The 16 bits of key.hashcode () are xor operations. The high 16bit remains the same, while the low 16bit and high 16bit make an xor to reduce collisions. Index = (2 to the NTH power – 1) & hash (2 to the NTH power – 1) After considering the speed, function, and quality, the designers use xOR of high and low 16bits to simplify the process to reduce collisions, and JDK8 uses O (logn) tree structure to improve performance under collisions.

The PUT process of the HashMap

  1. Check whether the key-value pair array table[I] is empty or null; otherwise, perform resize() for expansion.
  2. Table [I]==null; if table[I] is not null, go to ⑥; if table[I] is not null, go to ③;
  3. Check whether the first element of table[I] is the same as the first element of key.
  4. Check whether table[I] is a treeNode, that is, whether table[I] is a red-black tree. If table[I] is a red-black tree, insert a key-value pair directly into the tree; otherwise, change to 5.
  5. Table [I] is traversed to determine whether the length of the linked list is greater than 8. If the length is greater than 8, the linked list is converted into a red-black tree and the insertion operation is performed in the red-black tree; otherwise, the insertion operation of the linked list is carried out. If the key already exists in the traversal process, the value can be overwritten directly.
  6. After the insert is successful, check whether the number of existing key value pairs size exceeds the maximum capacity threshold. If so, expand the capacity.

How does hashMap expand

This is also an optimization of JDK1.8. In 1.7, after expansion, it is necessary to re-calculate the Hash value and distribute it according to the Hash value. In 1.8, it is necessary to determine whether (e.hash & oldCap) is 0 based on the location of the same bucket. The location of the element either stays at the original location or moves to the original location + the increased array size

Why wrapper classes like String and Integer in HashMap are suitable for keys?

The features of wrapper classes such as String and Integer ensure the immodification of Hash values and the accuracy of calculation, effectively reducing the probability of Hash collisions

Why not use the hash value of hashCode() as the subscript of the table

The hashCode() method returns an int integer ranging from -(2 ^ 31) to (2 ^ 31-1), which is about 4 billion mapping Spaces. The size of a HashMap ranges from 16 (the default value) to 2 ^ 30. It is also difficult to provide so much storage space on the device that the hash calculated by hashCode() may not be within the array size and thus not match the storage location

  • HashMap implements its own hash() method, which makes the high and low bits of its hash value perform xOR operation by itself through two perturbations, reducing the probability of hash collision and making the data distribution more even.
  • When the array length is a power of 2, it is more efficient to use the hash() value and (&) (array length -1) to get the index of the array. H &(length-1) is equivalent to h%length. Thirdly, the problem of “the hash value does not match the array size range” is solved.

TreeMap

  • A TreeMap is an ordered set of key-values implemented through a red-black tree.
  • TreeMap is implemented based on a red-black tree. The map is sorted according to the natural order of its keys, or according to the Comparator provided when the map was created, depending on the constructor used.
  • TreeMap is thread asynchronous.

A HashMap with the HashTable

  • The main difference is that Hashtable is thread-safe, while HashMap is not.
  • A Hashtable does not allow null keys or values, whereas a HashMap can have null keys.
  • The implementation is different: Hashtable inherits from Dictionary classes, while HashMap inherits from AbstractMap classes.
  • The initial capacity of HashMap is 16, and that of Hashtable is 11. The default load factor of both is 0.75.
  • The capacity expansion mechanisms are different. If the existing capacity is greater than the total capacity x load factor, the HashMap capacity expansion rule is double the current capacity, and the Hashtable capacity expansion rule is double the current capacity + 1.
  • Iterators in a HashMap are fail-fast, whereas enumerators in a Hashtable are not fail-fast.

ConcurrentHashMap Low-level concrete implementation

ConCurrentHashMap 1.8 has the following main changes compared to 1.7:

  • The Segment + HashEntry + Unsafe implementation is Synchronized + CAS + Node + Unsafe. But HashEntry is an inner class. Synchronized + CAS is used to replace the Segment, so that the granularity of the lock is smaller, and the lock is not needed every time. CAS is used to attempt to write values to the bucket position of the array. If the value fails, the spin is guaranteed to succeed, and the lock will only be added when hash collision is generated to assign values to the linked list or red-black tree. And only the head of the list (the root of a red-black tree) needs to be locked.
  • When the put() method initializes the array size, 1.8 is unlocked because of the sizeCtl variable. Setting this variable to -1 indicates that the table is being initialized.

Why does ConcurrentHashMap use synchronized in jdk1.8 instead of reentrant locking

  1. Reduce memory overhead

Assuming that reentrant locks are used for synchronization support, each node needs to inherit AQS for synchronization support. However, not every node needs to be synchronized. Only the head node of the linked list (the root node of the red-black tree) needs to be synchronized, which is a huge waste of memory.

  1. Get JVM support

Reentrant locking is, after all, at the API level, leaving little room for further performance optimization. Synchronized is directly supported by the JVM and can be optimized at run time: lock coarsening, lock elimination, lock spin, and so on. This allows synchronized to gain performance gains with JDK versions without changing the code.

What is the fail – fast

Is a mechanism in Java collections that throws Concurrent Modification Exceptions when iterators iterate over a collection object and modify (add, delete, modify) the contents of the collection object during the iteration. Use a modCount variable during traversal. If the contents of the collection change during traversal, the value of modCount is changed. Whenever the iterator iterates over the next element using hashNext()/next(), it checks whether the modCount variable is expectedmodCount and returns the traversal if it is; Otherwise, an exception is thrown and the traversal is terminated.

Implementation principle of HashSet

As for HashSet, it is implemented based on HashMap. HashSet uses HashMap to store all elements at the bottom level, so the implementation of HashSet is relatively simple. Operations related to HashSet are basically completed by directly calling related methods of underlying HashMap. Essentially, a HashMap puts a key, and the value is a fixed Obj.

Private Public Protect Description Properties left and right range

Algorithm part (1) stack and queue

The queue consists of two stacks

Requirement: Write a class with two stacks to implement the queue. Satisfy the basic operation idea of queue: the characteristics of stack is first in and last out, and the characteristics of queue is first in and first out. We use two stacks just to reverse the order for queue-like operations. But there are two things to note here:

  1. If a stackPush pushes data into a stackPop, the data in the stackPush must be pushed all at once.
  2. If the stackPop is not empty, stackPush must never push data into the stackPop.

Errors can occur if you violate both of these points.

public class TwoStack {

    Stack<Integer> stackPush = new Stack<>();
    Stack<Integer> stackPop = new Stack<>();

    public void add(int intPush){
        stackPush.push(intPush);
    }

    public int myPeek(a){
        if (stackPush.isEmpty() && stackPop.isEmpty()) {
            throw  new RuntimeException("");
        }else{
            if(! stackPush.isEmpty()){while(stackPop.isEmpty()){ stackPop.push(stackPush.pop()); }}}returnstackPop.peek(); }}Copy the code

Using one stack to sort another stack

If you want to sort the stack from top to bottom, you are allowed to apply for only one stack. In addition, you can apply for new variables, but not additional data structures. The stack to be sorted is called stack and the secondary stack to be requested is called help. Perform the pop operation on the stack, and the popup element is denoted as cur. Its core logic is as follows:

  • If help is not empty and cur is less than the top element in help then pop the top element of help back onto the stack. First cycle judgment
  • If cur is greater than or equal to help, the top element goes directly to help
public class OrderStack {
    public void orderStackVal(Stack<Integer> stack){
        Stack<Integer> help = new Stack<>();

        while(! stack.isEmpty()){ Integer cur = stack.pop();while(! help.isEmpty() && cur < help.peek()) { stack.push(help.pop()); } help.push(cur); } System.out.println(help); }public static void main(String[] args) {

        OrderStack orderStack = new OrderStack();
        Stack<Integer> stack = new Stack<>();
        stack.push(5);
        stack.push(3);
        stack.push(4);
        stack.push(2);
        stack.push(1);
        orderStack.orderStackVal(stack);
    }
Copy the code

Reverse stack data using recursion and stack

Requirements: For example, if a stack is pushed into 1, 2, 3, 4 and 5 in sequence, the numbers from the top of the stack to the bottom of the stack are 5, 4, 3, 2 and 1 respectively. Transpose the stack, from the top of the stack to the bottom of the stack 1, 2, 3, 4, 5, which is the implementation of the stack elements in reverse order, but can only be implemented using recursive functions, no other data structure.

We need two recursive functions. The first recursion is to find the element at the bottom of the stack and return it. The second one takes the result of the first recursion and puts it on the new stack.

public class ReverseOrder {

    // Recursively query the bottom element of the stack
    public static int getStackLast(Stack<Integer> stack) {
        Integer result = stack.pop();
        if (stack.isEmpty()) {
            return result;
        } else {
            int stackLast = getStackLast(stack);
            stack.push(result);
            returnstackLast; }}// Call the recursion at the bottom of the query stack
    public static void reverse(Stack<Integer> stack) {
        if(stack.isEmpty()){
            return ;
        }
        int stackLast = getStackLast(stack);
        reverse(stack);
        // Call the following after recursion
        stack.push(stackLast);
        System.out.println(stack);
    }

    public static void main(String[] args) {

        ReverseOrder orderStack = new ReverseOrder();
        Stack<Integer> stack = new Stack<>();
        stack.push(5);
        stack.push(3);
        stack.push(4);
        stack.push(2);
        stack.push(1); orderStack.reverse(stack); }}Copy the code