Collections Framework

Collection Overview

A collection is a container used to save and manipulate a set of objects. Java collection classes encapsulate data structures such as arrays, linked lists, hash tables, and trees, and provide a unified interface.

Compared to arrays, collections usually have the following characteristics:

• Collection length can change dynamically.
• Collection can only store reference types directly, and basic types will be converted to wrapper classes through automatic boxing.
• Different sets have their own characteristics in terms of finding, inserting, deleting, sorting, and de-duplication.

When selecting a collection, a comprehensive judgment should be made based on whether index is needed, whether duplication is allowed, whether order is required, whether key-value mapping is required, and concurrency requirements.

collective framework structure

Collection Is a top-level interface of a single-column collection. Common methods include add()、addAll()、contains()、remove()、clear()、size() and iterator()。

List、Set and Queue belong to Collection system;Map Save key-value mapping without inheriting Collection。

the List interface

List Represents an ordered, repeatable sequence of elements and provides index-based operations.

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add(1, "C");

System.out.println(list.get(0));
System.out.println(list.indexOf("C"));
list.set(0, "AA");
list.remove(1);

ArrayList

ArrayList Internally use expandable arrays to store elements.

Characteristics of ArrayList

• Access to elements based on indexes is fast and typically has a time complexity of O(1)。
• Adding elements at the end is usually faster, but you need to copy the array when expanding.
• Inserting or deleting elements in the middle requires moving subsequent elements, which is usually in time complexity of O(n)。
• Not a thread-safe collection.

Design of a simplified version of ArrayList

Implement a simplified version ArrayList When, you can use the following fields:

private Object[] data;
private int size;

data.length Represents the current capacity,size Represents the actual number of elements. Valid element index ranges are 0 to size - 1。

capacity expansion

Before adding an element, if size == data.length, you need to create a larger array and copy the elements.

private void ensureCapacity() {
    if (size < data.length) {
        return;
    }

    int newCapacity = data.length == 0 ? 10 : data.length + (data.length >> 1);
    data = Arrays.copyOf(data, newCapacity);
}

Capacity expansion ratio needs to strike a balance between reducing the number of copies and controlling free memory.

additive element

public boolean add(Object value) {
    ensureCapacity();
    data[size++] = value;
    return true;
}

When inserting an element at a specified location, the allowed index range is 0 to size, among them size Represents tail insertion.

public void add(int index, Object value) {
    checkPositionIndex(index);
    ensureCapacity();

    System.arraycopy(data, index, data, index + 1, size - index);
    data[index] = value;
    size++;
}

Get, modify, and delete elements

public Object get(int index) {
    checkElementIndex(index);
    return data[index];
}

public Object set(int index, Object value) {
    checkElementIndex(index);
    Object oldValue = data[index];
    data[index] = value;
    return oldValue;
}

public Object remove(int index) {
    checkElementIndex(index);
    Object oldValue = data[index];

    int moved = size - index - 1;
    if (moved > 0) {
        System.arraycopy(data, index + 1, data, index, moved);
    }
    data[--size] = null;
    return oldValue;
}

After deleting, set the free location to null, you can prevent the collection from continuing to hold useless object references.

Find and clear

public int indexOf(Object value) {
    for (int i = 0; i < size; i++) {
        if (Objects.equals(value, data[i])) {
            return i;
        }
    }
    return -1;
}

public boolean contains(Object value) {
    return indexOf(value) >= 0;
}

public void clear() {
    Arrays.fill(data, 0, size, null);
    size = 0;
}

Objects.equals() Can correctly handle ordinary objects and null。

LinkedList

LinkedList Internally uses a double linked list to store elements and implements List and Deque Interface.

Each node typically holds current data, a previous node reference, and a subsequent node reference. The linked list object also holds the head node, tail node, and number of elements.

Characteristics of LinkedList

• When node locations are known, insertion and deletion only require modification of adjacent node references.
• Searching by index requires moving one by one from the head or tail, and the time complexity is usually O(n)。
• Each node needs to save additional front and back references, and the memory overhead is usually greater than ArrayList。
• Not a thread-safe collection.

Simplified node structure

private static class Node {
    private Object data;
    private Node prev;
    private Node next;

    Node(Object data, Node prev, Node next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }
}

Add node to tail

public boolean add(Object value) {
    Node oldLast = last;
    Node newNode = new Node(value, oldLast, null);
    last = newNode;

    if (oldLast == null) {
        first = newNode;
    } else {
        oldLast.next = newNode;
    }

    size++;
    return true;
}

Find nodes based on index

You can compare the index with size / 2Decide whether to start looking at the head or the tail.

private Node getNode(int index) {
    checkElementIndex(index);

    if (index < (size >> 1)) {
        Node current = first;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }

    Node current = last;
    for (int i = size - 1; i > index; i--) {
        current = current.prev;
    }
    return current;
}

remove nodes

private Object unlink(Node node) {
    Node previous = node.prev;
    Node next = node.next;

    if (previous == null) {
        first = next;
    } else {
        previous.next = next;
        node.prev = null;
    }

    if (next == null) {
        last = previous;
    } else {
        next.prev = previous;
        node.next = null;
    }

    Object oldValue = node.data;
    node.data = null;
    size--;
    return oldValue;
}

Queue and stack usage for LinkedList

Queue Queue

Queues usually follow first-in, first-out rules. recommended offer()、poll() and peek(), which use the return value to represent the result when the operation fails or the queue is empty.

Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");

System.out.println(queue.poll());
System.out.println(queue.peek());

Deque double ended queue

Deque Elements can be added and removed from both ends, or used as a stack.

Deque<String> stack = new LinkedList<>();
stack.push("A");
stack.push("B");

System.out.println(stack.pop());
System.out.println(stack.peek());

New code usually uses Deque replace the old Stack Class.

ArrayList, LinkedList, and Vector

cannot be simply assumed LinkedList All insertions and deletions of ArrayList Come on. If you still need to find the location by index first, the overall operation may still be O(n)。

generic

Generics take types as arguments, allowing the compiler to check types at compile time and reduce cast.

Classes and interfaces generics

public class Test<E, F> {
    public F method(E value) {
        return null;
    }
}

public interface ITest<PK> {
    void method(PK value);
}

Generic type parameters usually use a single upper case letter, such as T、E、K and V。

generic method

Generic methods declare their own type parameters before returning the type.

public static <T> T first(T[] values) {
    return values.length == 0 ? null : values[0];
}

Method generics and class generics are independent of each other.

Specify generic types

Test<String, Integer> test = new Test<>();

When a subclass inherits a generic parent class or implements a generic interface, you can specify a specific type.

public class SubTest extends Test<String, Integer>
        implements ITest<Person> {

    @Override
    public Integer method(String value) {
        return value.length();
    }

    @Override
    public void method(Person value) {
        System.out.println(value);
    }
}

Using raw types will lose compile-time type checking, and “unspecified generics” should not be simply understood as safe Object Generics.

List rawList = new ArrayList(); // 不推荐

Generics do not have covariance

even Student is Person subclass of,List<Student> nor List<Person> Subtypes of.

// List<Person> people = new ArrayList<Student>(); // 编译错误

Arrays are covariance, but errors may be delayed until run time.

Person[] people = new Student[3];
// people[0] = new Person(); // 运行时抛出 ArrayStoreException

wildcard

? Represents an unknown type.

upper bound wildcard

? extends Person Represents an unknown Person Subtype, suitable for reading data.

public static void printPeople(List<? extends Person> people) {
    for (Person person : people) {
        System.out.println(person);
    }
}

addition to null In addition, it is usually not safe to add concrete objects to the collection because the actual element type is unknown.

Lower bound wildcard

? super Student said Student or its parent type, suitable for writing Student object.

public static void addStudent(List<? super Student> people) {
    people.add(new Student());
}

You can use “producer use extends, consumer use super”Help remember.

Collections tool class

Collections Is a set algorithm tool class,Collection Is a collection interface, and the two have different meanings.

Batch add and sort

List<String> values = new ArrayList<>();
Collections.addAll(values, "cac", "bcd", "abc");
Collections.sort(values);

element realization Comparable When, natural order can be provided.

public class Person implements Comparable<Person> {
    private int age;
    private double height;

    @Override
    public int compareTo(Person other) {
        int ageResult = Integer.compare(age, other.age);
        if (ageResult != 0) {
            return ageResult;
        }
        return Double.compare(height, other.height);
    }
}

use Integer.compare() Such methods can avoid integer overflows caused by direct subtraction.

When you need to temporarily change the comparison rules, you can pass in Comparator。

Collections.sort(people, new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.getScore(), p2.getScore());
    }
});

compareTo() and compare() Should return negative, zero, or positive numbers, and exactly return is not required -1、0、1。

other commonly used methods

• binarySearch(): Performs a binary lookup in an ordered list.
• replaceAll(): Replace all equal elements.
• shuffle(): Randomly shuffle the list order.
• swap(): Swap elements at two index positions.
• synchronizedList(): Returns to the synchronous packaging list.

When traversing the synchronized wrapper collection, it still needs to be externally synchronized according to the document requirements. Synchronization of a single method does not mean that a set of composite operations is automatically atomic.

Map interface

Map Use keys and values to save mappings. Key cannot be repeated, repeated calls put() Old values are replaced; values can be repeated.

Map<String, Integer> map = new HashMap<>();
map.put("001", 100);
map.put("002", 200);
map.put("002", 300);

System.out.println(map.get("001"));
System.out.println(map.containsKey("002"));
System.out.println(map.containsValue(300));
map.remove("002");

different Map Implementations have different provisions for order, null keys, sorting, and thread safety.

HashMap

HashMap Use a hash table to save key-value mappings. Ideally, the average time complexity for finding, adding, and deleting is close to O(1), but worst-case and actual performance depend on hash distribution, conflicts and capacity.

basic structure

Java 8 ‘s HashMap It mainly consists of arrays, linked lists and red-black trees.

The default load factor is 0.75, the capacity expansion threshold is usually the capacity multiplied by the load factor.

Key-value pairs are encapsulated as node objects, and the node implements Map.Entry Interface.

The default constructor does not immediately create a file with a length of 16 , storage tables are usually delayed initialization to the default capacity when first inserted.

The process of adding elements

to HashMap When adding key-value pairs, the main process is as follows:

1. Calculate the hash value of the key and perform perturbation processing.

2. Calculate the bucket index using the array length and hash value. When the capacity is a power of two, bit operations are usually used instead of ordinary residue.

3. Create nodes directly when the bucket is empty.

4. When the bucket is not empty, the hash value and equals() Determine whether the same key exists.

5. Replace the value if the key already exists; otherwise add the new node to the linked list or red-black tree.

6. Expand capacity when the number of elements exceeds the threshold.

In Java 8, when the number of linked list nodes in a single bucket reaches the tree-based threshold, the array capacity must also be checked. When the capacity is insufficient, priority is usually given to capacity expansion; only when the capacity meets the requirements will it be converted to a red-black tree. It cannot be simply expressed as “the linked list reaches a certain length and must be treed.”

HashMap allow one null keys and multiple null Value, but is not a thread-safe collection.

Requirements for key objects

If an object as a key is overridden equals(), must be rewritten correctly at the same time hashCode()。key deposit HashMap After that, it should not be modified to participate equals() or hashCode() Calculated field, otherwise the key may not be found again.

Common Map implementations

Hashtable

Hashtable Is an old synchronous map and is not allowed null bond or null value. New code is usually selected based on the scenario HashMap, synchronous packaging or ConcurrentHashMap。

TreeMap

TreeMap Based on a red-black tree, sorting according to the natural order of the keys or specifying a comparator.

TreeMap<Integer, String> map = new TreeMap<>(
        Comparator.reverseOrder()
);
map.put(100, "100");
map.put(80, "80");
map.put(120, "120");
System.out.println(map);

When the comparator determines that two keys are equal,TreeMap They will be treated as the same key, so the comparison rules should be consistent with the business equality semantics.

LinkedHashMap

LinkedHashMap Maintain a double linked list based on a hash table. Iterates in insertion order by default, or can be configured in access order through a constructor. It is often used to implement simple LRU caching.

Map<String, Integer> map = new LinkedHashMap<>();
map.put("b", 10);
map.put("a", 11);
map.put("c", 12);
System.out.println(map);

Set interface

Set Duplicate elements are not allowed. Whether to maintain the order or sorting is determined by the specific implementation, and all cannot be Set All are summarized as disorder.

HashSet

HashSet internal use HashMap Save elements, collect elements as keys, and use internal fixed objects for values.

Set<String> set = new HashSet<>();
set.add("a");
set.add("b");
set.add("a");
set.add("c");
System.out.println(set);

Whether an element is duplicate is mainly determined by hashCode() and equals() Decide jointly.

LinkedHashSet

LinkedHashSet Maintain insertion order while removing duplication.

Set<String> set = new LinkedHashSet<>();
Collections.addAll(set, "b", "a", "c", "a");
System.out.println(set);

TreeSet

TreeSet Sort according to natural order or comparator, and use whether the comparison result is zero to determine whether the elements are duplicate.

Set<String> set = new TreeSet<>(
        Comparator.comparingInt(String::length)
                .thenComparing(Comparator.naturalOrder())
);
set.add("baaaa");
set.add("a");
set.add("ccc");
set.add("bbb");
System.out.println(set);

If the comparator only compares string lengths, different strings of the same length will be considered duplicate elements, so secondary comparison rules need to be added.

Iterator iterator

Iterable interface provides iterator() Methods,Iterator Interface unifies the traversal of different collections.

Common methods are as follows:

• hasNext(): Determine if there is a next element.
• next(): Returns the next element; thrown if there are no elements NoSuchElementException。
• remove(): Delete the most recent time next() Whether the returned element is supported or not depends on the specific iterator.

Traverse List

List<String> list = new ArrayList<>();
Collections.addAll(list, "a", "b", "c");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String value = iterator.next();
    if ("c".equals(value)) {
        iterator.remove();
    }
}

A direct call to the collection’s structural modification method during traversal usually triggers a quick failure check and throws a ConcurrentModificationException。Use the iterator’s own remove(), or modify them uniformly after the traversal is over.

Traverse Set

Set<String> set = new HashSet<>();
Collections.addAll(set, "a", "b", "c");

Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

Traverse Map

Map Not realized in itself Iterable, usually through entrySet()、keySet() or values() Get an iterable view.

Map<String, String> map = new HashMap<>();
map.put("101", "a");
map.put("102", "b");
map.put("103", "c");

for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "," + entry.getValue());
}

Can be traversed when only keys are needed keySet(), you can traverse only when values are needed values()。

Enhance the for loop

enhance for Loops can traverse arrays and implement Iterable object.

for (String value : list) {
    System.out.println(value);
}

When traversing a collection, enhance for Iterators are used at the bottom of the loop, so unsupported structural modifications to the collection cannot be made directly within the loop.

When traversing an array, the compiler generates loop logic based on the array index, rather than using the Iterator。

String[][] values = {
    {"a", "b"},
    {"c", "d"}
};

for (String[] row : values) {
    for (String value : row) {
        System.out.println(value);
    }
}

Needs to be modified based on index List Element, you can use ordinary for cycle or ListIterator。