preface

HashMap ConcurrentHashMap java-based HashMap ConcurrentHashMap Let’s take a look at the age-old ArrayList and LinkedList. Compared with Map, the List structure is a relatively simple data structure, so I intend to introduce the two data structures together. Again, we’ll give you a step-by-step introduction, and compare the differences between these two data structures, so that you can clearly understand how to use them in work and interviews.

ConcurrentHashMap: juejin.cn/post/696089…

[A thorough understanding of the past and present life of Hashmap] : juejin.cn/post/695958…

The ArrayList.

1.1. Key Concepts

ArrayList is the most frequently used collection of list-type data structures in everyday work. Its internal data structure is an array, which is located by hash. The query efficiency is O (1), and the new insert efficiency is O (n), making it unsafe for threads.

1.2. Introduction of key variables

// ArrayList Default array size Private static final Int DEFAULT_CAPACITY = 10; Private static final Object[] EMPTY_ELEMENTDATA = {}; // EMPTY_ELEMENTDATA = {}; Private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; Ephemeral Object[] elementData; ephemeral Object[] elementData; // List existing element size private int size; // AbstractList < hashMap > < hashMap > < hashMap > < hashMap >Copy the code

1.3. Introduction of core methods

1.3.1. Constructors

Public ArrayList(int initialCapacity) {// If the variable passed is greater than 0, If (initialCapacity > 0) {this.elementData = new Object[initialCapacity]; Else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA; Else {throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);} else {throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }} public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; ArrayList public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) ! = 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

1.3.2. The add method

Public Boolean add(E E) {ensureCapacityInternal(size + 1); ElementData [size++] = e; elementData[size++] = e; elementData[size++] = e; return true; } public void add(int index, E element) {rangeCheckForAdd(index); EnsureCapacityInternal (size + 1); Arraycopy (elementData, index, elementData, index + 1, size-index); arrayCopy (elementData, index, elementData, index + 1, size-index); // Insert element elementData[index] = element; // index add size++; }Copy the code

The add method is relatively simple in general, without any complicated logic, the core ideas are several in recapacityInternal method and System. Arraycopy method, let’s see where it is.

1.3.2.1. EnsureCapacityInternal

Private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }Copy the code
DEFAULTCAPACITY_EMPTY_ELEMENTDATA (EMPTY_ELEMENTDATA); EMPTY_ELEMENTDATA private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; }Copy the code

DEFAULTCAPACITY_EMPTY_ELEMENTDATA differs from EMPTY_ELEMENTDATA.

  • If you use the empty parameter constructor new ArrayList(), elementData.length=10 after adding an element, the initialization capacity is large;
  • Elementdata.length =10 if you use the parameterized constructor new ArrayList(0) or new ArrayList(empty Collection), add an element, elementData.length=10.
  • Elementdata.length =1 when adding an element to the new ArrayList(0) constructor, initialization is small;

Private void ensureExplicitCapacity(int minCapacity) {private void ensureExplicitCapacity(int minCapacity) {modCount++; If (minCapacity - elementdata. length > 0) grow(minCapacity); }Copy the code
Private void grow(int minCapacity) {int oldCapacity = elementData.length; // the newCapacity is 1.5 times the original length int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; If (newCapacity -max_array_size > 0) // Ensure the maximum array capacity newCapacity = hugeCapacity(minCapacity); ElementData = array.copyof (elementData, newCapacity); }Copy the code

1.3.2.2.System.arraycopy

Native JDK method, array copy, very efficient, the bottom call C/C ++

1.3.3. The get method

Public E get(int index) {// rangeCheck(index); Return elementData(index); }Copy the code

1.3.4. The remove method

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}


public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
Copy the code

The simple way to do this, without comments, is to delete the target element and move the array one bit to the left.

1.4 summary

1.ArrayList contains an Object[] array. Different constructors have different initialization capacities.

2. The target capacity is calculated before adding elements. If the capacity is insufficient, the new array length is 1.5 times that of the original array.

3.ArrayList is suitable for scenarios where there are many queries but few additions and deletions.

4.ArrayList collections are not thread-safe.

2. LinkedList

2.1. Key Concepts

LinkedList is a collection of underlying linked-list structures that, in contrast to ArrayList, is slower to find and faster to add and delete.

2.2. Key variables

// Set element number transient int size = 0; // A transient Node<E> first; // A transient Node<E> last; Protected TRANSIENT int modCount = 0;Copy the code

2.3. Introduction of core methods

2.3.1. Constructors

Public LinkedList() {} public LinkedList(Collection<? extends E> c) { this(); addAll(c); }Copy the code
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
Copy the code
public boolean addAll(int index, Collection<? Extends E> c) {checkPositionIndex(index); [] a = c.toarray (); Int numNew = a.length; // Check the length of the array. If 0, return false to indicate that no element was added. if (numNew == 0) return false; Pred Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; For (Object o: a) {@suppressWarnings ("unchecked") E E = (E) o; for (Object o: a) {@suppressWarnings ("unchecked") E E = (E) o; Node<E> newNode = new Node<>(pred, e, null); If (pred == null) first = newNode; if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; If (succ == null) {last = pred; if (succ == null) {last = pred; } else {// otherwise, pred next index to succ, succ prev index to pred pred.next = succ; succ.prev = pred; } // Update the size of the current list and return true to indicate that the list was successfully added size += numNew; modCount++; return true; }Copy the code

2.3.2. The add method

Public Boolean add(E E) {linkLast(E); return true; } public void addFirst(E E) {linkFirst(E); } public void addLast(E E) {linkLast(E); }Copy the code
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++; } 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++; }Copy the code

For the added element, add a node to the end of the list using a pointer to the end of the member variable queue.

2.3.3. The get method

Public E get(int index) {checkElementIndex(index); Return node(index).item; Public E getFirst() {final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; Public E getLast() {final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }Copy the code
If (index < (size >> 1)) {Node<E> x = first; 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 code

2.3.4. The remove method

The remove method supports more, here does not do the specific expansion, the overall logic with get method and add method combination can see the thing, is almost linked list traversal, splicing

2.4 summary

  1. LinkedList is a two-way LinkedList. It can also operate as a stack, queue, or double-endian queue.
  2. LinkedList is fast to add and delete, but slow to find.
  3. LinkedList is asynchronous.

ArrayList vs. LinkedList

1.ArrayList is an array and LinkedList is a two-way list. ArrayList feels superior to LinkedList for random access to GET and set because LinkedList moves the pointer. 3. For add and remove operations, LinedList has an advantage because ArrayList moves data.

Of course, this is not absolute, the conclusion is based on a large amount of data

1. ArrayList performs even better than LinkedList if the newly deleted data is at the end of the queue and does not need to be expanded

2. The data to be searched is at the head of the team or at the end of the team. The efficiency of the two is the same, because the LinkedList maintains the pointer to the end of the team and the head of the team, and the data can be directly obtained

3. Add and delete When the amount of data is small, less than 30, the efficiency of the two is similar without significant difference; When the volume of data is large, starting at about 1/10 of the volume, the efficiency of LinkedList is not as high as that of ArrayList. Especially, when the volume of data is inserted in the half and the second half, the efficiency of LinkedList is obviously lower than that of ArrayList, and the larger the volume of data, the more obvious. It is also mentioned in this paper that array copy of ArrayList is implemented based on native method of C, which has high performance. However, when adding and modifying LinkedList method, nodes need to be created or deleted, and pointer relationship needs to be maintained, which will be difficult after a large amount of data

4. The subList method exists in both classes and is not recommended as it is a reference to the original collection. Both data and structural changes have a two-way effect. Changes to subsets of data that affect the parent without being aware of them are a common mistake in subList development.

4. Reference

1. Juejin. Cn/post / 684490…

2. Juejin. Cn/post / 684490…

3. blog.csdn.net/eson_15/art…

Five. Contact me

It’s not easy to write a post, like it, comment it, follow it

Nailing: louyanfeng25

WeChat: baiyan_lou