Java 中 List、Set、Map 核心实现类解析

Java中List、Set、Map核心实现类解析

在 Java 里，List、Set 和 Map 是集合框架里的关键接口，其中 ArrayList、LinkedList 属于 List 接口的常见实现类，HashMap 和 ConcurrentHashMap 则是 Map 接口的常用实现类。

1. ArrayList

简介

ArrayList 是基于动态数组实现的 List 类，它允许存储重复元素，并且可以通过索引快速访问元素。

特点

• 动态扩容：当数组容量不足时，会自动进行扩容。
• 随机访问快：可以通过索引在 $O(1)$ 的时间复杂度内访问元素。
• 插入和删除慢：在数组中间或开头插入、删除元素时，需要移动大量元素，时间复杂度为 $O(n)$。

示例代码

import java.util.ArrayList;
import java.util.List;

public class ArrayListExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("apple");
        list.add("banana");
        list.add("cherry");

        // 通过索引访问元素
        System.out.println(list.get(1)); // 输出: banana

        // 删除元素
        list.remove(0);
        System.out.println(list); // 输出: [banana, cherry]
    }
}

2. LinkedList

简介

LinkedList 是基于双向链表实现的 List 类，同样允许存储重复元素。

特点

• 插入和删除快：在链表头部、尾部或中间插入、删除元素时，只需修改指针，时间复杂度为 $O(1)$。
• 随机访问慢：需要从头或尾开始遍历链表，时间复杂度为 $O(n)$。
• 可作为栈、队列使用：提供了 push()、pop()、offer()、poll() 等方法。

示例代码

import java.util.LinkedList;
import java.util.List;

public class LinkedListExample {
    public static void main(String[] args) {
        List<String> list = new LinkedList<>();
        list.add("apple");
        list.add("banana");
        list.add("cherry");

        // 在头部插入元素
        ((LinkedList<String>) list).addFirst("date");
        System.out.println(list); // 输出: [date, apple, banana, cherry]

        // 删除尾部元素
        ((LinkedList<String>) list).removeLast();
        System.out.println(list); // 输出: [date, apple, banana]
    }
}

3. HashMap

简介

HashMap 是基于哈希表实现的 Map 类，用于存储键值对，键不能重复。

特点

• 快速查找：通过哈希函数计算键的哈希值，平均时间复杂度为 $O(1)$ 来查找、插入和删除元素。
• 无序：不保证元素的插入顺序。
• 非线程安全：在多线程环境下可能会出现数据不一致的问题。

示例代码

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("cherry", 3);

        // 获取元素
        System.out.println(map.get("banana")); // 输出: 2

        // 删除元素
        map.remove("apple");
        System.out.println(map); // 输出: {banana=2, cherry=3}
    }
}

4. ConcurrentHashMap

简介

ConcurrentHashMap 也是基于哈希表实现的 Map 类，是线程安全的，适合在多线程环境下使用。

特点

• 线程安全：采用分段锁或 CAS（Compare-And-Swap）机制保证线程安全，并发性能高。
• 高效并发操作：不同的段可以同时进行读写操作，提高了并发处理能力。
• 无序：不保证元素的插入顺序。

示例代码

import java.util.concurrent.ConcurrentHashMap;
import java.util.Map;

public class ConcurrentHashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new ConcurrentHashMap<>();
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("cherry", 3);

        // 获取元素
        System.out.println(map.get("banana")); // 输出: 2

        // 删除元素
        map.remove("apple");
        System.out.println(map); // 输出: {banana=2, cherry=3}
    }
}

总结

• 若需要快速随机访问元素，可选择 ArrayList。
• 若频繁进行插入和删除操作，LinkedList 是更好的选择。
• 单线程环境下，使用 HashMap 存储键值对。
• 多线程环境下，使用 ConcurrentHashMap 确保线程安全。