数据结构第34节 性能优化 选择合适的数据结构

选择合适的数据结构对于优化 Java 应用程序的性能至关重要。下面我将通过几个具体的 Java 代码示例来说明如何根据不同的需求选择合适的数据结构。

示例 1: 频繁插入和删除操作

场景描述:

假设你需要实现一个消息队列，其中消息会被频繁地添加和移除。

数据结构选择:

在这种情况下，LinkedList 是一个很好的选择，因为它支持 O(1) 时间复杂度的插入和删除操作。

代码示例:

import java.util.LinkedList;public class MessageQueue {private LinkedList<String> queue = new LinkedList<>();public void enqueue(String message) {// 在队列尾部添加消息queue.addLast(message);}public String dequeue() {// 移除并返回队列头部的消息return queue.poll();}public int size() {// 返回队列中的消息数量return queue.size();}
}

示例 2: 快速查找和更新操作

场景描述:

假设你需要实现一个电话簿，用户可以通过姓名快速查找电话号码，并且能够更新电话号码。

数据结构选择:

在这种情况下，HashMap 是最佳选择，因为它提供平均 O(1) 时间复杂度的查找、插入和删除操作。

代码示例:

import java.util.HashMap;public class PhoneBook {private HashMap<String, String> phoneNumbers = new HashMap<>();public void addOrUpdateContact(String name, String phoneNumber) {// 添加或更新联系人电话phoneNumbers.put(name, phoneNumber);}public String getPhoneNumber(String name) {// 根据姓名查找电话号码return phoneNumbers.get(name);}public boolean removeContact(String name) {// 删除联系人return phoneNumbers.remove(name) != null;}
}

示例 3: 需要排序的数据集合

场景描述:

假设你需要实现一个任务列表，其中的任务按照优先级排序。

数据结构选择:

在这种情况下，TreeSet 或 PriorityQueue 可以用来自动维持数据的排序状态。

代码示例:

import java.util.PriorityQueue;
import java.util.Comparator;class Task implements Comparable<Task> {private int priority;private String description;public Task(int priority, String description) {this.priority = priority;this.description = description;}@Overridepublic int compareTo(Task other) {return Integer.compare(this.priority, other.priority);}@Overridepublic String toString() {return "Task{" +"priority=" + priority +", description='" + description + '\'' +'}';}
}public class TaskList {private PriorityQueue<Task> tasks = new PriorityQueue<>();public void addTask(Task task) {// 添加任务tasks.add(task);}public Task getNextTask() {// 获取并移除优先级最高的任务return tasks.poll();}public void printTasks() {// 打印所有任务while (!tasks.isEmpty()) {System.out.println(tasks.poll());}}
}

通过这些示例，你可以看到，不同的数据结构适用于不同类型的业务需求。选择合适的数据结构不仅可以简化代码，还可以显著提升应用程序的性能。

当然，我们可以继续深入每个示例，添加更多的功能和细节，以便更好地理解如何在实际应用中使用这些数据结构。让我们扩展之前的例子，包括一些额外的功能和更详细的代码：

示例 1: 频繁插入和删除操作 - 扩展版

我们将添加一个方法用于查看队列中的所有消息，并添加一个方法用于清空队列。

import java.util.LinkedList;public class MessageQueue {private LinkedList<String> queue = new LinkedList<>();public void enqueue(String message) {queue.addLast(message);}public String dequeue() {return queue.poll();}public int size() {return queue.size();}public void clear() {queue.clear();}public String[] getAllMessages() {String[] messages = new String[queue.size()];for (int i = 0; i < messages.length; i++) {messages[i] = queue.get(i);}return messages;}
}

示例 2: 快速查找和更新操作 - 扩展版

我们将添加一个方法用于列出所有联系人，并添加一个方法用于查找是否存在某个联系人。

import java.util.HashMap;public class PhoneBook {private HashMap<String, String> phoneNumbers = new HashMap<>();public void addOrUpdateContact(String name, String phoneNumber) {phoneNumbers.put(name, phoneNumber);}public String getPhoneNumber(String name) {return phoneNumbers.get(name);}public boolean removeContact(String name) {return phoneNumbers.remove(name) != null;}public boolean containsContact(String name) {return phoneNumbers.containsKey(name);}public String[] listContacts() {return phoneNumbers.keySet().toArray(new String[0]);}
}

示例 3: 需要排序的数据集合 - 扩展版

我们将添加一个方法用于添加多个任务，以及一个方法用于获取队列中的所有任务，同时保持优先级排序。

import java.util.PriorityQueue;
import java.util.Comparator;class Task implements Comparable<Task> {private int priority;private String description;public Task(int priority, String description) {this.priority = priority;this.description = description;}@Overridepublic int compareTo(Task other) {return Integer.compare(this.priority, other.priority);}@Overridepublic String toString() {return "Task{" +"priority=" + priority +", description='" + description + '\'' +'}';}
}public class TaskList {private PriorityQueue<Task> tasks = new PriorityQueue<>();public void addTask(Task task) {tasks.add(task);}public void addTasks(Task... tasks) {for (Task task : tasks) {addTask(task);}}public Task getNextTask() {return tasks.poll();}public void printTasks() {while (!tasks.isEmpty()) {System.out.println(tasks.poll());}}public Task[] getAllTasks() {Task[] allTasks = new Task[tasks.size()];for (int i = 0; i < allTasks.length; i++) {allTasks[i] = getNextTask();}return allTasks;}
}

请注意，getAllTasks() 方法将清空任务列表，因为每次调用 getNextTask() 都会移除队列中的一个任务。如果你希望保留队列中的任务，你可能需要使用不同的方法，例如创建一个副本或者使用迭代器来遍历队列而不移除元素。

针对之前提供的代码示例，我们可以进一步完善，确保代码的健壮性和实用性。以下是对每个示例的改进：

示例 1: 频繁插入和删除操作 - 最终版

我们增加错误处理和同步机制以确保线程安全。

import java.util.LinkedList;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;public class MessageQueue {private final LinkedList<String> queue = new LinkedList<>();private final Lock lock = new ReentrantLock();public void enqueue(String message) {lock.lock();try {queue.addLast(message);} finally {lock.unlock();}}public String dequeue() {lock.lock();try {return queue.poll();} finally {lock.unlock();}}public int size() {lock.lock();try {return queue.size();} finally {lock.unlock();}}public void clear() {lock.lock();try {queue.clear();} finally {lock.unlock();}}public String[] getAllMessages() {lock.lock();try {return queue.toArray(new String[0]);} finally {lock.unlock();}}
}

示例 2: 快速查找和更新操作 - 最终版

我们同样增加线程安全机制，并确保方法的健壮性。

import java.util.concurrent.ConcurrentHashMap;public class PhoneBook {private final ConcurrentHashMap<String, String> phoneNumbers = new ConcurrentHashMap<>();public void addOrUpdateContact(String name, String phoneNumber) {phoneNumbers.put(name, phoneNumber);}public String getPhoneNumber(String name) {return phoneNumbers.get(name);}public boolean removeContact(String name) {return phoneNumbers.remove(name) != null;}public boolean containsContact(String name) {return phoneNumbers.containsKey(name);}public String[] listContacts() {return phoneNumbers.keySet().toArray(new String[0]);}
}

示例 3: 需要排序的数据集合 - 最终版

我们确保getAllTasks()不会改变原始任务队列的状态，并增加线程安全措施。

import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.List;
import java.util.Collections;class Task implements Comparable<Task> {private int priority;private String description;public Task(int priority, String description) {this.priority = priority;this.description = description;}@Overridepublic int compareTo(Task other) {return Integer.compare(this.priority, other.priority);}@Overridepublic String toString() {return "Task{" +"priority=" + priority +", description='" + description + '\'' +'}';}
}public class TaskList {private final PriorityQueue<Task> tasks = new PriorityQueue<>();private final List<Task> tasksCopy = Collections.synchronizedList(new CopyOnWriteArrayList<>());public void addTask(Task task) {tasks.add(task);tasksCopy.add(task);}public void addTasks(Task... tasks) {for (Task task : tasks) {addTask(task);}}public Task getNextTask() {return tasks.poll();}public void printTasks() {synchronized (tasksCopy) {for (Task task : tasksCopy) {System.out.println(task);}}}public Task[] getAllTasks() {synchronized (tasksCopy) {return tasksCopy.toArray(new Task[0]);}}
}

注意，在TaskList中，getAllTasks()和printTasks()使用了CopyOnWriteArrayList来保存任务的副本，这样在遍历或返回所有任务时不会影响到原始任务队列。同时，使用Collections.synchronizedList来确保线程安全。这种设计确保了在多线程环境下操作数据结构的安全性。