This issue is the second issue of the [Online interviewer] series, which mainly focuses on high-frequency interview questions.

Reply to [interview] obtain Dabin's carefully sorted interview Manual of the big factory, which has helped many small partners win big factory offer s!

Interview site

Interviewer: Hello, this is interviewer xxx. Are you Dabin?

Dabin: Hello, interviewer. I'm Dabin

Interviewer: is it convenient for the interview now?

Dabin: Yes, you can

Interviewer: let's start the interview now

Interviewer: look, your resume says that you are familiar with collection related content. Do you know Java List?

Dabin: Well, List is an interface. The common implementation classes are ArrayList and LinkedList

Interviewer: what's the difference between the two implementation classes?

Monologue: old eight part essay, ha ha

Dabin: the underlying data structure of ArrayList is array, which supports subscript access and fast data query. The default initial value is 10. When the capacity is insufficient, it will be expanded

Dabin: the underlying data structure of LinkedList is a linked list. Adding elements to the end of the linked list does not require capacity expansion

Interviewer: Uh huh. Just now you mentioned the expansion of ArrayList. Tell me more about it?

Monologue: good guy, I knew you would ask this. The eight part essay is ready.

Dabin: the source code of ArrayList expansion is as follows:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  //Capacity expansion
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

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);
}

Dabin: you can see that the capacity of the array is expanded by 1.5 times in the grow th method.

Dabin: for example, if the initialization value is 8, when the 9th element is added, it is found that the array space is insufficient, and the capacity will be expanded to 12.

Dabin: after capacity expansion, arrays will be called The copyof () method copies the array.

Interviewer: Well, that's good. What scenarios are ArrayList and LinkedList applicable to respectively?

Dabin: for the get and set methods of random index access, ArrayList is faster than LinkedList. Because ArrayList finds elements directly through array subscripts; LinkedList moves the pointer through each element until it is found.

Dabin: LinkedList is faster than ArrayList in adding and deleting elements. Because ArrayList may expand and copy the array when adding and deleting elements; The addition and deletion of LinkedList only need to modify the pointer.

Dabin: therefore, ArrayList is suitable for scenes with more queries and less additions and deletions. LinkedList is suitable for scenarios with less queries and more additions and deletions

Interviewer: what's the difference between Set and List?

Dabin: List accesses elements by index. Elements are ordered. Elements can be repeated and multiple nulls can be inserted; Set cannot store duplicate elements, which are unordered. Only one null is allowed to be inserted.

Dabin: there are two ways to realize the bottom layer of List: array and linked List; Set is implemented based on Map. The element value in set is the key value of Map.

Interviewer: do you know Vector?

Dabin: Well, Vector is the underlying structure and array. Now Vector is basically not used because the efficiency of operating Vector is relatively low. Compared with ArrayList, it is thread safe. When the capacity is expanded, the capacity is doubled.

Interviewer: Well, do you know any thread safe lists?

Dabin: you can use collections The synchronizedlist () method returns a thread safe List.

Dabin: there is another way to use CopyOnWriteArrayList.

Interviewer: Well, just now you mentioned CopyOnWriteArrayList. Tell me more about its principle?

Monologue: This is too voluminous. One word disagreement is the underlying principle

Dabin: CopyOnWriteArrayList is a thread safe List. The bottom layer is realized by copying arrays.

Dabin: the so-called CopyOnWrite is to copy when writing.

Dabin: when we add elements to a container, instead of directly adding them to the container, we first copy the current container, copy a new container, and then add elements to the new container. After adding elements, we point the reference of the original container to the new container.

Dabin: the advantage of this is that the CopyOnWrite container can be read concurrently without locking, because the current container will not be modified.

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock(); //The add method needs to be locked
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1); //Copy new array
        newElements[len] = e;
        setArray(newElements); //The reference of the original container points to the new container
        return true;
    } finally {
        lock.unlock();
    }
}

Interviewer: can you talk about the disadvantages of CopyOnWriteArrayList?

Dabin: there are two main problems.

Dabin: memory occupation problem. Due to CopyOnWrite's copy on write mechanism, when writing, the memory of two objects will be stationed in the memory at the same time.

Dabin: the CopyOnWrite container cannot guarantee the real-time consistency of data, and may read old data.

Interviewer: Well, yes.

Interviewer: how to sort the List when you ask some common problems in development?

Dabin: you can use the sort method of list itself or collections Sort (list) method.

Interviewer: how to remove an element when traversing ArrayList?

Dabin: if you use foreach to delete elements, it will lead to fast fail. You can use the remove() method of the iterator to avoid the fast fail problem.

Iterator itr = list.iterator();
while(itr.hasNext()) {
      if(itr.next().equals("dabin") {
        itr.remove();
      }
}

Interviewer: the foundation is pretty good! Go back and wait for notice

Dabin: OK, thank you

Monologue: go back and wait for notice? It won't be cold