Java基础终章篇（10）容器类与集合操作
目录
1.前言
哈喽大家好吖，安排到这里该讲述Java中非常重要的容器类和集合操作嘞，Java基础的学习很快接近了尾声，往后博主将继续学习JavaEE，MySQL以及spring的相关内容，本文将以凝练的语言与方式将容器类和集合操作总结在一起，奉上正文~
2.容器类与集合操作
Java容器类主要是指java.util包中的类，它们用于存储数据集合。这些容器类可以分为两大类：容器类（Collections）和工具类（Tools）。容器类主要包括List、Set、Map三种接口及其实现类，而工具类则包括Collections和Arrays等。
2.2.1层次结构
1. 顶层接口
Iterable：这是集合框架的顶层接口，Collection接口继承了Iterable。实现了Iterable接口的类可以使用增强型for循环（for-each）。2. Collection接口层
Collection：是所有集合类的根接口，定义了集合的基本操作方法，比如add()、remove()、size()等。
- 主要子接口包括：
List、Set和Queue。3. Collection接口的子接口
List：有序的集合，允许重复元素。List接口定义了根据索引操作元素的方法。
- 主要实现类：
ArrayList、LinkedList、Vector。Set：不允许重复元素的集合，主要用于存储唯一值。Set接口不保证元素的顺序。
- 主要实现类：
HashSet、LinkedHashSet、TreeSet。Queue：先进先出的集合接口，常用于处理队列和任务。
- 主要实现类：
LinkedList（也实现了List接口）、PriorityQueue。Deque：双端队列接口，支持从两端插入和移除元素。
- 主要实现类：
ArrayDeque、LinkedList。4. Map接口层
Map：键值对集合接口，存储键值映射关系，键不能重复。
- 主要实现类：
HashMap、TreeMap、LinkedHashMap、Hashtable。下面用一张图来更加形象的展现出它们之间的层级关系：
┌─────────────────────┐ │ Iterable │ └─────────────────────┘ │ │ │ ┌─────────────────────┐ │ Collection │ └─────────────────────┘ / | \ / | \ / | \ ┌─────────────┐ ┌─────────────┐ ┌──────────────┐ │ List │ │ Set │ │ Queue │ └─────────────┘ └─────────────┘ └──────────────┘ │ │ │ ┌───────────────┐ ┌─────────────┐ ┌──────────────┐ │ ArrayList │ │ HashSet │ │ LinkedList │ │ LinkedList │ │LinkedHashSet│ │ PriorityQueue│ │ Vector │ │ TreeSet │ └──────────────┘ └───────────────┘ └─────────────┘ ┌─────────────────────┐ │ Map │ └─────────────────────┘ / \ / \ ┌────────────────┐ ┌─────────────┐ │ HashMap │ │ TreeMap │ │ LinkedHashMap │ └─────────────┘ │ Hashtable │ └────────────────┘
2.2collection框架
Collection接口：所有集合类的根接口，定义了一些基本操作方法，如add()、remove()、size()等。Collection接口有三个子接口：List、Set和Queue。
我们接下来主要讲解的是List、Set和Queue子接口以及实现的类：
2.2.1List接口及其实现类
ArrayList：
基本原理：
- 数组存储：
ArrayList使用一个数组来存储数据，初始容量默认为 10。数组容量不足时，它会创建一个新的数组（通常是当前数组容量的 1.5 倍），并将现有元素复制到新数组中。- 扩容机制：当
ArrayList的容量不足以容纳新元素时，会进行扩容操作。扩容过程通过创建一个更大的数组（一般是原来容量的 1.5 倍）并复制旧数据来完成。常用的方法：
boolean add(E e)：将元素添加到列表末尾。void add(int index, E element)：在指定位置插入元素。E get(int index)：返回指定位置的元素。E set(int index, E element)：替换指定位置的元素。E remove(int index)：删除指定位置的元素。boolean remove(Object o)：删除列表中首次出现的指定元素。int size()：返回列表中元素的个数。boolean isEmpty()：检查列表是否为空。boolean contains(Object o)：检查列表是否包含指定元素。int indexOf(Object o)：返回列表中第一次出现的指定元素的索引。int lastIndexOf(Object o)：返回列表中最后一次出现的指定元素的索引。void clear()：清空列表中的所有元素。代码示例：
public static void main(String[] args) { ArrayList <String> student = new ArrayList<>(); System.out.println(student.add("张三"));//返回值为布尔类型 student.add(0,"李四"); System.out.println("列表中元素量:" + student.size());//2 System.out.println(student.indexOf("李四"));//0 System.out.println(student.lastIndexOf("张三"));//1 System.out.println(student.get(0));//李四 System.out.println(student.get(1));//张三 student.remove(0); System.out.println(student.get(0));//张三 System.out.println(student.isEmpty());//false student.clear(); System.out.println("列表中元素量:" + student.size());//0 System.out.println(student.isEmpty());//true }优点
- 随机访问快：
ArrayList支持通过索引快速访问元素，时间复杂度为 O(1)。- 动态扩展：
ArrayList可以根据需要动态扩展，增加了其灵活性。缺点
- 插入和删除效率低：在中间位置插入或删除元素时，需要移动后面的元素，时间复杂度为 O(n)。
- 占用额外内存：为了实现动态扩展，
ArrayList会预留一些空间，这些空闲空间在不使用时会占用内存。
LinkedList：
基本原理：
- 节点存储结构：
LinkedList的每个元素都存储在一个称为节点（Node）的对象中。每个节点包含当前元素、前驱节点和后继节点的引用。结构如下：- 头尾节点引用：
LinkedList使用first和last引用分别指向链表的头节点和尾节点。常用方法：
由于其既继承了List接口，又继承了Deque的接口，作为一个双向链表拥有更多的方法
List接口中的方法
- add(E e)：将元素添加到链表的末尾。
- add(int index, E element)：在指定位置插入元素。
- get(int index)：获取指定位置的元素。
- set(int index, E element)：修改指定位置的元素。
- remove(int index)：删除指定位置的元素。
- size()：返回链表中元素的数量。
Deque接口中的方法
- addFirst(E e)：在链表的头部添加元素。
- addLast(E e)：在链表的尾部添加元素。
- getFirst()：返回链表的第一个元素。
- getLast()：返回链表的最后一个元素。
- removeFirst()：删除并返回链表的第一个元素。
- removeLast()：删除并返回链表的最后一个元素。
- offer(E e)：将元素添加到队列尾部（等效于
addLast）。- offerFirst(E e)：将元素添加到队列头部。
- offerLast(E e)：将元素添加到队列尾部。
- poll()：删除并返回链表的第一个元素（等效于
removeFirst）。- pollFirst()：删除并返回链表的第一个元素。
- pollLast()：删除并返回链表的最后一个元素。
Queue接口中的方法
- peek()：返回第一个元素，但不删除。如果链表为空，返回
null。- poll()：删除并返回第一个元素。如果链表为空，返回
null。代码示例：
public static void main(String[] args) { LinkedList <String> list = new LinkedList<>(); //List接口中的个方法 list.add("张三");//在尾部添加 list.add(1,"李四"); System.out.println(list.get(0));//张三 list.set(0,"王五"); System.out.println(list.get(0));//王五 System.out.println(list.size());//2 //Deque接口中的方法 list.addFirst("孙六"); list.offerLast("孔七"); System.out.println(list.getFirst());//孙六 System.out.println(list.getLast());//孔七 //Queue接口中的个方法 System.out.println(list.peek());//孙六 System.out.println(list.poll());//孙六 System.out.println(list.poll());//王五 }优点
- 插入和删除效率高：在链表的头部、尾部或中间位置插入和删除元素的效率较高，适合频繁插入和删除操作的场景。
- 实现双端队列：
LinkedList同时实现了Deque接口，支持从两端插入和删除元素。缺点
- 随机访问效率低：访问链表中的某个元素需要遍历整个链表，因此随机访问效率较低。
- 内存消耗大：链表的每个节点都需要存储前后引用，增加了内存开销。
这里对比一下ArrayList和LinkedList的特点，以便有更深的理解：
| 特性 | LinkedList | ArrayList |
|---|---|---|
| 实现结构 | 双向链表 | 动态数组 |
| 随机访问 | 慢 (O(n)) | 快 (O(1)) |
| 插入/删除 | 头尾插入删除快 (O(1))，中间插入删除慢 | 中间插入删除慢（O(n)），尾部快 (O(1)) |
| 内存开销 | 大，每个节点需额外存储两个引用 | 较小，主要存储元素本身 |
| 适合的使用场景 | 频繁插入/删除操作 | 频繁访问操作，较少插入/删除 |
2.2.2Set接口及其实现类
Set 接口是 Java 集合框架中的一个接口，表示一个不允许包含重复元素的集合。它继承了 Collection 接口，主要用于存储唯一的元素。Set 的实现类主要包括 HashSet、LinkedHashSet 和 TreeSet，每种实现类的特性和应用场景各不相同。
HashSet：
基本原理：
HashSet底层依赖HashMap实现，所有元素都作为HashMap的键值对中的键存储，值统一使用一个固定的占位对象（private static final Object PRESENT = new Object();）。- 由于
HashMap的键是唯一的，因此HashSet也只能存储唯一元素。常用方法：
boolean add(E e)：添加元素e到集合中，若已存在返回false。boolean remove(Object o)：移除指定元素o，成功移除返回true。boolean contains(Object o)：检查集合是否包含指定元素o，存在返回true。int size()：返回集合中的元素数量。boolean isEmpty()：检查集合是否为空，空则返回true。void clear()：清空集合中的所有元素。Iterator<E> iterator()：返回一个用于遍历集合的迭代器。Object[] toArray()：将集合中的所有元素以数组形式返回。<T> T[] toArray(T[] a)：将集合中的元素以指定类型的数组返回。boolean containsAll(Collection<?> c)：检查集合是否包含指定集合c中的所有元素。特点：
- 无序性：
HashSet中的元素没有特定顺序，因为其内部基于哈希表。- 唯一性：
HashSet中不允许有重复元素。如果试图添加重复元素，添加操作会失败。- 允许空值：
HashSet允许最多有一个null元素。代码示例：
public static void main(String[] args) { String str1 = new String("Hello"); String str2 = new String("Hello"); System.out.println(str1 == str2); System.out.println(str1.equals(str2)); HashSet<String> set = new HashSet<>(); set.add(str1); System.out.println(set.contains("Hello")); System.out.println(set.contains(str2)); set.add(str2); System.out.println(set.size()); set.remove(str1); set.clear(); System.out.println(set.isEmpty()); }
LinkedHashSet：
基本原理：
LinkedHashSet是 Java 集合框架中基于哈希表和双向链表实现的一个集合类，它是HashSet的子类，具有以下特点：
- 保证了 插入顺序（相较于
HashSet的无序性）。- 继承了
HashSet的所有功能，同时提供了更高的遍历顺序可控性。- 适用于需要高效去重且维持插入顺序的场景。
常用方法：
由于是HashSet子类，大部分常用的方法一致，这里不过多列举
特点：
- 顺序性：
LinkedHashSet内部维护了一个双向链表，用于记录元素的插入顺序，因此其迭代顺序与插入顺序一致。- 唯一性：与
HashSet类似，LinkedHashSet不允许存储重复元素。代码演示：
public static void main(String[] args) { LinkedHashSet<Integer> set = new LinkedHashSet<>(); set.add(2); set.add(3); set.add(1); System.out.println(set); for (Integer x:set){ System.out.print(x + " "); } System.out.println(); System.out.println(set.isEmpty()); System.out.println(set.size()); set.remove(2); System.out.println(set); }
treeset：
基本原理：
TreeSet底层基于 红黑树 实现，其主要特点是：
- 自平衡：红黑树是一种高度平衡的二叉搜索树，任何节点到叶子节点的最长路径不会超过最短路径的两倍。
- 动态排序：插入和删除时会动态调整树的结构，确保元素有序。
- 查询高效：每次操作的时间复杂度为 O(log n)。
特点：
- 有序性：集合中的元素会按照自然顺序（
Comparable）或指定的比较器（Comparator）进行排序。- 唯一性：不允许存储重复元素。
- 动态排序：每次插入都会动态调整元素顺序，插入、删除和查找的时间复杂度为 O(log n)。
常用方法：
boolean add(E e)：将元素e添加到集合中，若已存在返回false。boolean remove(Object o)：从集合中移除指定元素o，成功移除返回true。boolean contains(Object o)：检查集合是否包含指定元素o，存在返回true。int size()：返回集合中元素的数量。boolean isEmpty()：检查集合是否为空，空则返回true。void clear()：清空集合中的所有元素。Iterator<E> iterator()：返回一个按升序遍历集合的迭代器。E first()：返回集合中的第一个（最小）元素。E last()：返回集合中的最后一个（最大）元素。E lower(E e)：返回严格小于给定元素的最大元素，若不存在返回null。E floor(E e)：返回小于或等于给定元素的最大元素，若不存在返回null。E ceiling(E e)：返回大于或等于给定元素的最小元素，若不存在返回null。E higher(E e)：返回严格大于给定元素的最小元素，若不存在返回null。代码示例：
public static void main(String[] args) { TreeSet<Integer> treeSet = new TreeSet<>(); treeSet.add(5); treeSet.add(3); treeSet.add(8); treeSet.add(1); System.out.println(treeSet); System.out.println("First: " + treeSet.first()); System.out.println("Last: " + treeSet.last()); System.out.println(treeSet.contains(3)); System.out.println(treeSet.contains(7)); System.out.println(treeSet.lower(5)); System.out.println(treeSet.ceiling(4)); }
2.2.3Queue接口及其实现类
Queue 接口 是 java.util 包的一部分，用于表示一个 先进先出（FIFO） 数据结构。Queue 接口提供了一系列方法来操作队列中的元素，同时 Java 提供了多个实现类以适应不同场景的需求。其中常用的实现类：LinkedList, PriorityQueue，ArrayDeque。下面详细讲解后俩个，第一个链表以及前文提及。
PriorityQueue
基本原理：
PriorityQueue是一个基于堆实现的优先队列，能够按照元素的 自然顺序 或自定义的 比较规则 对元素排序。特点：
- 排序队列：
- 元素入队后自动排序。
- 优先级最高的元素会被最先移除。
- 基于堆实现：
- 默认是最小堆，头元素是最小值。
- 可以通过自定义比较器实现最大堆。
- 动态扩容：
- 初始容量为 11，满时容量会动态扩展至 1.5 倍。
- 允许重复元素：
- 不像
Set接口，PriorityQueue中允许相同优先级的元素重复。常用方法：
boolean add(E e)：添加元素，若超出容量抛出异常。boolean offer(E e)：添加元素，若超出容量返回false。E remove()：移除并返回优先级最高的元素，若队列为空抛出异常。E poll()：移除并返回优先级最高的元素，若队列为空返回null。E element()：返回优先级最高的元素但不移除，若队列为空抛出异常。E peek()：返回优先级最高的元素但不移除，若队列为空返回null。boolean isEmpty()：判断队列是否为空。int size()：返回队列中的元素个数。void clear()：清空队列。代码示例：
public static class Student implements Comparable<Student>{ private String name; private int age; public Student(String name, int age) { this.name = name; this.age = age; } @Override // 按年龄升序排序 public int compareTo(Student other) { return Integer.compare(this.age, other.age); } @Override//重写转字符串的方法，方便输出调试 public String toString() { return "姓名" + this.name + " 年龄" + this.age; } } public static void main(String[] args) { //创建堆时，如果不指定比较器则默认小顶堆 PriorityQueue<Integer> test1 = new PriorityQueue<>(); test1.add(2); test1.add(1); test1.add(3); while(!test1.isEmpty()){ System.out.print(test1.poll() + " "); } System.out.println(); System.out.println("------------------------"); PriorityQueue<Integer> test2 = new PriorityQueue<>(Comparator.reverseOrder()); test2.add(2); test2.add(1); test2.add(3); while(!test2.isEmpty()){ System.out.print(test2.poll() + " "); } System.out.println(); System.out.println("------------------------"); //如果需要对自定义对象排序，可以让类实现 Comparable 接口，或在 PriorityQueue 构造函数中传入 Comparator。 PriorityQueue<Student> test3 = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1.age,o2.age))); test3.offer(new Student("tom",16)); test3.offer(new Student("jerry",12)); test3.offer(new Student("Amy",18)); while(!test3.isEmpty()){ System.out.println(test3.poll()); } }
2.3Map接口
Map 是一个用于存储键值对（key-value）的集合接口。它提供了将唯一的键映射到特定值的功能，广泛应用于需要快速查找数据的场景。这里我们着重讲解HashMap和TreeMap
HashMap
基本原理：
- 数组（Table）:
- HashMap 的底层结构是一个数组，数组中的每个元素称为桶（Bucket）。
- 哈希函数:
- 将键的哈希值（通过
hashCode()方法计算）与桶的索引关联起来。- 链表和红黑树:
- 同一哈希值的键可能映射到同一个桶（发生哈希冲突），此时会使用链表或红黑树来解决冲突。
特点：
- 键不能重复，但值可以重复。
- 允许
null键（最多一个）和多个null值。- 无序存储，不保证插入顺序。
常用方法：
put(K key, V value)：插入一个键值对。如果键已存在，则更新对应的值。get(Object key)：根据键获取对应的值。如果键不存在，返回null。remove(Object key)：删除指定键的键值对，并返回被删除的值。如果键不存在，返回null。containsKey(Object key)：检查是否包含指定的键，返回true或false。containsValue(Object value)：检查是否包含指定的值，返回true或false。size()：返回当前 HashMap 中键值对的数量。isEmpty()：检查 HashMap 是否为空，返回true或false。clear()：清空所有键值对，使 HashMap 变为空。keySet()：返回所有键的集合（Set）。values()：返回所有值的集合（Collection）。entrySet()：返回所有键值对的集合（Set<Map.Entry>）。代码示例：
public static void main(String[] args) { Student s1 = new Student(17, "张三"); Student s2 = new Student(17, "张三"); HashMap<Student, String> map = new HashMap<>(); map.put(s1, "这是张三"); System.out.println(map.containsKey(s1)); System.out.println(map.containsKey(s2)); map.put(s2, "这也是张三"); System.out.println(map.size()); System.out.println(map.get(s1)); System.out.println(map.get(s2)); } public static class Student { public int age; public String name; public Student(int a, String b) { age = a; name = b; } }
TreeMap
TreeMap 是基于红黑树（Red-Black Tree）实现的 Map 接口的有序集合。它按键的自然顺序或指定的比较器顺序排序，适用于需要排序和高效范围查询的场景。以下是对 TreeMap 的详细解析。
基本原理：
数据存储
TreeMap 使用红黑树结构存储键值对，红黑树是一种自平衡的二叉搜索树。排序特性
- 默认按键的自然顺序（由键的
Comparable接口决定）。- 可以通过构造函数指定自定义的
Comparator进行排序。键的要求
- 键必须实现
Comparable接口，或者必须提供Comparator。- 键不能为
null（与 HashMap 不同）。特点：
- 有序性：键值对按键的自然顺序或自定义比较器排序。
- 底层实现：基于红黑树，保证操作的时间复杂度为 O(logn)O(\log n)O(logn)。
- 键的限制：键必须实现
Comparable或提供Comparator，且键不能为null。- 支持范围操作：如
subMap()、headMap()、tailMap()提供高效的范围查询。常用方法：
put(K key, V value)：将键值对插入到 TreeMap 中。如果键已存在，则更新值。get(Object key)：根据键获取值。如果键不存在，返回null。remove(Object key)：删除指定键的键值对，返回被删除的值。firstKey()：返回 TreeMap 中最小的键。lastKey()：返回 TreeMap 中最大的键。subMap(K fromKey, K toKey)：返回从fromKey（包含）到toKey（不包含）的子集视图。headMap(K toKey)：返回小于toKey的键值对视图。tailMap(K fromKey)：返回大于等于fromKey的键值对视图。代码示例：
public static void main(String[] args) { TreeMap<Integer, String> treeMap = new TreeMap<>(); treeMap.put(5, "这是5"); treeMap.put(7, "这是7"); treeMap.put(1, "这是1"); treeMap.put(2, "这是2"); treeMap.put(3, "这是3"); treeMap.put(4, "这是4"); treeMap.put(8, "这是8"); System.out.println(treeMap.containsKey(1)); System.out.println(treeMap.containsKey(10)); System.out.println(treeMap.get(4)); treeMap.put(4, "张三是4"); System.out.println(treeMap.get(4)); treeMap.remove(4); System.out.println(treeMap.get(4) == null); System.out.println(treeMap.firstKey()); System.out.println(treeMap.lastKey()); System.out.println(treeMap.floorKey(4)); System.out.println(treeMap.ceilingKey(4)); }
3.小结
今天的分享到这里就结束了，万字文章终于要收尾了，喜欢的小伙伴点点关注点点赞，未来的编程之旅让我伴你前行，大家加油！
原文地址：https://blog.csdn.net/2301_81073317/article/details/143835097
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！