本章将详细介绍Java集合框架中的Set接口和Map接口及其主要实现类，包括HashSet、LinkedHashSet、TreeSet、HashMap、LinkedHashMap、TreeMap等。
8.1 Set接口和实现类
8.1.1 HashSet详解
import java.util.*;
/**
* HashSet详细演示
*/
public class HashSetDemo {
public static void main(String[] args) {
System.out.println("=== HashSet详细演示 ===");
demonstrateBasicOperations();
demonstrateSetProperties();
demonstrateHashCodeAndEquals();
demonstratePerformance();
demonstrateUseCases();
}
public static void demonstrateBasicOperations() {
System.out.println("\n--- HashSet基本操作 ---");
// 1. 创建HashSet
Set<String> fruits = new HashSet<>();
// 2. 添加元素
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");
fruits.add("Apple"); // 重复元素，不会被添加
System.out.println("添加元素后: " + fruits);
System.out.println("集合大小: " + fruits.size());
// 3. 检查元素
System.out.println("\n检查元素:");
System.out.println("包含Apple: " + fruits.contains("Apple"));
System.out.println("包含Orange: " + fruits.contains("Orange"));
System.out.println("集合是否为空: " + fruits.isEmpty());
// 4. 删除元素
boolean removed = fruits.remove("Banana");
System.out.println("\n删除Banana: " + removed);
System.out.println("删除后: " + fruits);
// 5. 遍历元素
System.out.println("\n遍历元素:");
for (String fruit : fruits) {
System.out.println("- " + fruit);
}
// 6. 批量操作
Set<String> moreFruits = new HashSet<>(Arrays.asList("Date", "Elderberry", "Apple"));
System.out.println("\n批量操作:");
System.out.println("原集合: " + fruits);
System.out.println("新集合: " + moreFruits);
// 并集
Set<String> union = new HashSet<>(fruits);
union.addAll(moreFruits);
System.out.println("并集: " + union);
// 交集
Set<String> intersection = new HashSet<>(fruits);
intersection.retainAll(moreFruits);
System.out.println("交集: " + intersection);
// 差集
Set<String> difference = new HashSet<>(fruits);
difference.removeAll(moreFruits);
System.out.println("差集: " + difference);
}
public static void demonstrateSetProperties() {
System.out.println("\n--- Set集合特性 ---");
Set<Integer> numbers = new HashSet<>();
// 1. 唯一性
System.out.println("\n1. 元素唯一性:");
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(2); // 重复元素
numbers.add(1); // 重复元素
System.out.println("添加重复元素后: " + numbers);
System.out.println("实际大小: " + numbers.size());
// 2. 无序性
System.out.println("\n2. 元素无序性:");
Set<String> letters = new HashSet<>();
letters.add("Z");
letters.add("A");
letters.add("M");
letters.add("B");
System.out.println("添加顺序: Z, A, M, B");
System.out.println("存储顺序: " + letters);
System.out.println("注意: HashSet不保证元素顺序");
// 3. null值处理
System.out.println("\n3. null值处理:");
Set<String> withNull = new HashSet<>();
withNull.add("Value1");
withNull.add(null);
withNull.add("Value2");
withNull.add(null); // 重复的null
System.out.println("包含null的集合: " + withNull);
System.out.println("null的数量: 1个（Set保证唯一性）");
}
public static void demonstrateHashCodeAndEquals() {
System.out.println("\n--- hashCode和equals的重要性 ---");
// 1. 正确实现hashCode和equals的类
System.out.println("\n1. 正确实现的Person类:");
Set<Person> people = new HashSet<>();
Person person1 = new Person("张三", 25);
Person person2 = new Person("张三", 25); // 内容相同但是不同对象
Person person3 = new Person("李四", 30);
people.add(person1);
people.add(person2); // 应该不会被添加（内容重复）
people.add(person3);
System.out.println("添加3个Person对象:");
for (Person person : people) {
System.out.println("- " + person);
}
System.out.println("实际大小: " + people.size() + " (person1和person2被认为是同一个)");
// 2. 错误实现hashCode和equals的类
System.out.println("\n2. 错误实现的BadPerson类:");
Set<BadPerson> badPeople = new HashSet<>();
BadPerson badPerson1 = new BadPerson("张三", 25);
BadPerson badPerson2 = new BadPerson("张三", 25);
badPeople.add(badPerson1);
badPeople.add(badPerson2); // 会被添加（因为没有正确实现equals和hashCode）
System.out.println("添加2个内容相同的BadPerson对象:");
for (BadPerson person : badPeople) {
System.out.println("- " + person);
}
System.out.println("实际大小: " + badPeople.size() + " (被认为是不同对象)");
// 3. 演示hashCode的重要性
System.out.println("\n3. hashCode分布演示:");
demonstrateHashCodeDistribution();
}
private static void demonstrateHashCodeDistribution() {
Set<String> words = new HashSet<>();
words.add("apple");
words.add("banana");
words.add("cherry");
words.add("date");
System.out.println("字符串的hashCode分布:");
for (String word : words) {
System.out.println(word + " -> hashCode: " + word.hashCode());
}
}
public static void demonstratePerformance() {
System.out.println("\n--- HashSet性能特征 ---");
int size = 1000000;
Set<Integer> hashSet = new HashSet<>();
// 1. 添加性能
long startTime = System.nanoTime();
for (int i = 0; i < size; i++) {
hashSet.add(i);
}
long addTime = System.nanoTime() - startTime;
// 2. 查找性能
Random random = new Random();
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
hashSet.contains(random.nextInt(size));
}
long searchTime = System.nanoTime() - startTime;
// 3. 删除性能
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
hashSet.remove(i);
}
long removeTime = System.nanoTime() - startTime;
System.out.println("性能测试结果:");
System.out.println("添加" + size + "个元素耗时: " + addTime / 1000000 + "ms");
System.out.println("查找100000次耗时: " + searchTime / 1000000 + "ms");
System.out.println("删除10000个元素耗时: " + removeTime / 1000000 + "ms");
System.out.println("\nHashSet特点:");
System.out.println("- 基于哈希表实现");
System.out.println("- 平均时间复杂度: O(1)");
System.out.println("- 最坏时间复杂度: O(n) (哈希冲突严重时)");
System.out.println("- 不保证元素顺序");
System.out.println("- 允许null值");
System.out.println("- 非线程安全");
}
public static void demonstrateUseCases() {
System.out.println("\n--- HashSet使用场景 ---");
// 1. 去重
System.out.println("\n1. 数据去重:");
List<String> duplicateList = Arrays.asList(
"apple", "banana", "apple", "cherry", "banana", "date"
);
Set<String> uniqueItems = new HashSet<>(duplicateList);
System.out.println("原始列表: " + duplicateList);
System.out.println("去重后: " + uniqueItems);
// 2. 快速查找
System.out.println("\n2. 快速成员检查:");
Set<String> validUsers = new HashSet<>(Arrays.asList(
"admin", "user1", "user2", "guest"
));
String[] loginAttempts = {"admin", "hacker", "user1", "unknown"};
for (String user : loginAttempts) {
if (validUsers.contains(user)) {
System.out.println(user + ": 登录成功");
} else {
System.out.println(user + ": 登录失败 - 无效用户");
}
}
// 3. 集合运算
System.out.println("\n3. 集合运算应用:");
Set<String> course1Students = new HashSet<>(Arrays.asList(
"张三", "李四", "王五", "赵六"
));
Set<String> course2Students = new HashSet<>(Arrays.asList(
"李四", "王五", "钱七", "孙八"
));
// 同时选修两门课的学生
Set<String> bothCourses = new HashSet<>(course1Students);
bothCourses.retainAll(course2Students);
System.out.println("同时选修两门课: " + bothCourses);
// 只选修课程1的学生
Set<String> onlyCourse1 = new HashSet<>(course1Students);
onlyCourse1.removeAll(course2Students);
System.out.println("只选修课程1: " + onlyCourse1);
// 所有学生
Set<String> allStudents = new HashSet<>(course1Students);
allStudents.addAll(course2Students);
System.out.println("所有学生: " + allStudents);
// 4. 缓存已处理的项目
System.out.println("\n4. 缓存已处理项目:");
Set<String> processedFiles = new HashSet<>();
String[] files = {"file1.txt", "file2.txt", "file1.txt", "file3.txt", "file2.txt"};
for (String file : files) {
if (!processedFiles.contains(file)) {
System.out.println("处理文件: " + file);
processedFiles.add(file);
} else {
System.out.println("跳过已处理文件: " + file);
}
}
}
// 正确实现hashCode和equals的Person类
static class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Person person = (Person) obj;
return age == person.age && Objects.equals(name, person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public String toString() {
return "Person{name='" + name + "', age=" + age + "}";
}
}
// 错误实现（没有重写hashCode和equals）的BadPerson类
static class BadPerson {
private String name;
private int age;
public BadPerson(String name, int age) {
this.name = name;
this.age = age;
}
// 没有重写equals和hashCode，使用Object的默认实现
@Override
public String toString() {
return "BadPerson{name='" + name + "', age=" + age + "}";
}
}
}
8.1.2 LinkedHashSet详解
import java.util.*;
/**
* LinkedHashSet详细演示
*/
public class LinkedHashSetDemo {
public static void main(String[] args) {
System.out.println("=== LinkedHashSet详细演示 ===");
demonstrateInsertionOrder();
demonstrateVsHashSet();
demonstratePerformance();
demonstrateUseCases();
}
public static void demonstrateInsertionOrder() {
System.out.println("\n--- LinkedHashSet插入顺序保持 ---");
// 1. LinkedHashSet保持插入顺序
LinkedHashSet<String> linkedSet = new LinkedHashSet<>();
linkedSet.add("First");
linkedSet.add("Second");
linkedSet.add("Third");
linkedSet.add("Fourth");
linkedSet.add("Second"); // 重复元素，不会改变顺序
System.out.println("LinkedHashSet (保持插入顺序): " + linkedSet);
// 2. HashSet不保证顺序
HashSet<String> hashSet = new HashSet<>();
hashSet.add("First");
hashSet.add("Second");
hashSet.add("Third");
hashSet.add("Fourth");
System.out.println("HashSet (不保证顺序): " + hashSet);
// 3. 遍历顺序
System.out.println("\nLinkedHashSet遍历顺序:");
int index = 1;
for (String item : linkedSet) {
System.out.println(index++ + ". " + item);
}
// 4. 删除和重新添加
System.out.println("\n删除和重新添加测试:");
linkedSet.remove("Second");
System.out.println("删除Second后: " + linkedSet);
linkedSet.add("Second");
System.out.println("重新添加Second: " + linkedSet);
System.out.println("注意: Second被添加到末尾");
}
public static void demonstrateVsHashSet() {
System.out.println("\n--- LinkedHashSet vs HashSet 对比 ---");
// 创建相同内容的两个集合
String[] items = {"Apple", "Banana", "Cherry", "Date", "Elderberry"};
LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
HashSet<String> hashSet = new HashSet<>();
for (String item : items) {
linkedHashSet.add(item);
hashSet.add(item);
}
System.out.println("添加顺序: " + Arrays.toString(items));
System.out.println("LinkedHashSet: " + linkedHashSet);
System.out.println("HashSet: " + hashSet);
// 多次遍历，LinkedHashSet顺序一致
System.out.println("\n多次遍历LinkedHashSet:");
for (int i = 1; i <= 3; i++) {
System.out.print("第" + i + "次: ");
for (String item : linkedHashSet) {
System.out.print(item + " ");
}
System.out.println();
}
// 内存使用对比
System.out.println("\n内存使用对比:");
System.out.println("LinkedHashSet: 额外维护双向链表，内存开销更大");
System.out.println("HashSet: 只维护哈希表，内存开销较小");
}
public static void demonstratePerformance() {
System.out.println("\n--- 性能对比测试 ---");
int size = 100000;
// 1. 添加性能
System.out.println("\n1. 添加性能测试:");
LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>();
long startTime = System.nanoTime();
for (int i = 0; i < size; i++) {
linkedHashSet.add(i);
}
long linkedHashSetAddTime = System.nanoTime() - startTime;
HashSet<Integer> hashSet = new HashSet<>();
startTime = System.nanoTime();
for (int i = 0; i < size; i++) {
hashSet.add(i);
}
long hashSetAddTime = System.nanoTime() - startTime;
System.out.println("LinkedHashSet添加耗时: " + linkedHashSetAddTime / 1000000 + "ms");
System.out.println("HashSet添加耗时: " + hashSetAddTime / 1000000 + "ms");
// 2. 查找性能
System.out.println("\n2. 查找性能测试:");
Random random = new Random();
startTime = System.nanoTime();
for (int i = 0; i < 50000; i++) {
linkedHashSet.contains(random.nextInt(size));
}
long linkedHashSetSearchTime = System.nanoTime() - startTime;
startTime = System.nanoTime();
for (int i = 0; i < 50000; i++) {
hashSet.contains(random.nextInt(size));
}
long hashSetSearchTime = System.nanoTime() - startTime;
System.out.println("LinkedHashSet查找耗时: " + linkedHashSetSearchTime / 1000000 + "ms");
System.out.println("HashSet查找耗时: " + hashSetSearchTime / 1000000 + "ms");
// 3. 遍历性能
System.out.println("\n3. 遍历性能测试:");
startTime = System.nanoTime();
for (Integer item : linkedHashSet) {
// 空操作，只测试遍历
}
long linkedHashSetIterateTime = System.nanoTime() - startTime;
startTime = System.nanoTime();
for (Integer item : hashSet) {
// 空操作，只测试遍历
}
long hashSetIterateTime = System.nanoTime() - startTime;
System.out.println("LinkedHashSet遍历耗时: " + linkedHashSetIterateTime / 1000000 + "ms");
System.out.println("HashSet遍历耗时: " + hashSetIterateTime / 1000000 + "ms");
System.out.println("\n性能总结:");
System.out.println("- LinkedHashSet比HashSet稍慢（维护链表开销）");
System.out.println("- 但性能差异通常很小");
System.out.println("- 遍历性能LinkedHashSet可能更好（链表顺序访问）");
}
public static void demonstrateUseCases() {
System.out.println("\n--- LinkedHashSet使用场景 ---");
// 1. 保持处理顺序的去重
System.out.println("\n1. 保持处理顺序的去重:");
List<String> processingQueue = Arrays.asList(
"task1", "task2", "task1", "task3", "task2", "task4"
);
LinkedHashSet<String> uniqueTasks = new LinkedHashSet<>(processingQueue);
System.out.println("原始队列: " + processingQueue);
System.out.println("去重后保持顺序: " + uniqueTasks);
// 2. 用户访问历史
System.out.println("\n2. 用户访问历史记录:");
UserVisitHistory visitHistory = new UserVisitHistory(5);
visitHistory.visit("首页");
visitHistory.visit("产品页");
visitHistory.visit("关于我们");
visitHistory.visit("首页"); // 重复访问
visitHistory.visit("联系我们");
visitHistory.visit("产品页"); // 重复访问
visitHistory.visit("帮助页面");
System.out.println("访问历史: " + visitHistory.getHistory());
// 3. 配置项管理
System.out.println("\n3. 配置项管理:");
ConfigurationManager config = new ConfigurationManager();
config.addConfig("database.url", "jdbc:mysql://localhost:3306/db");
config.addConfig("database.username", "admin");
config.addConfig("server.port", "8080");
config.addConfig("database.url", "jdbc:mysql://localhost:3306/newdb"); // 更新配置
config.addConfig("logging.level", "INFO");
System.out.println("配置项（保持添加顺序）:");
config.printConfigs();
// 4. 缓存最近使用项
System.out.println("\n4. 最近使用项缓存:");
RecentItemsCache<String> recentCache = new RecentItemsCache<>(3);
recentCache.access("文档1");
recentCache.access("文档2");
recentCache.access("文档3");
recentCache.access("文档1"); // 重复访问
recentCache.access("文档4"); // 超出容量
System.out.println("最近访问的文档: " + recentCache.getRecentItems());
}
// 用户访问历史类
static class UserVisitHistory {
private LinkedHashSet<String> history;
private int maxSize;
public UserVisitHistory(int maxSize) {
this.maxSize = maxSize;
this.history = new LinkedHashSet<>();
}
public void visit(String page) {
// 如果已存在，先删除（这样重新添加时会放到末尾）
if (history.contains(page)) {
history.remove(page);
}
history.add(page);
// 如果超出最大大小，删除最旧的（第一个）
if (history.size() > maxSize) {
Iterator<String> iterator = history.iterator();
iterator.next();
iterator.remove();
}
}
public LinkedHashSet<String> getHistory() {
return new LinkedHashSet<>(history);
}
}
// 配置管理器
static class ConfigurationManager {
private LinkedHashSet<ConfigItem> configs;
public ConfigurationManager() {
this.configs = new LinkedHashSet<>();
}
public void addConfig(String key, String value) {
ConfigItem newItem = new ConfigItem(key, value);
// 如果已存在相同key的配置，先删除
configs.removeIf(item -> item.key.equals(key));
// 添加新配置
configs.add(newItem);
}
public void printConfigs() {
for (ConfigItem item : configs) {
System.out.println(" " + item.key + " = " + item.value);
}
}
static class ConfigItem {
String key;
String value;
ConfigItem(String key, String value) {
this.key = key;
this.value = value;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
ConfigItem that = (ConfigItem) obj;
return Objects.equals(key, that.key);
}
@Override
public int hashCode() {
return Objects.hash(key);
}
}
}
// 最近使用项缓存
static class RecentItemsCache<T> {
private LinkedHashSet<T> items;
private int maxSize;
public RecentItemsCache(int maxSize) {
this.maxSize = maxSize;
this.items = new LinkedHashSet<>();
}
public void access(T item) {
// 如果已存在，先删除
if (items.contains(item)) {
items.remove(item);
}
// 添加到末尾
items.add(item);
// 如果超出容量，删除最旧的
if (items.size() > maxSize) {
Iterator<T> iterator = items.iterator();
iterator.next();
iterator.remove();
}
}
public List<T> getRecentItems() {
return new ArrayList<>(items);
}
}
}
8.1.3 TreeSet详解
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
/**
* TreeSet详细演示
*/
public class TreeSetDemo {
public static void main(String[] args) {
System.out.println("=== TreeSet详细演示 ===");
demonstrateBasicOperations();
demonstrateSortingAndComparison();
demonstrateNavigationMethods();
demonstrateSubSetOperations();
demonstratePerformance();
demonstrateUseCases();
}
public static void demonstrateBasicOperations() {
System.out.println("\n--- TreeSet基本操作 ---");
// 1. 创建TreeSet（自然排序）
TreeSet<Integer> numbers = new TreeSet<>();
// 2. 添加元素（自动排序）
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);
numbers.add(9);
numbers.add(3);
System.out.println("添加顺序: 5, 2, 8, 1, 9, 3");
System.out.println("TreeSet内容: " + numbers);
System.out.println("注意: 元素自动按升序排列");
// 3. 基本操作
System.out.println("\n基本操作:");
System.out.println("包含5: " + numbers.contains(5));
System.out.println("大小: " + numbers.size());
System.out.println("是否为空: " + numbers.isEmpty());
// 4. 删除元素
numbers.remove(5);
System.out.println("删除5后: " + numbers);
// 5. 字符串TreeSet
TreeSet<String> words = new TreeSet<>();
words.add("banana");
words.add("apple");
words.add("cherry");
words.add("date");
System.out.println("\n字符串TreeSet: " + words);
System.out.println("按字典序排列");
}
public static void demonstrateSortingAndComparison() {
System.out.println("\n--- 排序和比较器 ---");
// 1. 自然排序
System.out.println("\n1. 自然排序:");
TreeSet<Integer> naturalOrder = new TreeSet<>();
int[] values = {3, 1, 4, 1, 5, 9, 2, 6, 5};
for (int value : values) {
naturalOrder.add(value);
}
System.out.println("原始数组: " + Arrays.toString(values));
System.out.println("自然排序: " + naturalOrder);
// 2. 自定义比较器（降序）
System.out.println("\n2. 自定义比较器（降序）:");
TreeSet<Integer> reverseOrder = new TreeSet<>(Collections.reverseOrder());
for (int value : values) {
reverseOrder.add(value);
}
System.out.println("降序排序: " + reverseOrder);
// 3. 复杂对象排序
System.out.println("\n3. 复杂对象排序:");
// 按年龄排序的学生
TreeSet<Student> studentsByAge = new TreeSet<>(Comparator.comparingInt(Student::getAge));
studentsByAge.add(new Student("张三", 20, 85));
studentsByAge.add(new Student("李四", 19, 92));
studentsByAge.add(new Student("王五", 21, 78));
studentsByAge.add(new Student("赵六", 19, 88)); // 相同年龄
System.out.println("按年龄排序:");
for (Student student : studentsByAge) {
System.out.println(" " + student);
}
// 按成绩排序的学生
TreeSet<Student> studentsByScore = new TreeSet<>(Comparator.comparingInt(Student::getScore));
studentsByScore.add(new Student("张三", 20, 85));
studentsByScore.add(new Student("李四", 19, 92));
studentsByScore.add(new Student("王五", 21, 78));
studentsByScore.add(new Student("赵六", 19, 88));
System.out.println("\n按成绩排序:");
for (Student student : studentsByScore) {
System.out.println(" " + student);
}
// 4. 多级排序
System.out.println("\n4. 多级排序（先按年龄，再按成绩）:");
TreeSet<Student> multiLevelSort = new TreeSet<>(
Comparator.comparingInt(Student::getAge)
.thenComparingInt(Student::getScore)
);
multiLevelSort.add(new Student("张三", 20, 85));
multiLevelSort.add(new Student("李四", 19, 92));
multiLevelSort.add(new Student("王五", 21, 78));
multiLevelSort.add(new Student("赵六", 19, 88));
multiLevelSort.add(new Student("钱七", 19, 95));
for (Student student : multiLevelSort) {
System.out.println(" " + student);
}
}
public static void demonstrateNavigationMethods() {
System.out.println("\n--- TreeSet导航方法 ---");
TreeSet<Integer> numbers = new TreeSet<>();
numbers.addAll(Arrays.asList(1, 3, 5, 7, 9, 11, 13, 15));
System.out.println("TreeSet: " + numbers);
// 1. 边界元素
System.out.println("\n1. 边界元素:");
System.out.println("第一个元素: " + numbers.first());
System.out.println("最后一个元素: " + numbers.last());
// 2. 查找相关元素
System.out.println("\n2. 查找相关元素:");
int target = 8;
System.out.println("目标值: " + target);
System.out.println("小于" + target + "的最大元素: " + numbers.lower(target));
System.out.println("小于等于" + target + "的最大元素: " + numbers.floor(target));
System.out.println("大于等于" + target + "的最小元素: " + numbers.ceiling(target));
System.out.println("大于" + target + "的最小元素: " + numbers.higher(target));
// 3. 删除边界元素
System.out.println("\n3. 删除边界元素:");
TreeSet<Integer> copy = new TreeSet<>(numbers);
System.out.println("删除前: " + copy);
Integer first = copy.pollFirst();
Integer last = copy.pollLast();
System.out.println("删除的第一个元素: " + first);
System.out.println("删除的最后一个元素: " + last);
System.out.println("删除后: " + copy);
// 4. 降序视图
System.out.println("\n4. 降序视图:");
NavigableSet<Integer> descendingSet = numbers.descendingSet();
System.out.println("原集合: " + numbers);
System.out.println("降序视图: " + descendingSet);
// 修改降序视图会影响原集合
descendingSet.add(17);
System.out.println("在降序视图中添加17:");
System.out.println("原集合: " + numbers);
System.out.println("降序视图: " + descendingSet);
}
public static void demonstrateSubSetOperations() {
System.out.println("\n--- TreeSet子集操作 ---");
TreeSet<Integer> numbers = new TreeSet<>();
for (int i = 1; i <= 20; i++) {
numbers.add(i);
}
System.out.println("完整集合: " + numbers);
// 1. headSet - 小于指定元素的子集
System.out.println("\n1. headSet操作:");
SortedSet<Integer> headSet = numbers.headSet(10);
System.out.println("小于10的元素: " + headSet);
NavigableSet<Integer> headSetInclusive = numbers.headSet(10, true);
System.out.println("小于等于10的元素: " + headSetInclusive);
// 2. tailSet - 大于等于指定元素的子集
System.out.println("\n2. tailSet操作:");
SortedSet<Integer> tailSet = numbers.tailSet(15);
System.out.println("大于等于15的元素: " + tailSet);
NavigableSet<Integer> tailSetExclusive = numbers.tailSet(15, false);
System.out.println("大于15的元素: " + tailSetExclusive);
// 3. subSet - 指定范围的子集
System.out.println("\n3. subSet操作:");
SortedSet<Integer> subSet = numbers.subSet(5, 15);
System.out.println("[5, 15)范围的元素: " + subSet);
NavigableSet<Integer> subSetInclusive = numbers.subSet(5, true, 15, true);
System.out.println("[5, 15]范围的元素: " + subSetInclusive);
// 4. 子集的动态特性
System.out.println("\n4. 子集的动态特性:");
System.out.println("原始子集[5, 15): " + subSet);
numbers.add(8); // 在范围内添加元素
numbers.add(25); // 在范围外添加元素
System.out.println("添加8和25后的子集: " + subSet);
subSet.remove(10); // 从子集删除元素
System.out.println("从子集删除10后的原集合: " + numbers);
}
public static void demonstratePerformance() {
System.out.println("\n--- TreeSet性能特征 ---");
int size = 100000;
// 1. 添加性能
TreeSet<Integer> treeSet = new TreeSet<>();
long startTime = System.nanoTime();
for (int i = 0; i < size; i++) {
treeSet.add(ThreadLocalRandom.current().nextInt(size * 2));
}
long addTime = System.nanoTime() - startTime;
// 2. 查找性能
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
treeSet.contains(ThreadLocalRandom.current().nextInt(size * 2));
}
long searchTime = System.nanoTime() - startTime;
// 3. 删除性能
startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
treeSet.remove(ThreadLocalRandom.current().nextInt(size * 2));
}
long removeTime = System.nanoTime() - startTime;
// 4. 遍历性能
startTime = System.nanoTime();
for (Integer num : treeSet) {
// 空操作，只测试遍历
}
long iterateTime = System.nanoTime() - startTime;
System.out.println("性能测试结果:");
System.out.println("添加" + size + "个元素耗时: " + addTime / 1000000 + "ms");
System.out.println("查找10000次耗时: " + searchTime / 1000000 + "ms");
System.out.println("删除1000个元素耗时: " + removeTime / 1000000 + "ms");
System.out.println("遍历" + treeSet.size() + "个元素耗时: " + iterateTime / 1000000 + "ms");
System.out.println("\nTreeSet特点:");
System.out.println("- 基于红黑树实现");
System.out.println("- 时间复杂度: O(log n)");
System.out.println("- 自动排序");
System.out.println("- 不允许null值");
System.out.println("- 非线程安全");
}
public static void demonstrateUseCases() {
System.out.println("\n--- TreeSet使用场景 ---");
// 1. 排行榜系统
System.out.println("\n1. 排行榜系统:");
Leaderboard leaderboard = new Leaderboard(5);
leaderboard.addScore("Alice", 1500);
leaderboard.addScore("Bob", 1200);
leaderboard.addScore("Charlie", 1800);
leaderboard.addScore("David", 1100);
leaderboard.addScore("Eve", 1600);
leaderboard.addScore("Frank", 1300);
System.out.println("排行榜前5名:");
leaderboard.printTopScores();
// 2. 时间窗口数据
System.out.println("\n2. 时间窗口数据管理:");
TimeWindowData<String> timeWindow = new TimeWindowData<>(5000); // 5秒窗口
timeWindow.addData("事件1");
try { Thread.sleep(1000); } catch (InterruptedException e) {}
timeWindow.addData("事件2");
try { Thread.sleep(2000); } catch (InterruptedException e) {}
timeWindow.addData("事件3");
System.out.println("当前窗口数据: " + timeWindow.getCurrentData());
try { Thread.sleep(3000); } catch (InterruptedException e) {}
timeWindow.addData("事件4");
System.out.println("3秒后窗口数据: " + timeWindow.getCurrentData());
// 3. 范围查询
System.out.println("\n3. 范围查询应用:");
TreeSet<Integer> scores = new TreeSet<>();
scores.addAll(Arrays.asList(65, 72, 85, 91, 78, 88, 95, 82, 76, 89));
System.out.println("所有成绩: " + scores);
System.out.println("优秀成绩(>=90): " + scores.tailSet(90));
System.out.println("良好成绩[80,90): " + scores.subSet(80, 90));
System.out.println("及格成绩[60,80): " + scores.subSet(60, 80));
// 4. 去重并排序
System.out.println("\n4. 去重并排序:");
int[] duplicateArray = {5, 2, 8, 2, 1, 9, 5, 3, 8, 1};
TreeSet<Integer> uniqueSorted = new TreeSet<>();
for (int num : duplicateArray) {
uniqueSorted.add(num);
}
System.out.println("原始数组: " + Arrays.toString(duplicateArray));
System.out.println("去重排序后: " + uniqueSorted);
}
// 学生类
static class Student {
private String name;
private int age;
private int score;
public Student(String name, int age, int score) {
this.name = name;
this.age = age;
this.score = score;
}
public String getName() { return name; }
public int getAge() { return age; }
public int getScore() { return score; }
@Override
public String toString() {
return String.format("Student{name='%s', age=%d, score=%d}", name, age, score);
}
}
// 排行榜类
static class Leaderboard {
private TreeSet<ScoreEntry> scores;
private int maxSize;
public Leaderboard(int maxSize) {
this.maxSize = maxSize;
// 按分数降序排列，分数相同时按名字排序
this.scores = new TreeSet<>((a, b) -> {
int scoreCompare = Integer.compare(b.score, a.score);
return scoreCompare != 0 ? scoreCompare : a.name.compareTo(b.name);
});
}
public void addScore(String name, int score) {
scores.add(new ScoreEntry(name, score));
// 保持排行榜大小
while (scores.size() > maxSize) {
scores.pollLast();
}
}
public void printTopScores() {
int rank = 1;
for (ScoreEntry entry : scores) {
System.out.println(rank++ + ". " + entry.name + ": " + entry.score);
}
}
static class ScoreEntry {
String name;
int score;
ScoreEntry(String name, int score) {
this.name = name;
this.score = score;
}
}
}
// 时间窗口数据类
static class TimeWindowData<T> {
private TreeSet<TimestampedData<T>> data;
private long windowSizeMs;
public TimeWindowData(long windowSizeMs) {
this.windowSizeMs = windowSizeMs;
this.data = new TreeSet<>(Comparator.comparing(TimestampedData::getTimestamp));
}
public void addData(T item) {
long now = System.currentTimeMillis();
data.add(new TimestampedData<>(item, now));
// 清理过期数据
cleanupExpiredData(now);
}
public List<T> getCurrentData() {
long now = System.currentTimeMillis();
cleanupExpiredData(now);
return data.stream()
.map(TimestampedData::getData)
.collect(ArrayList::new, ArrayList::add, ArrayList::addAll);
}
private void cleanupExpiredData(long currentTime) {
long cutoffTime = currentTime - windowSizeMs;
data.removeIf(item -> item.getTimestamp() < cutoffTime);
}
static class TimestampedData<T> {
private T data;
private long timestamp;
TimestampedData(T data, long timestamp) {
this.data = data;
this.timestamp = timestamp;
}
public T getData() { return data; }
public long getTimestamp() { return timestamp; }
}
}
}
8.2 Map接口和实现类
8.2.1 HashMap详解
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
/**
* HashMap详细演示
*/
public class HashMapDemo {
public static void main(String[] args) {
System.out.println("=== HashMap详细演示 ===");
demonstrateBasicOperations();
demonstrateAdvancedOperations();
demonstrateHashCodeImportance();
demonstratePerformance();
demonstrateUseCases();
}
public static void demonstrateBasicOperations() {
System.out.println("\n--- HashMap基本操作 ---");
// 1. 创建HashMap
Map<String, Integer> studentScores = new HashMap<>();
// 2. 添加键值对
studentScores.put("张三", 85);
studentScores.put("李四", 92);
studentScores.put("王五", 78);
studentScores.put("赵六", 88);
System.out.println("学生成绩: " + studentScores);
System.out.println("Map大小: " + studentScores.size());
// 3. 获取值
System.out.println("\n获取值:");
System.out.println("张三的成绩: " + studentScores.get("张三"));
System.out.println("不存在学生的成绩: " + studentScores.get("钱七"));
// 使用getOrDefault
System.out.println("钱七的成绩(默认0): " + studentScores.getOrDefault("钱七", 0));
// 4. 检查键和值
System.out.println("\n检查操作:");
System.out.println("包含键'李四': " + studentScores.containsKey("李四"));
System.out.println("包含值92: " + studentScores.containsValue(92));
System.out.println("是否为空: " + studentScores.isEmpty());
// 5. 更新值
System.out.println("\n更新操作:");
Integer oldScore = studentScores.put("张三", 90); // 更新张三的成绩
System.out.println("张三的旧成绩: " + oldScore);
System.out.println("更新后: " + studentScores);
// 6. 删除操作
System.out.println("\n删除操作:");
Integer removedScore = studentScores.remove("王五");
System.out.println("删除王五的成绩: " + removedScore);
System.out.println("删除后: " + studentScores);
// 7. 遍历操作
System.out.println("\n遍历操作:");
// 遍历键
System.out.print("所有学生: ");
for (String name : studentScores.keySet()) {
System.out.print(name + " ");
}
System.out.println();
// 遍历值
System.out.print("所有成绩: ");
for (Integer score : studentScores.values()) {
System.out.print(score + " ");
}
System.out.println();
// 遍历键值对
System.out.println("键值对遍历:");
for (Map.Entry<String, Integer> entry : studentScores.entrySet()) {
System.out.println(" " + entry.getKey() + ": " + entry.getValue());
}
}
public static void demonstrateAdvancedOperations() {
System.out.println("\n--- HashMap高级操作 ---");
Map<String, List<String>> courseStudents = new HashMap<>();
// 1. putIfAbsent - 仅在键不存在时添加
System.out.println("\n1. putIfAbsent操作:");
courseStudents.putIfAbsent("数学", new ArrayList<>());
courseStudents.get("数学").add("张三");
courseStudents.get("数学").add("李四");
courseStudents.putIfAbsent("数学", new ArrayList<>()); // 不会覆盖
System.out.println("数学课程学生: " + courseStudents.get("数学"));
// 2. computeIfAbsent - 计算并添加值
System.out.println("\n2. computeIfAbsent操作:");
courseStudents.computeIfAbsent("物理", k -> new ArrayList<>()).add("王五");
courseStudents.computeIfAbsent("物理", k -> new ArrayList<>()).add("赵六");
System.out.println("物理课程学生: " + courseStudents.get("物理"));
// 3. merge操作
System.out.println("\n3. merge操作:");
Map<String, Integer> wordCount = new HashMap<>();
String[] words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
for (String word : words) {
wordCount.merge(word, 1, Integer::sum);
}
System.out.println("单词计数: " + wordCount);
// 4. replace操作
System.out.println("\n4. replace操作:");
Map<String, String> userStatus = new HashMap<>();
userStatus.put("user1", "offline");
userStatus.put("user2", "online");
System.out.println("替换前: " + userStatus);
userStatus.replace("user1", "online");
userStatus.replace("user3", "online"); // 不存在的键，不会添加
System.out.println("替换后: " + userStatus);
// 条件替换
boolean replaced = userStatus.replace("user2", "online", "busy");
System.out.println("条件替换成功: " + replaced);
System.out.println("条件替换后: " + userStatus);
// 5. forEach操作
System.out.println("\n5. forEach操作:");
wordCount.forEach((word, count) ->
System.out.println(word + "出现" + count + "次"));
// 6. replaceAll操作
System.out.println("\n6. replaceAll操作:");
Map<String, String> messages = new HashMap<>();
messages.put("msg1", "hello");
messages.put("msg2", "world");
messages.put("msg3", "java");
System.out.println("转换前: " + messages);
messages.replaceAll((key, value) -> value.toUpperCase());
System.out.println("转换后: " + messages);
}
public static void demonstrateHashCodeImportance() {
System.out.println("\n--- hashCode在HashMap中的重要性 ---");
// 1. 正确实现hashCode和equals的类
System.out.println("\n1. 正确实现的Employee类:");
Map<Employee, String> employeeDepartments = new HashMap<>();
Employee emp1 = new Employee("E001", "张三");
Employee emp2 = new Employee("E001", "张三"); // 相同内容
Employee emp3 = new Employee("E002", "李四");
employeeDepartments.put(emp1, "技术部");
employeeDepartments.put(emp2, "人事部"); // 应该覆盖emp1的值
employeeDepartments.put(emp3, "财务部");
System.out.println("员工部门映射:");
employeeDepartments.forEach((emp, dept) ->
System.out.println(" " + emp + " -> " + dept));
System.out.println("Map大小: " + employeeDepartments.size());
// 2. 错误实现的类
System.out.println("\n2. 错误实现的BadEmployee类:");
Map<BadEmployee, String> badEmployeeDepartments = new HashMap<>();
BadEmployee badEmp1 = new BadEmployee("E001", "张三");
BadEmployee badEmp2 = new BadEmployee("E001", "张三");
badEmployeeDepartments.put(badEmp1, "技术部");
badEmployeeDepartments.put(badEmp2, "人事部"); // 不会覆盖，被认为是不同的键
System.out.println("错误实现的员工部门映射:");
badEmployeeDepartments.forEach((emp, dept) ->
System.out.println(" " + emp + " -> " + dept));
System.out.println("Map大小: " + badEmployeeDepartments.size());
// 3. hashCode分布演示
System.out.println("\n3. hashCode分布对性能的影响:");
demonstrateHashCodeDistribution();
}
private static void demonstrateHashCodeDistribution() {
// 好的hashCode分布
Map<GoodHashCode, String> goodMap = new HashMap<>();
for (int i = 0; i < 10; i++) {
goodMap.put(new GoodHashCode(i), "Value" + i);
}
// 坏的hashCode分布（所有对象返回相同hashCode）
Map<BadHashCode, String> badMap = new HashMap<>();
for (int i = 0; i < 10; i++) {
badMap.put(new BadHashCode(i), "Value" + i);
}
System.out.println("好的hashCode分布 - 性能测试:");
testMapPerformance(goodMap, "GoodHashCode");
System.out.println("\n坏的hashCode分布 - 性能测试:");
testMapPerformance(badMap, "BadHashCode");
}
private static <K> void testMapPerformance(Map<K, String> map, String type) {
long startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
for (K key : map.keySet()) {
map.get(key);
}
}
long endTime = System.nanoTime();
System.out.println(type + "查找耗时: " + (endTime - startTime) / 1000000 + "ms");
}
public static void demonstratePerformance() {
System.out.println("\n--- HashMap性能特征 ---");
int size = 1000000;
Map<Integer, String> hashMap = new HashMap<>();
// 1. 添加性能
long startTime = System.nanoTime();
for (int i = 0; i < size; i++) {
hashMap.put(i, "Value" + i);
}
long addTime = System.nanoTime() - startTime;
// 2. 查找性能
Random random = new Random();
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
hashMap.get(random.nextInt(size));
}
long searchTime = System.nanoTime() - startTime;
// 3. 删除性能
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
hashMap.remove(i);
}
long removeTime = System.nanoTime() - startTime;
System.out.println("性能测试结果:");
System.out.println("添加" + size + "个元素耗时: " + addTime / 1000000 + "ms");
System.out.println("查找100000次耗时: " + searchTime / 1000000 + "ms");
System.out.println("删除10000个元素耗时: " + removeTime / 1000000 + "ms");
System.out.println("\nHashMap特点:");
System.out.println("- 基于哈希表实现");
System.out.println("- 平均时间复杂度: O(1)");
System.out.println("- 最坏时间复杂度: O(n) (哈希冲突严重时)");
System.out.println("- 不保证元素顺序");
System.out.println("- 允许null键和null值");
System.out.println("- 非线程安全");
System.out.println("- 初始容量16，负载因子0.75");
}
public static void demonstrateUseCases() {
System.out.println("\n--- HashMap使用场景 ---");
// 1. 缓存系统
System.out.println("\n1. 简单缓存系统:");
SimpleCache<String, String> cache = new SimpleCache<>(3);
cache.put("user:1", "张三");
cache.put("user:2", "李四");
cache.put("user:3", "王五");
cache.put("user:4", "赵六"); // 会触发LRU淘汰
System.out.println("缓存内容: " + cache.getAll());
System.out.println("获取user:1: " + cache.get("user:1"));
// 2. 计数器
System.out.println("\n2. 字符频率统计:");
String text = "hello world hello java world";
Map<String, Integer> wordFreq = new HashMap<>();
for (String word : text.split(" ")) {
wordFreq.merge(word, 1, Integer::sum);
}
System.out.println("词频统计: " + wordFreq);
// 3. 分组操作
System.out.println("\n3. 学生按年级分组:");
List<Student> students = Arrays.asList(
new Student("张三", "一年级", 85),
new Student("李四", "二年级", 92),
new Student("王五", "一年级", 78),
new Student("赵六", "二年级", 88),
new Student("钱七", "三年级", 95)
);
Map<String, List<Student>> studentsByGrade = new HashMap<>();
for (Student student : students) {
studentsByGrade.computeIfAbsent(student.getGrade(), k -> new ArrayList<>())
.add(student);
}
studentsByGrade.forEach((grade, studentList) -> {
System.out.println(grade + ": " + studentList.size() + "人");
studentList.forEach(s -> System.out.println(" - " + s.getName()));
});
// 4. 配置管理
System.out.println("\n4. 应用配置管理:");
Map<String, Object> appConfig = new HashMap<>();
appConfig.put("database.url", "jdbc:mysql://localhost:3306/mydb");
appConfig.put("database.username", "admin");
appConfig.put("server.port", 8080);
appConfig.put("logging.enabled", true);
appConfig.put("cache.size", 1000);
System.out.println("应用配置:");
appConfig.forEach((key, value) ->
System.out.println(" " + key + " = " + value + " (" + value.getClass().getSimpleName() + ")"));
}
// 正确实现hashCode和equals的Employee类
static class Employee {
private String id;
private String name;
public Employee(String id, String name) {
this.id = id;
this.name = name;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Employee employee = (Employee) obj;
return Objects.equals(id, employee.id) && Objects.equals(name, employee.name);
}
@Override
public int hashCode() {
return Objects.hash(id, name);
}
@Override
public String toString() {
return "Employee{id='" + id + "', name='" + name + "'}";
}
}
// 错误实现（没有重写hashCode和equals）的BadEmployee类
static class BadEmployee {
private String id;
private String name;
public BadEmployee(String id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "BadEmployee{id='" + id + "', name='" + name + "'}";
}
}
// 好的hashCode实现
static class GoodHashCode {
private int value;
public GoodHashCode(int value) {
this.value = value;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
GoodHashCode that = (GoodHashCode) obj;
return value == that.value;
}
@Override
public int hashCode() {
return Objects.hash(value); // 好的分布
}
}
// 坏的hashCode实现
static class BadHashCode {
private int value;
public BadHashCode(int value) {
this.value = value;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
BadHashCode that = (BadHashCode) obj;
return value == that.value;
}
@Override
public int hashCode() {
return 1; // 所有对象返回相同hashCode，导致严重冲突
}
}
// 简单缓存实现
static class SimpleCache<K, V> {
private Map<K, V> cache;
private int maxSize;
public SimpleCache(int maxSize) {
this.maxSize = maxSize;
this.cache = new LinkedHashMap<K, V>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > SimpleCache.this.maxSize;
}
};
}
public V get(K key) {
return cache.get(key);
}
public void put(K key, V value) {
cache.put(key, value);
}
public Map<K, V> getAll() {
return new HashMap<>(cache);
}
}
// 学生类
static class Student {
private String name;
private String grade;
private int score;
public Student(String name, String grade, int score) {
this.name = name;
this.grade = grade;
this.score = score;
}
public String getName() { return name; }
public String getGrade() { return grade; }
public int getScore() { return score; }
}
}
8.2.2 LinkedHashMap详解
import java.util.*;
/**
* LinkedHashMap详细演示
*/
public class LinkedHashMapDemo {
public static void main(String[] args) {
System.out.println("=== LinkedHashMap详细演示 ===");
demonstrateInsertionOrder();
demonstrateAccessOrder();
demonstrateLRUCache();
demonstrateVsHashMap();
demonstrateUseCases();
}
public static void demonstrateInsertionOrder() {
System.out.println("\n--- LinkedHashMap插入顺序 ---");
// 1. 插入顺序LinkedHashMap
Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("First", 1);
linkedHashMap.put("Second", 2);
linkedHashMap.put("Third", 3);
linkedHashMap.put("Fourth", 4);
System.out.println("LinkedHashMap (保持插入顺序): " + linkedHashMap);
// 2. HashMap不保证顺序
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("First", 1);
hashMap.put("Second", 2);
hashMap.put("Third", 3);
hashMap.put("Fourth", 4);
System.out.println("HashMap (不保证顺序): " + hashMap);
// 3. 遍历顺序一致性
System.out.println("\nLinkedHashMap多次遍历:");
for (int i = 1; i <= 3; i++) {
System.out.print("第" + i + "次: ");
for (String key : linkedHashMap.keySet()) {
System.out.print(key + " ");
}
System.out.println();
}
// 4. 更新操作不改变顺序
System.out.println("\n更新操作测试:");
System.out.println("更新前: " + linkedHashMap);
linkedHashMap.put("Second", 20); // 更新现有键
System.out.println("更新Second后: " + linkedHashMap);
System.out.println("注意: 顺序保持不变");
}
public static void demonstrateAccessOrder() {
System.out.println("\n--- LinkedHashMap访问顺序 ---");
// 1. 访问顺序LinkedHashMap
Map<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);
accessOrderMap.put("A", 1);
accessOrderMap.put("B", 2);
accessOrderMap.put("C", 3);
accessOrderMap.put("D", 4);
System.out.println("初始状态: " + accessOrderMap);
// 2. 访问元素改变顺序
System.out.println("\n访问操作:");
accessOrderMap.get("B"); // 访问B
System.out.println("访问B后: " + accessOrderMap);
accessOrderMap.get("A"); // 访问A
System.out.println("访问A后: " + accessOrderMap);
// 3. put操作也算访问
accessOrderMap.put("C", 30); // 更新C
System.out.println("更新C后: " + accessOrderMap);
// 4. 插入顺序vs访问顺序对比
System.out.println("\n插入顺序vs访问顺序对比:");
Map<String, Integer> insertionOrder = new LinkedHashMap<>();
Map<String, Integer> accessOrder = new LinkedHashMap<>(16, 0.75f, true);
// 添加相同数据
String[] keys = {"X", "Y", "Z"};
for (String key : keys) {
insertionOrder.put(key, key.hashCode());
accessOrder.put(key, key.hashCode());
}
// 访问中间元素
insertionOrder.get("Y");
accessOrder.get("Y");
System.out.println("插入顺序Map: " + insertionOrder);
System.out.println("访问顺序Map: " + accessOrder);
}
public static void demonstrateLRUCache() {
System.out.println("\n--- LRU缓存实现 ---");
// 1. 基于LinkedHashMap的LRU缓存
LRUCache<String, String> lruCache = new LRUCache<>(3);
System.out.println("\n1. LRU缓存操作:");
lruCache.put("key1", "value1");
lruCache.put("key2", "value2");
lruCache.put("key3", "value3");
System.out.println("添加3个元素: " + lruCache);
lruCache.get("key1"); // 访问key1，使其成为最近使用
System.out.println("访问key1后: " + lruCache);
lruCache.put("key4", "value4"); // 添加第4个元素，应该淘汰key2
System.out.println("添加key4后: " + lruCache);
// 2. 缓存命中率测试
System.out.println("\n2. 缓存命中率测试:");
LRUCache<Integer, String> cache = new LRUCache<>(5);
// 添加数据
for (int i = 1; i <= 5; i++) {
cache.put(i, "value" + i);
}
// 模拟访问模式
int hits = 0;
int total = 0;
int[] accessPattern = {1, 2, 3, 1, 4, 5, 6, 1, 2, 7, 8, 1};
for (int key : accessPattern) {
total++;
if (cache.get(key) != null) {
hits++;
System.out.println("访问" + key + ": 命中");
} else {
cache.put(key, "value" + key);
System.out.println("访问" + key + ": 未命中，已缓存");
}
System.out.println(" 当前缓存: " + cache);
}
System.out.println("\n缓存统计:");
System.out.println("总访问次数: " + total);
System.out.println("命中次数: " + hits);
System.out.println("命中率: " + (hits * 100.0 / total) + "%");
}
public static void demonstrateVsHashMap() {
System.out.println("\n--- LinkedHashMap vs HashMap 性能对比 ---");
int size = 100000;
// 1. 添加性能
System.out.println("\n1. 添加性能测试:");
Map<Integer, String> linkedHashMap = new LinkedHashMap<>();
long startTime = System.nanoTime();
for (int i = 0; i < size; i++) {
linkedHashMap.put(i, "Value" + i);
}
long linkedHashMapAddTime = System.nanoTime() - startTime;
Map<Integer, String> hashMap = new HashMap<>();
startTime = System.nanoTime();
for (int i = 0; i < size; i++) {
hashMap.put(i, "Value" + i);
}
long hashMapAddTime = System.nanoTime() - startTime;
System.out.println("LinkedHashMap添加耗时: " + linkedHashMapAddTime / 1000000 + "ms");
System.out.println("HashMap添加耗时: " + hashMapAddTime / 1000000 + "ms");
// 2. 遍历性能
System.out.println("\n2. 遍历性能测试:");
startTime = System.nanoTime();
for (Map.Entry<Integer, String> entry : linkedHashMap.entrySet()) {
// 空操作，只测试遍历
}
long linkedHashMapIterateTime = System.nanoTime() - startTime;
startTime = System.nanoTime();
for (Map.Entry<Integer, String> entry : hashMap.entrySet()) {
// 空操作，只测试遍历
}
long hashMapIterateTime = System.nanoTime() - startTime;
System.out.println("LinkedHashMap遍历耗时: " + linkedHashMapIterateTime / 1000000 + "ms");
System.out.println("HashMap遍历耗时: " + hashMapIterateTime / 1000000 + "ms");
System.out.println("\n性能总结:");
System.out.println("- LinkedHashMap比HashMap稍慢（维护链表开销）");
System.out.println("- 遍历性能LinkedHashMap通常更好（链表顺序访问）");
System.out.println("- 内存使用LinkedHashMap更高（额外的链表指针）");
}
public static void demonstrateUseCases() {
System.out.println("\n--- LinkedHashMap使用场景 ---");
// 1. 保持插入顺序的配置
System.out.println("\n1. 配置文件处理:");
Map<String, String> config = new LinkedHashMap<>();
config.put("database.driver", "com.mysql.cj.jdbc.Driver");
config.put("database.url", "jdbc:mysql://localhost:3306/mydb");
config.put("database.username", "admin");
config.put("database.password", "password");
config.put("server.port", "8080");
config.put("logging.level", "INFO");
System.out.println("配置项（保持定义顺序）:");
config.forEach((key, value) ->
System.out.println(" " + key + " = " + value));
// 2. 用户操作历史
System.out.println("\n2. 用户操作历史:");
UserActionHistory actionHistory = new UserActionHistory(5);
actionHistory.recordAction("登录");
actionHistory.recordAction("查看首页");
actionHistory.recordAction("搜索商品");
actionHistory.recordAction("查看商品详情");
actionHistory.recordAction("添加到购物车");
actionHistory.recordAction("查看购物车"); // 超出容量，删除最旧的
System.out.println("用户操作历史: " + actionHistory.getHistory());
// 3. 最近访问的文件
System.out.println("\n3. 最近访问文件管理:");
RecentFilesManager recentFiles = new RecentFilesManager(4);
recentFiles.openFile("document1.txt");
recentFiles.openFile("presentation.pptx");
recentFiles.openFile("spreadsheet.xlsx");
recentFiles.openFile("document1.txt"); // 重复访问
recentFiles.openFile("image.png");
recentFiles.openFile("video.mp4");
System.out.println("最近访问的文件: " + recentFiles.getRecentFiles());
// 4. 有序的JSON对象模拟
System.out.println("\n4. 有序JSON对象模拟:");
Map<String, Object> jsonObject = new LinkedHashMap<>();
jsonObject.put("id", 1001);
jsonObject.put("name", "张三");
jsonObject.put("email", "zhangsan@example.com");
jsonObject.put("age", 25);
jsonObject.put("department", "技术部");
jsonObject.put("salary", 8000.0);
System.out.println("员工信息JSON（保持字段顺序）:");
System.out.println("{");
jsonObject.forEach((key, value) -> {
String valueStr = value instanceof String ? "\"" + value + "\"" : value.toString();
System.out.println(" \"" + key + "\": " + valueStr + ",");
});
System.out.println("}");
}
// LRU缓存实现
static class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int capacity;
public LRUCache(int capacity) {
super(16, 0.75f, true); // 启用访问顺序
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
boolean first = true;
for (Map.Entry<K, V> entry : entrySet()) {
if (!first) sb.append(", ");
sb.append(entry.getKey()).append("=").append(entry.getValue());
first = false;
}
sb.append("]");
return sb.toString();
}
}
// 用户操作历史
static class UserActionHistory {
private Map<String, Long> actions;
private int maxSize;
public UserActionHistory(int maxSize) {
this.maxSize = maxSize;
this.actions = new LinkedHashMap<String, Long>() {
@Override
protected boolean removeEldestEntry(Map.Entry<String, Long> eldest) {
return size() > UserActionHistory.this.maxSize;
}
};
}
public void recordAction(String action) {
actions.put(action, System.currentTimeMillis());
}
public List<String> getHistory() {
return new ArrayList<>(actions.keySet());
}
}
// 最近访问文件管理器
static class RecentFilesManager {
private Map<String, Long> recentFiles;
private int maxFiles;
public RecentFilesManager(int maxFiles) {
this.maxFiles = maxFiles;
this.recentFiles = new LinkedHashMap<String, Long>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, Long> eldest) {
return size() > RecentFilesManager.this.maxFiles;
}
};
}
public void openFile(String filename) {
recentFiles.put(filename, System.currentTimeMillis());
}
public List<String> getRecentFiles() {
List<String> files = new ArrayList<>(recentFiles.keySet());
Collections.reverse(files); // 最近访问的在前
return files;
}
}
}
8.2.3 TreeMap详解
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
/**
* TreeMap详细演示
*/
public class TreeMapDemo {
public static void main(String[] args) {
System.out.println("=== TreeMap详细演示 ===");
demonstrateBasicOperations();
demonstrateSortingAndComparison();
demonstrateNavigationMethods();
demonstrateSubMapOperations();
demonstratePerformance();
demonstrateUseCases();
}
public static void demonstrateBasicOperations() {
System.out.println("\n--- TreeMap基本操作 ---");
// 1. 创建TreeMap（自然排序）
TreeMap<String, Integer> scores = new TreeMap<>();
// 2. 添加键值对（自动按键排序）
scores.put("张三", 85);
scores.put("李四", 92);
scores.put("王五", 78);
scores.put("赵六", 88);
scores.put("钱七", 95);
System.out.println("学生成绩（按姓名排序）: " + scores);
// 3. 基本操作
System.out.println("\n基本操作:");
System.out.println("张三的成绩: " + scores.get("张三"));
System.out.println("包含李四: " + scores.containsKey("李四"));
System.out.println("包含成绩90: " + scores.containsValue(90));
System.out.println("Map大小: " + scores.size());
// 4. 遍历（按键的排序顺序）
System.out.println("\n按键排序遍历:");
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
System.out.println(" " + entry.getKey() + ": " + entry.getValue());
}
// 5. 数字键的TreeMap
TreeMap<Integer, String> numberMap = new TreeMap<>();
numberMap.put(3, "Three");
numberMap.put(1, "One");
numberMap.put(4, "Four");
numberMap.put(2, "Two");
System.out.println("\n数字键TreeMap: " + numberMap);
}
public static void demonstrateSortingAndComparison() {
System.out.println("\n--- TreeMap排序和比较器 ---");
// 1. 自然排序
System.out.println("\n1. 自然排序（升序）:");
TreeMap<Integer, String> naturalOrder = new TreeMap<>();
int[] keys = {5, 2, 8, 1, 9, 3};
for (int key : keys) {
naturalOrder.put(key, "Value" + key);
}
System.out.println("插入顺序: " + Arrays.toString(keys));
System.out.println("自然排序: " + naturalOrder);
// 2. 自定义比较器（降序）
System.out.println("\n2. 自定义比较器（降序）:");
TreeMap<Integer, String> reverseOrder = new TreeMap<>(Collections.reverseOrder());
for (int key : keys) {
reverseOrder.put(key, "Value" + key);
}
System.out.println("降序排序: " + reverseOrder);
// 3. 复杂对象作为键
System.out.println("\n3. 复杂对象作为键:");
// 按学生年龄排序
TreeMap<Student, String> studentsByAge = new TreeMap<>(Comparator.comparingInt(Student::getAge));
studentsByAge.put(new Student("张三", 20, 85), "计算机系");
studentsByAge.put(new Student("李四", 19, 92), "数学系");
studentsByAge.put(new Student("王五", 21, 78), "物理系");
studentsByAge.put(new Student("赵六", 19, 88), "化学系");
System.out.println("按年龄排序的学生:");
studentsByAge.forEach((student, department) ->
System.out.println(" " + student + " -> " + department));
// 4. 多级排序
System.out.println("\n4. 多级排序（年龄+成绩）:");
TreeMap<Student, String> multiLevelSort = new TreeMap<>(
Comparator.comparingInt(Student::getAge)
.thenComparingInt(Student::getScore)
);
multiLevelSort.put(new Student("张三", 20, 85), "计算机系");
multiLevelSort.put(new Student("李四", 19, 92), "数学系");
multiLevelSort.put(new Student("王五", 21, 78), "物理系");
multiLevelSort.put(new Student("赵六", 19, 88), "化学系");
multiLevelSort.put(new Student("钱七", 19, 95), "英语系");
multiLevelSort.forEach((student, department) ->
System.out.println(" " + student + " -> " + department));
}
public static void demonstrateNavigationMethods() {
System.out.println("\n--- TreeMap导航方法 ---");
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "Ten");
map.put(20, "Twenty");
map.put(30, "Thirty");
map.put(40, "Forty");
map.put(50, "Fifty");
System.out.println("TreeMap: " + map);
// 1. 边界元素
System.out.println("\n1. 边界元素:");
System.out.println("第一个键值对: " + map.firstEntry());
System.out.println("最后一个键值对: " + map.lastEntry());
System.out.println("第一个键: " + map.firstKey());
System.out.println("最后一个键: " + map.lastKey());
// 2. 查找相关元素
System.out.println("\n2. 查找相关元素:");
int target = 25;
System.out.println("目标键: " + target);
System.out.println("小于" + target + "的最大键: " + map.lowerKey(target));
System.out.println("小于等于" + target + "的最大键: " + map.floorKey(target));
System.out.println("大于等于" + target + "的最小键: " + map.ceilingKey(target));
System.out.println("大于" + target + "的最小键: " + map.higherKey(target));
// 对应的Entry方法
System.out.println("\n对应的Entry方法:");
System.out.println("小于" + target + "的最大Entry: " + map.lowerEntry(target));
System.out.println("小于等于" + target + "的最大Entry: " + map.floorEntry(target));
System.out.println("大于等于" + target + "的最小Entry: " + map.ceilingEntry(target));
System.out.println("大于" + target + "的最小Entry: " + map.higherEntry(target));
// 3. 删除边界元素
System.out.println("\n3. 删除边界元素:");
TreeMap<Integer, String> copy = new TreeMap<>(map);
System.out.println("删除前: " + copy);
Map.Entry<Integer, String> first = copy.pollFirstEntry();
Map.Entry<Integer, String> last = copy.pollLastEntry();
System.out.println("删除的第一个Entry: " + first);
System.out.println("删除的最后一个Entry: " + last);
System.out.println("删除后: " + copy);
// 4. 降序视图
System.out.println("\n4. 降序视图:");
NavigableMap<Integer, String> descendingMap = map.descendingMap();
System.out.println("原Map: " + map);
System.out.println("降序视图: " + descendingMap);
// 修改降序视图会影响原Map
descendingMap.put(60, "Sixty");
System.out.println("在降序视图中添加60:");
System.out.println("原Map: " + map);
System.out.println("降序视图: " + descendingMap);
}
public static void demonstrateSubMapOperations() {
System.out.println("\n--- TreeMap子Map操作 ---");
TreeMap<Integer, String> map = new TreeMap<>();
for (int i = 1; i <= 20; i++) {
map.put(i, "Value" + i);
}
System.out.println("完整Map: " + map);
// 1. headMap - 小于指定键的子Map
System.out.println("\n1. headMap操作:");
SortedMap<Integer, String> headMap = map.headMap(10);
System.out.println("小于10的键值对: " + headMap);
NavigableMap<Integer, String> headMapInclusive = map.headMap(10, true);
System.out.println("小于等于10的键值对: " + headMapInclusive);
// 2. tailMap - 大于等于指定键的子Map
System.out.println("\n2. tailMap操作:");
SortedMap<Integer, String> tailMap = map.tailMap(15);
System.out.println("大于等于15的键值对: " + tailMap);
NavigableMap<Integer, String> tailMapExclusive = map.tailMap(15, false);
System.out.println("大于15的键值对: " + tailMapExclusive);
// 3. subMap - 指定范围的子Map
System.out.println("\n3. subMap操作:");
SortedMap<Integer, String> subMap = map.subMap(5, 15);
System.out.println("[5, 15)范围的键值对: " + subMap);
NavigableMap<Integer, String> subMapInclusive = map.subMap(5, true, 15, true);
System.out.println("[5, 15]范围的键值对: " + subMapInclusive);
// 4. 子Map的动态特性
System.out.println("\n4. 子Map的动态特性:");
System.out.println("原始子Map[5, 15): " + subMap);
map.put(8, "NewValue8"); // 在范围内修改
map.put(25, "Value25"); // 在范围外添加
System.out.println("修改原Map后的子Map: " + subMap);
subMap.put(12, "ModifiedValue12"); // 从子Map修改
System.out.println("从子Map修改后的原Map: " + map);
}
public static void demonstratePerformance() {
System.out.println("\n--- TreeMap性能特征 ---");
int size = 100000;
TreeMap<Integer, String> treeMap = new TreeMap<>();
// 1. 添加性能
long startTime = System.nanoTime();
for (int i = 0; i < size; i++) {
treeMap.put(ThreadLocalRandom.current().nextInt(size * 2), "Value" + i);
}
long addTime = System.nanoTime() - startTime;
// 2. 查找性能
startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
treeMap.get(ThreadLocalRandom.current().nextInt(size * 2));
}
long searchTime = System.nanoTime() - startTime;
// 3. 删除性能
startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
treeMap.remove(ThreadLocalRandom.current().nextInt(size * 2));
}
long removeTime = System.nanoTime() - startTime;
// 4. 遍历性能
startTime = System.nanoTime();
for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
// 空操作，只测试遍历
}
long iterateTime = System.nanoTime() - startTime;
System.out.println("性能测试结果:");
System.out.println("添加" + size + "个元素耗时: " + addTime / 1000000 + "ms");
System.out.println("查找10000次耗时: " + searchTime / 1000000 + "ms");
System.out.println("删除1000个元素耗时: " + removeTime / 1000000 + "ms");
System.out.println("遍历" + treeMap.size() + "个元素耗时: " + iterateTime / 1000000 + "ms");
System.out.println("\nTreeMap特点:");
System.out.println("- 基于红黑树实现");
System.out.println("- 时间复杂度: O(log n)");
System.out.println("- 自动按键排序");
System.out.println("- 不允许null键（但允许null值）");
System.out.println("- 非线程安全");
}
public static void demonstrateUseCases() {
System.out.println("\n--- TreeMap使用场景 ---");
// 1. 排序的统计数据
System.out.println("\n1. 成绩分布统计:");
TreeMap<Integer, Integer> scoreDistribution = new TreeMap<>();
// 模拟学生成绩
int[] scores = {85, 92, 78, 88, 95, 82, 90, 76, 89, 94, 87, 91, 83, 79, 96};
// 按分数段统计
for (int score : scores) {
int range = (score / 10) * 10; // 分数段：70-79, 80-89, 90-99
scoreDistribution.merge(range, 1, Integer::sum);
}
System.out.println("成绩分布（按分数段排序）:");
scoreDistribution.forEach((range, count) ->
System.out.println(" " + range + "-" + (range + 9) + "分: " + count + "人"));
// 2. 时间序列数据
System.out.println("\n2. 时间序列数据管理:");
TreeMap<Long, Double> temperatureData = new TreeMap<>();
// 模拟温度数据（时间戳 -> 温度）
long baseTime = System.currentTimeMillis();
Random random = new Random();
for (int i = 0; i < 10; i++) {
long timestamp = baseTime + i * 3600000; // 每小时一个数据点
double temperature = 20 + random.nextGaussian() * 5; // 平均20度，标准差5度
temperatureData.put(timestamp, temperature);
}
System.out.println("温度数据（按时间排序）:");
temperatureData.forEach((timestamp, temp) -> {
Date date = new Date(timestamp);
System.out.printf(" %tH:%tM - %.1f°C%n", date, date, temp);
});
// 3. 范围查询应用
System.out.println("\n3. 价格范围查询:");
TreeMap<Double, List<String>> productsByPrice = new TreeMap<>();
// 添加商品数据
addProduct(productsByPrice, "笔记本电脑", 5999.0);
addProduct(productsByPrice, "手机", 2999.0);
addProduct(productsByPrice, "平板电脑", 1999.0);
addProduct(productsByPrice, "耳机", 299.0);
addProduct(productsByPrice, "键盘", 199.0);
addProduct(productsByPrice, "鼠标", 99.0);
addProduct(productsByPrice, "显示器", 1299.0);
System.out.println("所有商品（按价格排序）:");
productsByPrice.forEach((price, products) ->
System.out.println(" " + price + "元: " + products));
// 价格范围查询
double minPrice = 200.0;
double maxPrice = 3000.0;
NavigableMap<Double, List<String>> priceRange =
productsByPrice.subMap(minPrice, true, maxPrice, true);
System.out.println("\n价格在" + minPrice + "-" + maxPrice + "元的商品:");
priceRange.forEach((price, products) ->
System.out.println(" " + price + "元: " + products));
// 4. 字典/索引应用
System.out.println("\n4. 单词索引:");
TreeMap<String, Set<Integer>> wordIndex = new TreeMap<>();
String[] sentences = {
"Java is a programming language",
"Programming with Java is fun",
"Java programming requires practice"
};
// 构建单词索引
for (int i = 0; i < sentences.length; i++) {
String[] words = sentences[i].toLowerCase().split(" ");
for (String word : words) {
wordIndex.computeIfAbsent(word, k -> new TreeSet<>()).add(i + 1);
}
}
System.out.println("单词索引（按字母顺序）:");
wordIndex.forEach((word, lineNumbers) ->
System.out.println(" " + word + ": 出现在第" + lineNumbers + "句"));
}
private static void addProduct(TreeMap<Double, List<String>> map, String product, double price) {
map.computeIfAbsent(price, k -> new ArrayList<>()).add(product);
}
// 学生类
static class Student {
private String name;
private int age;
private int score;
public Student(String name, int age, int score) {
this.name = name;
this.age = age;
this.score = score;
}
public String getName() { return name; }
public int getAge() { return age; }
public int getScore() { return score; }
@Override
public String toString() {
return String.format("Student{name='%s', age=%d, score=%d}", name, age, score);
}
}
}
8.3 集合框架总结
8.3.1 Set接口实现类对比
| 特性 | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| 底层实现 | 哈希表 | 哈希表+双向链表 | 红黑树 |
| 时间复杂度 | O(1) | O(1) | O(log n) |
| 元素顺序 | 无序 | 插入顺序 | 自然排序/自定义排序 |
| null值 | 允许 | 允许 | 不允许 |
| 线程安全 | 否 | 否 | 否 |
| 内存开销 | 最小 | 中等 | 最大 |
| 适用场景 | 快速查找、去重 | 保持插入顺序的去重 | 需要排序的集合 |
8.3.2 Map接口实现类对比
| 特性 | HashMap | LinkedHashMap | TreeMap |
|---|---|---|---|
| 底层实现 | 哈希表 | 哈希表+双向链表 | 红黑树 |
| 时间复杂度 | O(1) | O(1) | O(log n) |
| 键的顺序 | 无序 | 插入顺序/访问顺序 | 自然排序/自定义排序 |
| null键/值 | 允许 | 允许 | 键不允许/值允许 |
| 线程安全 | 否 | 否 | 否 |
| 内存开销 | 最小 | 中等 | 最大 |
| 适用场景 | 通用键值存储 | LRU缓存、保持顺序 | 需要排序的键值对 |
8.3.3 选择指南
选择Set实现类：
- 需要快速查找和去重：选择 HashSet
- 需要保持插入顺序：选择 LinkedHashSet
- 需要排序功能：选择 TreeSet
选择Map实现类：
- 通用键值存储：选择 HashMap
- 需要保持插入顺序或实现LRU缓存：选择 LinkedHashMap
- 需要按键排序或范围查询：选择 TreeMap
本章小结
本章详细介绍了Java集合框架中的Set和Map接口及其主要实现类：
Set接口实现类：
- HashSet：基于哈希表，提供O(1)的性能，适合快速查找和去重
- LinkedHashSet：在HashSet基础上维护插入顺序
- TreeSet：基于红黑树，自动排序，提供丰富的导航方法
Map接口实现类：
- HashMap：基于哈希表，提供O(1)的性能，是最常用的Map实现
- LinkedHashMap：在HashMap基础上维护插入顺序或访问顺序，适合实现LRU缓存
- TreeMap：基于红黑树，按键自动排序，支持范围查询
重要概念：
- hashCode和equals方法的正确实现对HashMap和HashSet的性能至关重要
- TreeSet和TreeMap要求元素实现Comparable接口或提供Comparator
- LinkedHashSet和LinkedHashMap通过额外的链表维护元素顺序
性能特征：
- 哈希表实现：平均O(1)，最坏O(n)
- 红黑树实现：O(log n)
- 链表维护顺序：轻微的性能开销，但遍历性能更好
下一章预告
下一章我们将学习Java的输入输出（I/O）系统，包括： - 文件操作 - 字节流和字符流 - 缓冲流 - 对象序列化 - NIO（New I/O）
练习题
基础练习：
- 实现一个学生管理系统，使用不同的Set和Map实现类存储学生信息
- 比较HashSet、LinkedHashSet和TreeSet在相同数据下的表现
进阶练习：
- 实现一个基于LinkedHashMap的LRU缓存
- 使用TreeMap实现一个简单的时间序列数据库
综合练习：
- 设计一个单词频率统计程序，要求按频率排序显示结果
- 实现一个简单的倒排索引，支持多关键词搜索
