Analysis of Java collection List and Map

Collection classes are stored in Java There are three main types of util package: set, list and map

  • Collection: collection is the most basic interface of collection List, Set and Queue
  • Map: is the basic interface of the mapping table


1, Collection

List is an ordered Collection. List has three implementation classes: ArrayList, Vector and LinkedList


1.1 ArrayList

The most commonly used List implementation class, which is internally implemented through an array, allows fast random access to elements. The disadvantage of the array is that there can be no interval between each element. When the size of the array is not enough, the storage capacity needs to be increased, and the data of the existing array must be copied to the new storage space. When inserting or deleting elements from the middle of ArrayList, the array needs to be copied, moved and expensive. Therefore, it is suitable for random search and traversal, not for insertion and deletion


1.1.1 structure

Nonparametric structure (common)

/**
 * Constructs an empty list with an initial capacity of ten.
 * It is said here that an empty list with a capacity of 10 will be initialized, but it is not in the code
 * In the next step, we usually add elements, so the real initialization is in the add method
 */
public ArrayList() {
	// Here, elementData is the stored data, which is an array type. At the beginning, a default {} will be assigned
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

Parametric construction (initialization capacity)

/**
 * Constructs an empty list with the specified initial capacity.
 * The value you pass in will be used as the capacity size here
 */
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);
    }
}

Parameterized construction (incoming Collection)

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * Constructs a list containing the elements of the specified collection and returns them in the order in which the iterator of the collection returns them
 */
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

1.1.2 common methods


add to

add(E): boolean

Here we mainly talk about the method to determine the internal capacity of ensureCapacityInternal, and start to look at the source code

// The parameter here is the length required to add the next element to your list, which is size + 1
private void ensureCapacityInternal(int minCapacity) {
   ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

In fact, one layer after another, three methods are called

calculateCapacity: calculate capacity

// If elementData is empty at present, the minCapacity you passed in will be replaced with default_ Capability, that is, 10 will be returned
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

ensureExplicitCapacity: judge whether the capacity is sufficient

private void ensureExplicitCapacity(int minCapacity) {
   modCount++;
   // overflow-conscious code
   // When add ing for the first time, minCapacity will be changed to 10, and the length will still be 0,
   if (minCapacity - elementData.length > 0)
       grow(minCapacity);
 }

Growth: This is the key to determine the capacity and expansion of ArrayList

private void grow(int minCapacity) {
    // overflow-conscious code
    // Record the original array length
   int oldCapacity = elementData.length;
   // Bit operation, the new length is 1.5 times of the original
   int newCapacity = oldCapacity + (oldCapacity >> 1);
   // If it is the first time, newCapacity is 0 and minCapacity is 10. Here is the first capacity value
   if (newCapacity - minCapacity < 0)
       newCapacity = minCapacity;
   // If the maximum capacity limit is exceeded, hugeCapacity will be called to obtain the maximum value after capacity expansion
   if (newCapacity - MAX_ARRAY_SIZE > 0)
       newCapacity = hugeCapacity(minCapacity);
   // minCapacity is usually close to size, so this is a win:
   // Expand the array to a specified size
   elementData = Arrays.copyOf(elementData, newCapacity);
}

hugeCapacity: the maximum value Max needs to be adjusted here_ ARRAY_ Size for a discussion

/**
 * Integer.MAX_VALUE = 2^31-1 = 2147483647, The definition here is to subtract 8 for the following reasons
 * 1.Store headwords   
 * 2.Avoid some machine memory overflow and reduce the probability of error
 * In fact, if the header length information is greater than 8, even if you subtract 8, it will still OutOfMemoryError, so it is just avoided as far as possible
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // Here we can see that the real maximum length of ArrayList is actually integer MAX_ VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

add(int, E): void

Insert data in the specified location. If there is data in this location, move it all backward to see the system Arraycopy method

public void add(int index, E element) {
	// Check index out of bounds
    rangeCheckForAdd(index);
	// Determine capacity
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    /**
     * Copy the original array to the new array
     * Parameter 1: original array
     * Parameter 2: starting position of original array
     * Parameter 3: target array
     * Parameter 4: starting position of target array
     * Parameter 5: length of copy
     */
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

addAll(Collection<? extends E> c): boolean

All elements in the given collection are added to the arraylist

addAll(int index, Collection<? extends E> c): boolean

All elements in the given collection are added to the arraylist at the specified location


modify

set(int index, E element): E

It is used to replace the element of the specified index in the dynamic array. If the index position element does not exist, an error will be reported

replaceAll(UnaryOperator operator): void

Replace each element in the array with the given operation content

// Change all elements to uppercase
words.replaceAll(e -> e.toUpperCase());

// Multiply all elements by 2
numbers.replaceAll(e -> e * 2);

delete

remove(int index): E

Deletes the element at the specified location

remove(Object o): boolean

Delete the specified element to store null, pass in null, delete null, and call fastRemove

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
    	// The main reason is that moving the array is not all OK
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

removeAll(Collection<?> c): boolean

private boolean batchRemove(Collection<?> c, boolean complement) {
	// This can be equivalent to declaring a new array. The w variable will be used as the index length of the new array
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
        	// If the value of complexity is false, it is called by removeAll, and if the value is true, it is used to find the intersection of retainAll
            if (c.contains(elementData[r]) == complement)
            	// During the delete operation, the data stored here is the retained data, and 0 to w are all the index values of the array after the deletion is completed
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        // Only when an exception occurs in the try code is it possible r= Size, assign the remaining elements of the original array to the new array
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        // Judge whether the length of the new array is equal to the length of the original array. If it is different, assign null to all elements after w, and then wait for GC to recycle it
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

removeIf(Predicate<? super E> filter): boolean

Delete all array elements that meet specific conditions

// Delete all even elements
array01.removeIf(e -> (e % 2) == 0);
// Delete the element with - bak in the name
names.removeIf(e -> e.contains("-bak"));

removeRange(int fromIndex, int toIndex): void

Delete elements in index range

clear(): void

Assign each element in elementData null and wait for GC to recycle


lookup

get(int index): E

No need to say more

indexOf(Object o): int

Returns the index value of o this element in the dynamic array for the first time. If it does not exist, - 1 is returned

lastIndexOf(Object o): int

Returns o the position of the last occurrence of this element in the dynamic array. If it does not exist, - 1 is returned

contains(Object o): boolean

To judge whether an element is in a dynamic array is indexof (o) > = 0

forEach(Consumer<? super E> action): void

New methods in Java 8

// Output element
list.forEach((sss)-> System.out.println(sss));
list.forEach(System.out::println);

// Writable logic processing
list.forEach((sss)-> {});

Other operations

size(): int

isEmpty(): boolean

ensureCapacity(int minCapacity): void

Set the specified capacity size

trimToSize(): void

Adjust the capacity in the dynamic array to the number of elements in the array

toArray(): Object[]

Convert ArrayLsit to Object type array

toArray(T[] a): T[]

If the length is less than the length of the shape parameter group, null will be automatically supplemented

retainAll(Collection<?> c): boolean

Judge whether there is intersection. The batchRemove method is also called. The second parameter is true

clone(): Object

Shallow copy a dynamic array without copying the object itself. The old and new objects still share the same memory

sort(Comparator<? super E> c): void

Sorts the elements in a dynamic array in the specified order

// String alphabetic elements are arranged in ascending order
words.sort(Comparator.naturalOrder());

// Compare Integer fields in entity classes
list.sort(new Comparator<Student>(){
   @Override
   public int compare(Student arg0, Student arg1) {
	   // Eliminate null values of sort fields
	   if (arg0.getAge() == null || arg1.getAge() == null) return 0;
	   // This is the order
	   return arg0.getAge().compareTo(arg1.getAge());
   }
});

subList(int fromIndex, int toIndex): List

Intercepts and returns a part of the dynamic array. The header does not include the tail

spliterator(): Spliterator<E>

Separable parallel traversal element iterator


1.2 LinkedList

It is realized through array and supports thread synchronization. Only one thread can write Vector at a time to avoid inconsistency caused by multiple threads writing at the same time. Realizing synchronization requires a high cost, so it is slower than accessing ArrayList


1.3 Vector

The linked List structure is used to store data, which is suitable for dynamic insertion and deletion of data. The speed of random access and traversal is relatively slow. It also provides methods not defined in the List interface, which are specially used to operate header and footer elements, and can be used as stacks, queues and bidirectional queues


2, Map

2.1 HashMap

  • HashMap stores data according to the hashCode value of the key. In most cases, it can directly locate its value, so it has fast
    But the traversal order is uncertain
  • HashMap can only allow the key of one record to be null at most, and the value of multiple records to be null
  • HashMap is not thread safe, that is, multiple threads can write HashMap at any time, which may lead to inconsistent data. If you need to meet thread safety, you can use the synchronized map method of Collections to make HashMap thread safe, or use ConcurrentHashMap


Java 8 implementation

Java 8 uses the red black tree, which is composed of array + linked list + red black tree



When searching, we can quickly locate the specific subscripts of the array according to the hash value, but then we need to compare them one by one along the linked list to find what we need. The time complexity depends on the length of the linked list, which is O(n). In order to reduce this overhead, in Java 8, when there are more than 8 elements in the linked list, the linked list will be converted into a red black tree. When searching in these locations, the time complexity can be reduced to O(logN)


2.2 HashTable

  • Hashtable is a legacy class. The common functions of many mappings are similar to HashMap. The difference is that it inherits from the Dictionary class and is thread safe. Only one thread can write hashtable at any time
  • Concurrency is not as good as that of ConcurrentHashMap, because ConcurrentHashMap introduces segmentation lock
  • Hashtable is not recommended to be used in new code. When thread safety is not required, HashMap can be used. When thread safety is required, ConcurrentHashMap can be used to replace it

2.3 TreeMap

  • The SortedMap interface is implemented. The records it saves can be sorted according to the key. The default key value is in ascending order, and the sorting comparator can also be specified
  • When traversing TreeMap with Iterator, the records obtained are sorted. It is recommended to use TreeMap for sorted mapping
  • When using TreeMap, the key must implement the Comparable interface or pass in the custom Comparator during construction, otherwise it will throw Java. Com at runtime Lang.classcastexception exception

2.4 LinkedHashMap

  • A subclass of HashMap, which saves the insertion order of records
  • When traversing with Iterator, the records obtained first must be inserted first, or they can be sorted according to the access order with parameters during construction

summary

To be continued

Keywords: Java data structure HashMap arraylist

Added by louisA2A on Sun, 30 Jan 2022 17:59:59 +0200

Popular Keywords

©2024 Programming VIP