MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

Java集合框架源码解析

2022-07-085.4k 阅读

Java 集合框架概述

Java 集合框架（Java Collections Framework）是一个包含了多种数据结构和算法的框架，它提供了一系列的接口和类，用于存储、操作和管理数据集合。这个框架的设计目的是为了提高代码的复用性、可维护性以及性能。它包含了三个主要部分：接口（Interfaces）、实现类（Implementing Classes）和算法（Algorithms）。

接口定义了集合的行为规范，例如 Collection、List、Set 和 Map 等。实现类则具体实现了这些接口，像 ArrayList、LinkedList、HashSet、HashMap 等。而算法则是对集合进行操作的方法，如排序、查找等，这些算法在 Collections 工具类中提供。

集合框架的接口

  1. Collection 接口 Collection 接口是 Java 集合框架中最基本的接口，它定义了一组操作集合元素的方法。所有其他的集合接口都继承自这个接口。

    import java.util.ArrayList;
import java.util.Collection;
public class CollectionExample {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("apple");
        collection.add("banana");
        System.out.println(collection.size());
        System.out.println(collection.contains("apple"));
        collection.remove("banana");
        System.out.println(collection.size());
    }
}

    在这个例子中，我们创建了一个 ArrayList 实例，它实现了 Collection 接口。我们使用 add 方法添加元素，size 方法获取集合大小，contains 方法检查元素是否存在，remove 方法移除元素。

  2. List 接口 List 接口继承自 Collection 接口，它表示一个有序的集合，允许有重复元素。List 接口提供了基于索引访问元素的方法。

    import java.util.ArrayList;
import java.util.List;
public class ListExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("one");
        list.add("two");
        list.add(1, "three");
        System.out.println(list.get(1));
        list.set(2, "four");
        System.out.println(list);
    }
}

    这里我们展示了 List 接口特有的方法，如 add(int index, E element) 可以在指定索引位置添加元素，get(int index) 获取指定索引位置的元素，set(int index, E element) 修改指定索引位置的元素。

  3. Set 接口 Set 接口同样继承自 Collection 接口，但它表示一个不包含重复元素的集合。

    import java.util.HashSet;
import java.util.Set;
public class SetExample {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("apple");
        set.add("banana");
        set.add("apple");
        System.out.println(set.size());
    }
}

    在这个 HashSet 的例子中，我们可以看到，当尝试添加重复元素 “apple” 时，集合的大小并不会增加，因为 Set 不允许重复元素。

  4. Map 接口 Map 接口不是继承自 Collection 接口，它存储键值对（key - value pairs），一个键最多映射到一个值。

    import java.util.HashMap;
import java.util.Map;
public class MapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 1);
        map.put("banana", 2);
        System.out.println(map.get("apple"));
        System.out.println(map.containsKey("banana"));
        map.remove("banana");
        System.out.println(map.size());
    }
}

    这里我们使用 put 方法添加键值对，get 方法通过键获取值，containsKey 方法检查是否包含指定键，remove 方法移除键值对。

集合框架的实现类

  1. ArrayList ArrayList 是 List 接口的动态数组实现。它内部使用数组来存储元素，并且可以根据需要自动扩容。

    import java.util.ArrayList;
import java.util.List;
public class ArrayListAnalysis {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        int size = list.size();
        int capacity = ((ArrayList<Integer>) list).capacity();
        System.out.println("Size: " + size);
        System.out.println("Capacity: " + capacity);
    }
}

    在 ArrayList 的源码中，核心的属性有 elementData 数组用于存储元素，size 表示当前集合中元素的个数。当添加元素导致 size 超过 elementData 的容量时，会触发扩容机制。扩容时，新的容量通常是原来容量的 1.5 倍。

    private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

  2. LinkedList LinkedList 也是 List 接口的实现类，它基于双向链表数据结构。与 ArrayList 不同，LinkedList 在插入和删除操作上更高效，尤其是在链表中间进行操作时。

    import java.util.LinkedList;
import java.util.List;
public class LinkedListAnalysis {
    public static void main(String[] args) {
        List<String> list = new LinkedList<>();
        list.add("a");
        list.add("b");
        list.add(1, "c");
        System.out.println(list);
    }
}

    在 LinkedList 的源码中，每个节点（Node）包含前驱节点（prev）、后继节点（next）和存储的元素（item）。插入和删除操作主要涉及节点的指针调整。例如，在链表中间插入一个元素：

    void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

  3. HashSet HashSet 是 Set 接口的实现类，它基于 HashMap 实现。HashSet 中的元素是无序的，并且不允许重复。

    import java.util.HashSet;
import java.util.Set;
public class HashSetAnalysis {
    public static void main(String[] args) {
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(1);
        System.out.println(set.size());
    }
}

    HashSet 的源码中，它内部有一个 HashMap 实例。当向 HashSet 添加元素时，实际上是将元素作为 HashMap 的键来存储，值则是一个固定的对象 PRESENT。

    private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

  4. HashMap HashMap 是 Map 接口的常用实现类，它基于哈希表数据结构。HashMap 允许 null 键和 null 值，但在多线程环境下是非线程安全的。

    import java.util.HashMap;
import java.util.Map;
public class HashMapAnalysis {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 1);
        map.put("banana", 2);
        System.out.println(map.get("apple"));
    }
}

    在 HashMap 的源码中，核心的数据结构是一个数组 table，数组的每个元素是一个链表（在 JDK 1.8 及之后，当链表长度达到一定阈值时会转换为红黑树）。当向 HashMap 中插入键值对时，首先通过键的 hashCode 计算出哈希值，再通过哈希值确定在数组中的位置。

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 处理哈希冲突
        //...
    }
    //...
    return null;
}

    当发生哈希冲突（不同的键计算出相同的哈希值）时，在 JDK 1.8 之前，会将新的键值对插入到链表头部；在 JDK 1.8 及之后，当链表长度小于 8 时，插入到链表尾部，当链表长度大于等于 8 且数组长度大于等于 64 时，链表会转换为红黑树以提高查找效率。

  5. TreeMap TreeMap 也是 Map 接口的实现类，它基于红黑树数据结构。TreeMap 中的键是有序的，可以按照自然顺序或者自定义顺序进行排序。

    import java.util.Map;
import java.util.TreeMap;
public class TreeMapAnalysis {
    public static void main(String[] args) {
        Map<Integer, String> map = new TreeMap<>();
        map.put(3, "c");
        map.put(1, "a");
        map.put(2, "b");
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

    在 TreeMap 的源码中，核心的属性是一个红黑树的根节点 root。当插入键值对时，会按照红黑树的规则进行插入和调整，以保持树的平衡。插入操作的关键代码如下：

    private void insertEntry(Entry<K,V> entry) {
    int cmp;
    Entry<K,V> parent;
    boolean color = true;
    if (root == null) {
        root = entry;
        size = 1;
        modCount++;
        return;
    }
    TreeMap.Entry<K,V> t = root;
    do {
        parent = t;
        cmp = keyComparator == null?
            ((Comparable<? super K>)entry.key).compareTo(t.key) :
            keyComparator.compare(entry.key, t.key);
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else
            return;
    } while (t != null);
    entry.parent = parent;
    if (cmp < 0)
        parent.left = entry;
    else
        parent.right = entry;
    fixAfterInsertion(entry);
    size++;
    modCount++;
}

集合框架的算法

  1. 排序算法 在 Collections 工具类中，提供了对 List 进行排序的方法。对于实现了 Comparable 接口的元素类型，可以直接使用 Collections.sort(List<T> list) 方法进行排序。 
    import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SortingExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(1);
        list.add(2);
        Collections.sort(list);
        System.out.println(list);
    }
}
    如果元素类型没有实现 Comparable 接口，可以使用 Collections.sort(List<T> list, Comparator<? super T> c) 方法，通过传入一个 Comparator 来定义排序规则。 
    import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
class Person {
    String name;
    int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}
public class CustomSortingExample {
    public static void main(String[] args) {
        List<Person> list = new ArrayList<>();
        list.add(new Person("Alice", 25));
        list.add(new Person("Bob", 20));
        list.add(new Person("Charlie", 30));
        Collections.sort(list, new Comparator<Person>() {
            @Override
            public int compare(Person p1, Person p2) {
                return p1.age - p2.age;
            }
        });
        for (Person person : list) {
            System.out.println(person.name + ": " + person.age);
        }
    }
}
  2. 查找算法 Collections 工具类还提供了查找算法，如 binarySearch 方法用于在有序 List 中进行二分查找。 
    import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BinarySearchExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        int index = Collections.binarySearch(list, 2);
        System.out.println("Index of 2: " + index);
    }
}
    这里需要注意的是，binarySearch 方法要求列表必须是有序的，否则结果是未定义的。

集合框架的性能分析

  1. ArrayList 和 LinkedList 的性能对比
    • 随机访问性能：ArrayList 基于数组实现，随机访问元素的时间复杂度为 O(1)，因为可以直接通过索引访问数组元素。而 LinkedList 基于链表实现，随机访问元素需要从链表头或链表尾开始遍历，时间复杂度为 O(n)。
    • 插入和删除性能：在列表中间插入和删除元素时，LinkedList 的时间复杂度为 O(1)，因为只需要调整指针。而 ArrayList 需要移动插入或删除位置之后的所有元素，时间复杂度为 O(n)。在列表末尾插入元素时，ArrayList 的平均时间复杂度为 O(1)（考虑扩容情况，均摊时间复杂度），LinkedList 为 O(1)。
  2. HashMap 和 TreeMap 的性能对比
    • 查找性能：HashMap 基于哈希表，查找元素的平均时间复杂度为 O(1)，在理想情况下，通过哈希值可以直接定位到元素所在的位置。但是在哈希冲突严重时，时间复杂度会退化为 O(n)。TreeMap 基于红黑树，查找元素的时间复杂度为 O(log n)，因为红黑树的高度是对数级别的。
    • 插入和删除性能：HashMap 的插入和删除操作平均时间复杂度也是 O(1)，但同样在哈希冲突严重时性能会下降。TreeMap 的插入和删除操作时间复杂度为 O(log n)，因为需要维护红黑树的平衡。

集合框架的线程安全性

  1. 非线程安全的集合类 前面介绍的 ArrayList、LinkedList、HashSet、HashMap 等都是非线程安全的。在多线程环境下，如果多个线程同时对这些集合进行操作，可能会导致数据不一致或其他并发问题。例如，两个线程同时向 ArrayList 中添加元素，可能会导致元素丢失或数组越界等问题。
  2. 线程安全的集合类
    • Vector 和 Hashtable：Vector 是 ArrayList 的线程安全版本，它的方法大多使用 synchronized 关键字进行同步，以确保线程安全。Hashtable 是 HashMap 的线程安全版本，同样使用 synchronized 同步方法。然而，由于这种同步方式粒度较大，在高并发环境下性能较差。
    import java.util.Vector;
public class VectorExample {
    public static void main(String[] args) {
        Vector<Integer> vector = new Vector<>();
        vector.add(1);
        vector.add(2);
        synchronized (vector) {
            for (int i : vector) {
                System.out.println(i);
            }
        }
    }
}
    • Collections.synchronizedXxx 方法：Collections 工具类提供了一些方法来创建线程安全的集合，如 Collections.synchronizedList、Collections.synchronizedSet、Collections.synchronizedMap 等。这些方法返回的集合在内部使用 synchronized 块来同步对集合的操作。
    import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SynchronizedListExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        List<Integer> synchronizedList = Collections.synchronizedList(list);
        synchronizedList.add(1);
        synchronized (synchronizedList) {
            for (int i : synchronizedList) {
                System.out.println(i);
            }
        }
    }
}
    • ConcurrentHashMap：ConcurrentHashMap 是 HashMap 的线程安全版本，它采用了分段锁（在 JDK 1.8 之前）或 CAS 操作（在 JDK 1.8 及之后）来实现线程安全。相比 Hashtable，ConcurrentHashMap 在高并发环境下具有更好的性能，因为它允许多个线程同时访问不同的段（在 JDK 1.8 之前）或通过 CAS 操作实现无锁化的部分操作（在 JDK 1.8 及之后）。
    import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
public class ConcurrentHashMapExample {
    public static void main(String[] args) {
        ConcurrentMap<String, Integer> map = new ConcurrentHashMap<>();
        map.put("apple", 1);
        map.put("banana", 2);
        System.out.println(map.get("apple"));
    }
}

通过对 Java 集合框架的源码解析，我们深入了解了集合框架的接口、实现类、算法以及性能和线程安全性等方面的知识。这有助于我们在实际编程中根据不同的需求选择合适的集合类型，以提高程序的效率和稳定性。