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 single-column collection of top-level interfaces. Common methods include add(), addAll(), contains(), remove(), clear(), size() and iterator().

List, Set and Queue all belong to the Collection system; Map saves key-value mappings and does not inherit 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 uses an expandable array to store elements.

Characteristics of ArrayList

Access to elements based on indexes is fast and 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 O(n) in time complexity.
Not a thread-safe collection.

Design of a simplified version of ArrayList

When implementing the simplified version of ArrayList, you can use the following fields:

private Object[] data;
private int size;

data.length represents the current capacity, and size represents the actual number of elements. The valid element index range is 0 to size - 1.

capacity expansion

Before adding elements, 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 elements at specified locations, the allowed index range is 0 to size, where 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;
}

Setting the free location to null after deletion 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 at the same time.

LinkedList

LinkedList internally uses a bidirectional linked list to store elements, and implements the List and Deque interfaces.

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 / 2 to decide 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. offer(), poll(), and peek() are recommended, which use return values to represent results when an 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 can add and remove elements from both ends, and can also be 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 to replace the old Stack class.

ArrayList, LinkedList, and Vector

integrates	internal structure	main features
`ArrayList`	Dynamic array	index access is fast, intermediate insertion and deletion requires moving elements
`LinkedList`	Double-way linked list	is slow to access by index, and can be used as a queue or a double ended queue
`Vector`	dynamic array	old-style synchronization set, single method call with synchronization overhead

It cannot be simply assumed that all insertions and deletions of LinkedList are faster than ArrayList. If you still need to search for the location by the 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 reducing 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 though Student is a subclass of Person, List<Student> is not a subtype of List<Person>.

// 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 unknown type.

upper bound wildcard

? extends Person represents an unknown subtype of Person, suitable for reading data.

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

Except for null, it is usually not safe to add concrete objects to the collection because the actual element types are unknown.

Lower bound wildcard

? super Student represents Student or its parent type and is suitable for writing to Student objects.

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

You can use “Producers use extends, Consumers use super” to help remember.

Collections tool class

Collections is a set algorithm tool class, and Collection is a set interface. The two have different meanings.

Batch add and sort

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

When elements implement Comparable, 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);
    }
}

Using methods such as Integer.compare() 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());
    }
});

Both compareTo() and compare() should return negative, zero or positive numbers, and it is not required to return exactly -1, 0, and 1.

other commonly used methods

binarySearch(): Performs binary search in an ordered list.
replaceAll(): Replace all equal elements.
shuffle(): Randomly shuffle the list order.
swap(): Swap elements at two index positions.
synchronizedList(): Return 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 uses keys and values to store mapping relationships. The key cannot be repeated, and repeated calls to put() will replace the old value; the value 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 regulations for order, empty key, sorting, and thread safety.

HashMap

HashMap uses a hash table to store 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 mainly consists of arrays, linked lists and red-black trees.

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

Key-value pairs are encapsulated as node objects, and the nodes implement the Map.Entry interface.

The default constructor does not immediately create arrays of length 16, and storage tables are usually delayed initialized to the default capacity when first inserted.

The process of adding elements

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

Calculate the hash value of the key and perform perturbation processing.
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.
Create nodes directly when the bucket is empty.
When the bucket is not empty, determine whether the same key exists by using the hash value and equals().
Replace the value if the key already exists; otherwise add the new node to the linked list or red-black tree.
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 allows one null key and multiple null values, but is not a thread-safe collection.

Requirements for key objects

If equals() is rewritten as an object as a key, hashCode() must be rewritten correctly at the same time. After the key is stored in HashMap, the fields that will participate in the calculation of equals() or hashCode() should not be modified, otherwise the key may not be found again.

Common Map implementations

Hashtable

Hashtable is an old synchronous map that does not allow null keys or null values. The new code usually selects HashMap, synchronous packaging or ConcurrentHashMap based on the scenario.

TreeMap

TreeMap is based on a red-black tree and sorted according to the natural order of keys or a specified 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 will treat them as the same key, so the comparison rules should be consistent with the business equality semantics.

LinkedHashMap

LinkedHashMap maintains 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 does not allow duplicate elements. Whether to keep order or sort depends on the specific implementation, and all Set cannot be summarized as out of order.

HashSet

HashSet internally uses HashMap to store 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 elements are repeated is mainly determined by hashCode() and equals().

LinkedHashSet

LinkedHashSet maintains the insertion order while removing duplication.

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

TreeSet

TreeSet sorts according to natural order or comparator, and uses whether the comparison result is zero to determine whether 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

The Iterable interface provides the iterator() method, and the Iterator interface unifies the traversal methods of different sets.

Common methods are as follows:

hasNext(): Determine whether there is a next element.
next(): Returns the next element; throws NoSuchElementException when there are no elements.
remove(): Delete the most recent element returned by next(). Whether it supports it 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();
    }
}

Calling the structural modification method of the collection directly during traversal usually triggers a fast failure check and throws ConcurrentModificationException. You should use the iterator’s own remove(), or modify it uniformly after the traversal.

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 itself does not implement Iterable. Iterative views are usually obtained through entrySet(), keySet(), or values().

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

keySet() can be traversed when only keys are needed, and values() can be traversed when only values are needed.

Enhance the for loop

The enhanced for loop can traverse arrays and objects that implement Iterable.

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

When traversing collections, the enhanced for loop uses iterators at the bottom, so unsupported structural modifications to the collection cannot be made directly in the loop.

When traversing an array, the compiler generates loop logic based on the array index, not using Iterator.

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

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

When you need to modify List elements based on the index, you can use ordinary for cycles or ListIterator.