数据结构第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;
}
@Override
public int compareTo(Task other) {
return Integer.compare(this.priority, other.priority);
}
@Override
public 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;
}
@Override
public int compareTo(Task other) {
return Integer.compare(this.priority, other.priority);
}
@Override
public 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;
}
@Override
public int compareTo(Task other) {
return Integer.compare(this.priority, other.priority);
}
@Override
public 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来确保线程安全。这种设计确保了在多线程环境下操作数据结构的安全性。
原文地址：https://blog.csdn.net/hummhumm/article/details/140520350
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！