第七章 常用类与集合框架

第二节 集合框架与常用数据结构

---

概述

本节内容重点讲解Java面向对象程序设计中的集合框架及常用数据结构。集合框架是Java提供的一套用于存储、操作数据的接口和实现类体系。掌握集合框架不仅能帮助我们更高效地管理数据，还能提升程序设计的灵活性和性能。本节通过理论讲解与实例分析，帮助考生系统理解集合框架的核心接口、常用实现类的特点及其应用场景，掌握各类数据结构的原理与使用方法，为全国计算机等级考试四级中的面向对象程序设计部分打下坚实基础。

学习目标：

• 理解集合框架的组成和核心接口
• 掌握List、Set、Map三大集合的特点和应用
• 理解常用数据结构的工作原理及性能差异
• 熟悉集合的遍历、增删改查操作
• 掌握典型案例分析，避免常见误区

---

核心概念

1. 集合框架（Collection Framework）

   • Java中用于存储和操作一组对象的统一架构，包含接口、实现类及算法。

2. 接口（Interface）

   • 定义集合的抽象行为，如Collection、List、Set、Map等。

3. 实现类（Implementation Class）

   • 接口的具体实现，如ArrayList、LinkedList、HashSet、TreeSet、HashMap等。

4. List接口

   • 有序集合，允许元素重复，支持按索引访问。

5. Set接口

   • 不允许元素重复的集合，无序或有序（如HashSet、TreeSet）。

6. Map接口

   • 键值对集合，键唯一，值可重复，用于存储映射关系。

7. 数据结构

   • 存储和组织数据的方式，如数组、链表、哈希表、树等。

8. 泛型（Generics）

   • 提供类型安全的集合，实现编译时类型检查。

---

原理分析

1. 集合框架的设计理念

集合框架设计遵循统一接口和多态性原则，简化程序开发。用户通过接口编程，减少对实现细节依赖。核心接口如Collection、Map，定义通用操作，具体实现类负责性能优化。

2. 数据结构与性能核心

• 数组（Array）：连续内存，随机访问快，但插入删除成本高。
• 链表（LinkedList）：节点链式存储，插入删除快，随机访问慢。
• 哈希表（HashMap、HashSet）：通过哈希函数实现快速查找，插入删除效率高。
• 树（TreeSet、TreeMap）：基于红黑树实现，保持元素有序，查找插入效率为O(log n)。

理解这些底层结构有助于选择合适集合，提高程序效率。

3. 迭代器（Iterator）机制

集合框架提供统一的迭代器接口，用于遍历集合元素，支持安全删除，避免并发修改异常。

---

详细内容

1. 集合框架结构及核心接口

Java集合框架主要分为两大体系：

• Collection接口体系：包括List、Set、Queue等，主要用于存储一组元素。
• Map接口体系：用于存储键值对。

接口	说明	主要实现类
List	有序集合，允许元素重复	ArrayList、LinkedList、Vector
Set	不允许元素重复，无序或有序	HashSet、LinkedHashSet、TreeSet
Map	键值对映射，键唯一	HashMap、LinkedHashMap、TreeMap

Collection接口定义了基本操作，如add、remove、contains，size等。

Map接口定义put、get、remove等操作。

2. List接口详解

List是有序集合，允许重复元素，支持索引访问。常用实现类：

• ArrayList：基于动态数组实现，支持快速随机访问，插入删除相对较慢（尤其是在中间位置）。线程不安全。
• LinkedList：基于双向链表实现，插入删除效率高，随机访问慢。
• Vector：类似ArrayList，但线程安全，性能较低，不推荐使用。

操作示例：

• 添加元素：add(E e)、add(int index, E e)
• 访问元素：get(int index)
• 删除元素：remove(int index)、remove(Object o)
• 遍历方法：for循环、增强for循环、Iterator

3. Set接口详解

Set不允许重复元素，重写equals和hashCode是保证元素唯一性的关键。

• HashSet：基于哈希表实现，无序。插入、删除、查找效率高。
• LinkedHashSet：HashSet的子类，维护元素插入顺序。
• TreeSet：基于红黑树实现，元素自动排序。

操作注意：

• 元素必须实现Comparable接口，或在构造TreeSet时提供Comparator。
• 重写hashCode()和equals()方法保证唯一性。

4. Map接口详解

Map存储键值对，键唯一。常用实现类：

• HashMap：基于哈希表，线程不安全，性能优。
• LinkedHashMap：维护插入顺序或访问顺序。
• TreeMap：基于红黑树，键自动排序。

基本操作：

• put(key, value)
• get(key)
• remove(key)
• containsKey(key)
• keySet(), values(), entrySet()用于遍历

线程安全的版本是Hashtable和ConcurrentHashMap，但使用较少。

5. 集合遍历与迭代器

集合提供多种遍历方式：

• 增强for循环（for-each）：简洁，适用于Collection和数组。
• Iterator迭代器：支持安全删除，适合复杂操作。
• ListIterator：仅List实现，支持双向遍历，元素修改。

避免在遍历时进行结构性修改，否则可能抛出ConcurrentModificationException。

6. 泛型在集合中的应用

泛型使集合类型安全，避免强制类型转换。

示例：

List<String> list = new ArrayList<>();
list.add("Java");
String s = list.get(0); // 无需强制转换

---

实例分析

实例1：使用ArrayList管理学生名单

背景：设计一个程序管理班级学生名单，要求支持添加、删除、查询学生。

分析：

• 使用ArrayList存储学生对象，因其支持随机访问，方便快速获取指定位置学生。
• 添加操作用add()，删除用remove()。
• 查询用get(index)或遍历。

代码示例：

List<String> students = new ArrayList<>();
students.add("张三");
students.add("李四");

// 遍历
for(String name : students) {
    System.out.println(name);
}

// 删除
students.remove("张三");

结论：ArrayList适合频繁读操作，简单管理学生名单。

实例2：使用HashSet实现员工编号去重

背景：公司员工编号需要保证唯一，防止重复录入。

分析：

• 使用HashSet存储员工编号，自动去重。
• 添加重复编号时，HashSet不会存储。

代码示例：

Set<String> employeeIDs = new HashSet<>();
employeeIDs.add("E123");
employeeIDs.add("E456");
employeeIDs.add("E123"); // 不会被添加

System.out.println(employeeIDs.size()); // 输出2

结论：HashSet高效解决唯一性问题。

实例3：使用HashMap统计单词出现次数

背景：统计一段文本中每个单词出现的频率。

分析：

• 使用HashMap，键为单词，值为出现次数。
• 遍历文本，遇到单词则更新计数。

代码示例：

Map<String, Integer> wordCount = new HashMap<>();
String[] words = text.split("\\s+");
for(String word : words) {
    wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}

for(Map.Entry<String, Integer> entry : wordCount.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

结论：HashMap适合映射关系处理和统计。

---

常见误区

1. 误区：认为List中的元素一定唯一

   • List允许重复元素，若需唯一元素应使用Set。

2. 误区：未重写hashCode和equals导致Set中出现重复元素

   • 必须重写这两个方法保证元素唯一性。

3. 误区：遍历集合时修改集合结构导致ConcurrentModificationException

   • 应使用Iterator的remove方法或避免在遍历时修改结构。

4. 误区：错误使用Vector代替ArrayList，导致性能下降

   • Vector是线程安全但性能低，单线程环境推荐使用ArrayList。

5. 误区：将Map当作Collection使用，混淆两者区别

   • Map不继承Collection接口，操作方式不同。

---

应用场景

1. 学生信息管理系统

   • 使用List存储学生数据，Set避免学号重复，Map实现学生与成绩映射。

2. 电商购物车实现

   • List储存购物商品顺序，Map存储商品ID与数量对应关系。

3. 日志分析统计

   • HashMap统计访问次数，Set过滤重复IP。

4. 社交网络关系管理

   • Map存储用户与好友列表，Set存储关注者集合。

5. 缓存系统设计

   • LinkedHashMap实现访问顺序缓存淘汰。

---

知识拓展

• 线程安全集合类：了解Collections.synchronizedXXX()包装类，及并发包中的ConcurrentHashMap、CopyOnWriteArrayList。
• 自定义比较器：实现Comparator接口定制排序规则。
• 集合工具类Collections和Arrays：常用排序、查找、同步操作。
• JDK 8 Stream API与集合操作：函数式编程对集合的高效处理。
• 设计模式中集合框架的应用：如观察者模式中使用集合管理监听器。

---

总结回顾

本节重点围绕Java集合框架与常用数据结构展开，涵盖了：

• 集合框架的核心接口和实现类，理解List、Set、Map三大接口的特点与应用
• 详细分析ArrayList、LinkedList、HashSet、TreeSet、HashMap等核心类的结构与性能
• 掌握集合的遍历方式和泛型的应用，确保代码类型安全
• 通过实例演示集合的实际使用场景，提升理解和应用能力
• 指出常见误区，避免考试和实际开发中的错误
• 结合应用场景和知识拓展，拓宽学习视野，提升综合能力

通过系统学习本节内容，考生可以全面掌握面向对象程序设计中集合框架的知识，为全国计算机等级考试四级的相关考点做好充分准备。

---