集合概述

曾经如果想要保存一组数据，我们通常使用数组来实现，但是数组有一个致命缺点：就是定长，数组一旦被创建，长度就是固定的，无法改变，如果想要添加或删除一个数据，是无法在原数组操作的，只能创建一个新数组。所以，一个长度可变的容器就应运而生了，也就是我们要介绍的——集合。

什么是集合

集合（Collections）是 Java 标准库的一部分，是用于存储、操作和管理对象的框架或工具包。它提供了一系列接口和类来存储和操作一组对象，简化了对一组对象的操作，如添加、删除、排序和检索数据等。Java 集合框架由接口、实现类和算法组成。

集合的设计目标是为常见的数据结构提供统一的 API，并且确保这些实现具有高效性和灵活性。通过使用集合，开发者可以更容易地管理和处理复杂的数据关系。

集合的特点

1. 只能存储引用数据类型（如果数据为 int 类型，会自动封装成 Integer 类型）。

2. 动态性：集合的大小是动态调整的，与数组不同，不需要在定义时指定容量。可以根据需要自动增加或减少容量。

3. 丰富的操作方法：集合框架提供了一系列方法来操作集合，如添加、删除、遍历、排序、搜索等。Java 的 Collections 工具类还提供了大量操作集合的算法（如排序、随机化、二分查找等）。

4. 泛型支持：Java集合支持泛型（Generics），使得在编译时就可以指定集合中元素的类型。提高了代码的类型安全性，减少了类型转换的麻烦和运行时错误。

5. 支持迭代器（Iterator）和增强for循环：所有集合都支持 Iterator 接口，便于遍历元素。还可以使用增强的 for 循环对集合中的元素进行遍历。

集合的分类

集合主要分为两类：单列集合和双列集合。它们的主要区别在于存储的元素结构：单列集合存储单一元素，而双列集合存储键值对

单列集合

单列集合用于存储单一类型的对象，存储的元素通常是相同类型的数据，每个元素都是独立的，并且不与其他元素直接关联。主要包含两类：List 和 Set。

List

List 接口包含多个子类，常见的有 ArrayList、LinkedList、Vector、CopyOnWriteArrayList、Stack等

ArrayList

特点

1. 元素有序
2. 元素可重复
3. 有索引
4. 线程不安全
5. 底层数据结构：动态数组

优缺点

优点：

• 随机访问快：由于元素是连续存储的，因此可以通过索引进行快速的随机访问（O(1) 时间复杂度）。
• 缓存友好：连续存储的数据对 CPU 缓存更友好，提高了性能。
• 自动扩展：当容量不足时，会自动增长。

缺点：

• 插入和删除慢：在中间位置插入或删除元素需要移动大量元素，时间复杂度为 O(n)。
• 线程不安全：默认情况下不是线程安全的，在多线程环境中需要额外的同步控制。

使用场景

• 频繁查询数据的场景。
• 数据增删操作较少，尤其是尾部操作。

LinkedList

特点

1. 元素有序
2. 元素可重复
3. 有索引（本质上无索引，但是 Java 为其提供了一系列操作索引的方法）
4. 线程不安全
5. 底层数据结构：双向链表

优缺点

优点：

• 插入和删除快：在链表头部或尾部进行插入和删除操作非常高效，时间复杂度为 O(1)。
• 动态大小：不需要预先分配固定大小的空间，可以根据需要动态增加节点。
• 支持双端队列操作：可以方便地用作栈或队列，提供了如 addFirst, removeLast 等方法。

缺点：

• 随机访问慢：查找某个特定位置的元素需要遍历链表，时间复杂度为 O(n)。
• 内存占用大：每个元素都需要额外的指针来指向前后节点，增加了内存消耗。

Vector

特点

1. 元素有序
2. 元素可重复
3. 有索引
4. 线程安全
5. 底层数据结构：动态数组

优缺点

优点：

• 线程安全：所有方法都是同步的，适合多线程环境。
• 自动扩展：与 ArrayList 类似，容量不足时会自动增长。

缺点：

• 性能较低：由于所有的操作都经过同步处理，性能通常比 ArrayList 差。
• 过时推荐：虽然仍然可用，但在现代编程中更多推荐使用 ArrayList 结合外部同步机制或者使用 CopyOnWriteArrayList。

CopyOnWriteArrayList

同 ArrayList ，基于不可变数组实现，每次修改都会创建一个新的副本

优缺点

优点：

• 无需锁定，读操作性能高。
• 不会出现 ConcurrentModificationException。
• 线程安全，适合并发环境。

缺点：

• 写操作开销大（需要复制整个数组）。
• 占用内存较多（写操作频繁时尤为明显）。
• 不适合实时性要求高的场景（可能存在短暂的延迟一致性）。

Stack（继承 Vector）

基于 Vector 实现，提供后进先出（LIFO）的行为。

优缺点

优点

• 线程安全：继承了 Vector 的同步特性，保证了多线程环境下的安全性。
• 专用方法：提供了诸如 push, pop, peek 等专门用于栈操作的方法。

缺点

• 性能问题：同 Vector 一样，存在性能上的劣势。
• 过时推荐：现在更推荐使用 Deque 接口及其实现类（如 ArrayDeque）来代替 Stack。

Set

Set 包含多个子类，主要包括 HashSet、LinkedHashSet、TreeSet等

HashSet

• 快速查找、插入和删除：由于使用了哈希函数来确定元素的位置，因此这三种操作的时间复杂度平均为 O(1)。
• 无序性：元素没有固定的顺序，它们是根据哈希码分布的。
• 允许一个 null 元素：可以包含一个 null 值。
• 底层数据结构：哈希表。

LinkedHashSet

• 有序性：按照插入顺序迭代元素，即最先插入的元素会最先被访问到。
• 高效操作：像 HashSet 一样提供快速的查找、插入和删除操作，时间复杂度为 O(1)。
• 不允许重复元素：确保所有元素都是唯一的。
• 底层数据结构：哈希表 + 双向链表。

TreeSet

• 自然排序或定制排序：默认情况下，元素按照自然顺序排列；也可以通过构造函数传入自定义比较器来指定排序规则。
• 平衡树结构：保证了高效的插入、删除和查找操作，时间复杂度为 O(log n)。
• 不允许 null 元素：除非指定了自定义比较器并且该比较器能够处理 null 值。
• 底层数据结构：红黑树。

Collection 接口使用

概述

单列集合的顶级接口

使用

语法：

Collection<E> 对象名 = new 实现类<E>()

其中<E>代表泛型，决定了集合中存储什么类型的数据，统一元素类型

只能使用引用数据类型（Int不行，Integer行），如果不指定，默认为 Object 类型，什么类型的数据都可以存储

常用方法

boolean add(E e)：将给定的元素添加到当前集合中（我们调用该方法时，不用接受返回值，因为add一定会成功）
boolean addAll(Collection<? extends E> c)：将另一个集合元素添加到当前集合中（集合合并）
void clear()：清除集合中的所有元素
boolean contains(Object o)：判断当前集合中是否包含指定的元素
boolean isEmpty()：判断当前集合是否为空
boolean remove(Object o)：将指定的元素从集合中删除
int size()：返回集合中的元素个数
Object[] toArray()：将集合转化为数组

示例代码

import java.util.ArrayList;
import java.util.Collection;

public class Demo01 {

    public static void main(String[] args) {
        Collection<Integer> list1 = new ArrayList();
        // boolean add(E e)：将给定的元素添加到当前集合中（我们调用该方法时，不用接受返回值，因为add一定会成功）
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        list1.add(5);
        System.out.println(list1);
        // boolean addAll(Collection<? extends E> c)：将另一个集合元素添加到当前集合中（集合合并）
        Collection<Integer> list2 = new ArrayList();
        list2.add(6);
        list2.add(7);
        list2.add(8);
        list2.add(9);
        list2.add(10);
        list2.addAll(list1);
        System.out.println(list2);
        // void clear()：清除集合中的所有元素
        list2.clear();
        System.out.println(list2);
        // boolean contains(Object o)：判断当前集合中是否包含指定的元素
        System.out.println(list1.contains(1));
        System.out.println(list2.contains(6));
        // boolean isEmpty()：判断当前集合是否为空
        System.out.println(list1.isEmpty());
        System.out.println(list2.isEmpty());
        // boolean remove(Object o)：将指定的元素从集合中删除
        System.out.println(list1.remove(1));
        System.out.println(list1);
        System.out.println(list1.remove(6));
        System.out.println(list1);
        // int size()：返回集合中的元素个数
        System.out.println(list1.size());
        // Object[] toArray()：将集合转化为数组
        Object[] array = list1.toArray();
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

}

ArrayList 集合使用

常用方法

boolean add(E e)：将元素添加到集合尾部中
void add(int index, E element)：在指定索引位置上添加元素
boolean remove(Object o)：删除指定的元素，成功为true
E remove(int index)：删除指定索引位置的元素并返回
E set(int index, E element)：修改指定索引位置的元素  
E get(int index)：获取指定索引位置的元素  
int size()：获取集合元素个数  

示例

import java.util.ArrayList;

public class Demo03 {
    public static void main(String[] args) {
        // boolean add(E e)：将元素添加到集合尾部中
        ArrayList<String> list = new ArrayList<>();
        list.add("张三");
        list.add("李四");
        list.add("王五");
        list.add("赵六");
        list.add("田七");
        System.out.println(list);
        // void add(int index, E element)：在指定索引位置上添加元素
        list.add(2, "王八");
        System.out.println(list);
        // boolean remove(Object o)：删除指定的元素，成功为true
        System.out.println(list.remove("王八"));
        // E remove(int index)：删除指定索引位置的元素并返回
        System.out.println(list.remove(2));
        System.out.println(list);
        // E set(int index, E element)：修改指定索引位置的元素
        System.out.println(list.set(1, "王八"));
        // E get(int index)：获取指定索引位置的元素
        System.out.println(list.get(1));
        // int size()：获取集合元素个数
        System.out.println(list.size());
    }
}

注意：如果集合元素为 Integer 类型，想要删除指定元素时，指定元素会被默认成索引位置（均为int 类型），如果想要删除指定元素，需要包装成 Integer 类型。

例如：集合想要删除“2”这个元素

ArrayList<Integer> list = new ArrayList<>();
list.add(2);
list.remove(2);

这时候默认删除索引为2的元素，会报错，如果想要删除“2”这个元素，需要：

list.remove(Integer.valueOf(2));

底层源码分析

1.ArrayList构造方法：默认情况构建一个初始容量为10为空列表，也可以指定初始容量
2.源码总结：
  a.不是一new底层就会创建初始容量为10的空列表，而是第一次add的时候才会创建初始容量为10的空列表
  b.ArrayList底层会自动扩容（Array.copyof()），每次扩容1.5倍

双列集合

双列集合主要用于存储键值对（Key-Value），其中每个键与一个值相关联。最典型的例子是 Map 接口及其各种实现。在这种类型的集合中，键是唯一的，但对应的值可以相同。

Java 中最常用的双列集合接口是 Map 接口，以及它的几个实现类如 HashMap, TreeMap, LinkedHashMap, 和 Hashtable。

Map

Map 是双列集合的顶级接口

HashMap

内部结构：基于哈希表实现，允许 null 键和 null 值。

特点：

• 非线程安全：适合单线程环境。
• 无序性：元素没有固定的顺序。
• 高效操作：提供常数时间复杂度 O(1) 的查找、插入和删除操作（平均情况下）。

TreeMap

内部结构：基于红黑树实现。

特点：

• 自然排序或定制排序：默认按键的自然顺序排序，也可以通过构造函数传入自定义比较器。
• 有序性：保持键的排序顺序。
• 不允许 null 键：除非指定了能够处理 null 的比较器。
• 平衡树结构：保证高效的插入、删除和查找操作，时间复杂度为 O(log n)。

LinkedHashMap

内部结构：结合哈希表和双向链表，以维护插入顺序。

特点：

• 有序性：按照插入顺序迭代元素。
• 高效操作：像 HashMap 一样提供快速的查找、插入和删除操作，时间复杂度为 O(1)。
• 可选访问顺序：可以选择按照最近最少使用（LRU）顺序进行排序。

HashTable

内部结构：类似于 HashMap，但它是遗留类，现已很少使用。

特点：

• 线程安全：所有方法都是同步的，适用于多线程环境。
• 不允许 null 键和 null 值。
• 性能较低：由于同步机制，性能通常不如 HashMap 或 ConcurrentHashMap。

ConcurrentHashMap

内部结构：分段锁机制实现了并发访问控制。

特点：

• 线程安全：允许多个线程同时读写不同部分的数据。
• 高效并发操作：提供了较好的并发性能，适用于高并发环境。
• 不允许 null 键和 null 值。

HashMap 集合使用

常用方法

V put(K key, V value)：将指定的键值对插入到映射中。如果该键已经存在，则替换旧值并返回旧值。
V get(Object key)：根据指定的键返回相应的值；如果键不存在，则返回 null。
boolean containsKey(Object key)：判断映射是否包含指定的键。
boolean containsValue(Object value)：判断映射是否包含指定的值。
V remove(Object key)：移除指定键所映射的值；如果映射不包含该键，则返回 null。
void clear()：从映射中移除所有键值对。
Set<K> keySet()：返回映射中所有键的集合视图。
Collection<V> values()：返回映射中所有值的集合视图。
Set<Map.Entry<K,V>> entrySet()：返回映射中所有键值对的集合视图。

代码示例

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

public class Demo04 {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        // V put(K key, V value)：将指定的键值对插入到映射中。如果该键已经存在，则替换旧值并返回旧值。
        map.put(1, "张三");
        map.put(2, "李四");
        System.out.println(map);
        // V get(Object key)：根据指定的键返回相应的值；如果键不存在，则返回 null。
        System.out.println(map.get(1));
        // boolean containsKey(Object key)：判断映射是否包含指定的键。
        System.out.println(map.containsKey(1));
        System.out.println(map.containsKey(3));
        // boolean containsValue(Object value)：判断映射是否包含指定的值。
        System.out.println(map.containsValue("张三"));
        // V remove(Object key)：移除指定键所映射的值；如果映射不包含该键，则返回 null。
        System.out.println(map.remove(1));
        // void clear()：从映射中移除所有键值对。
        map.clear();
        System.out.println(map);
        // Set<K> keySet()：返回映射中所有键的集合视图。
        map.put(1, "张三");
        map.put(2, "李四");
        System.out.println(map.keySet());
        // Collection<V> values()：返回映射中所有值的集合视图。
        System.out.println(map.values());
        // Set<Map.Entry<K,V>> entrySet()：返回映射中所有键值对的集合视图。
        System.out.println(map.entrySet());
    }
}

结果：

{1=张三, 2=李四}
张三
true
false
true
张三
{}
[1, 2]
[张三, 李四]
[1=张三, 2=李四]

HashMap的几种遍历方式

1. 使用 entrySet() 方法

这是最常用的方法之一，它返回一个包含所有键值对的 Set<Map.Entry<K,V>>，然后你可以通过这个集合来访问每个键值对。

Map<String, Integer> map = new HashMap<>();
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Orange", 3);

// 使用 entrySet() 和增强型 for 循环
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}

2. 使用 keySet() 方法

这种方法只遍历键，如果你想根据键来获取对应的值，可以使用 get() 方法。

// 使用 keySet() 和增强型 for 循环
for (String key : map.keySet()) {
    System.out.println("Key = " + key + ", Value = " + map.get(key));
}

3. 使用 values() 方法

如果你只关心值而不关心键，可以直接遍历 values() 集合。

// 使用 values() 和增强型 for 循环
for (Integer value : map.values()) {
    System.out.println("Value = " + value);
}

4. 使用迭代器（Iterator）

对于更复杂的逻辑，或者你需要在遍历过程中移除元素，可以使用迭代器。

// 使用 entrySet() 和 Iterator
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
    
    // 如果需要在遍历过程中移除元素
    // iterator.remove(); // 注意：只能移除当前元素
}

5. 使用 Lambda 表达式（Java 8+）

从 Java 8 开始，你可以使用 lambda 表达式简化代码。

// 使用 forEach 和 lambda 表达式
map.forEach((key, value) -> System.out.println("Key = " + key + ", Value = " + value));

6. 使用 Stream API（Java 8+）

流（Stream）API 提供了更加功能强大的方法来处理集合数据，支持并行处理和其他高级操作。

// 使用 Stream API
map.entrySet().stream()
    .forEach(entry -> System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue()));

// 如果需要过滤或进行其他操作
map.entrySet().stream()
    .filter(entry -> entry.getValue() > 1)
    .forEach(entry -> System.out.println("Filtered Key = " + entry.getKey() + ", Value = " + entry.getValue()));

以上是几种遍历 HashMap 的常见方法。选择哪种方法取决于你的具体需求：

• 简单遍历：如果只是想遍历所有的键值对，entrySet() 结合增强型 for 循环是最简洁的方式。
• 只遍历键或值：分别使用 keySet() 或 values() 方法。
• 复杂逻辑或移除元素：使用迭代器。
• 现代编程风格：利用 Java 8 引入的 lambda 表达式和 Stream API 可以让代码更加简洁和易读，并且提供了更多功能。

无论你选择哪种方式，理解每种方法的工作原理和适用场景，可以帮助你在编写代码时做出最佳选择。

迭代器

什么是迭代器

在 Java 中，迭代器（Iterator） 是一个接口，它提供了一种遍历集合中元素的标准方式。通过使用迭代器，你可以在不暴露集合内部结构的情况下安全地访问和操作集合中的每一个元素。这不仅提高了代码的可读性和灵活性，还避免了直接操作集合时可能引发的问题，比如并发修改异常（ConcurrentModificationException）。

迭代器的特点

• 封装性：迭代器隐藏了集合的具体实现细节，允许以统一的方式遍历不同类型的集合。
• 安全性：在遍历过程中，如果你尝试直接修改集合（如添加或删除元素），可能会抛出 ConcurrentModificationException。而迭代器提供了安全的方法来移除当前元素而不影响遍历过程。
• 单向遍历：标准的 Iterator 接口只支持向前遍历集合，即从第一个元素到最后一个元素。对于双向遍历的需求，可以使用 ListIterator 接口。

迭代器使用

迭代器使用主要是 Collection 下的3个方法：

boolean hasNext()：检查是否还有下一个元素。如果有，则返回 true；否则返回 false。
E next()：返回集合中的下一个元素，并将游标移动到下一个位置。如果已经到达集合末尾，则抛出 NoSuchElementException。
void remove()：移除最近一次调用 next() 方法返回的元素。这个方法只能在 next() 被调用之后立即调用一次，否则会抛出 IllegalStateException。

示例

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

public class Demo02 {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("张三1");
        list.add("张三2");
        list.add("张三3");
        list.add("张三4");
        list.add("张三5");

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

结果：

张三1
张三2
张三3
张三4
张三5

注意：在使用迭代器遍历集合元素时不要随意修改集合长度，会报并发修改异常，如果想要修改，使用 ListIterator

总结

迭代器是 Java 中一种强大且灵活的工具，用于遍历集合中的元素。它不仅提供了安全的操作机制，还增强了代码的可读性和可维护性。理解如何正确使用迭代器及其相关接口（如 ListIterator），可以帮助你在处理集合时更加高效和可靠。