面试题：Java 中 LinkedHashMap 和 PriorityQueue 的区别是什么？

LinkedHashMap 和 PriorityQueue 是 Java 集合框架中两种不同的数据结构，它们的主要区别在于用途、内部实现和特性：

1. 用途和特性：

`LinkedHashMap`：

用途：
- LinkedHashMap 是一种基于哈希表和链表实现的 Map，用于存储键值对。
- 它保留了插入顺序或访问顺序（可选），因此可以按插入顺序或访问顺序迭代元素。
特性：
- 继承自 HashMap，具有 HashMap 的所有特性（如快速查找、插入和删除）。
- 通过双向链表维护插入顺序或访问顺序。
- 默认按插入顺序排序，但可以通过构造函数指定按访问顺序排序（最近访问的元素会移动到链表末尾）。

`PriorityQueue`：

用途：
- PriorityQueue 是一种基于优先级堆（通常是最小堆或最大堆）实现的队列。
- 用于存储元素，并按照自然顺序或自定义顺序（通过 Comparator）进行排序。
特性：
- 元素按照优先级排序，队头元素总是优先级最高（最小或最大）的元素。
- 不支持随机访问，只能访问队头元素。
- 插入和删除操作的时间复杂度为 O(log n)。

2. 内部实现：

`LinkedHashMap`：

基于哈希表和双向链表实现。
哈希表用于快速查找、插入和删除键值对。
双向链表用于维护插入顺序或访问顺序。

`PriorityQueue`：

基于优先级堆（通常是最小堆或最大堆）实现。
堆是一种完全二叉树，满足堆性质（父节点的值总是小于或大于子节点的值）。
通过数组存储堆结构。

3. 性能特点：

`LinkedHashMap`：

查找： 平均时间复杂度为 O(1)（基于哈希表）。
插入和删除： 平均时间复杂度为 O(1)。
迭代： 按插入顺序或访问顺序迭代，时间复杂度为 O(n)。

`PriorityQueue`：

查找队头元素： 时间复杂度为 O(1)。
插入和删除： 时间复杂度为 O(log n)。
迭代： 不保证顺序，按堆的内部结构迭代。

4. 适用场景：

`LinkedHashMap`：

需要保留插入顺序或访问顺序的场景。
需要快速查找、插入和删除键值对的场景。
例如：实现 LRU（最近最少使用）缓存。

`PriorityQueue`：

需要按优先级处理元素的场景。
需要快速获取优先级最高（最小或最大）元素的场景。
例如：任务调度、Dijkstra 算法中的优先队列。

5. 代码示例：

`LinkedHashMap` 示例：

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        // 按插入顺序排序
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("Apple", 10);
        map.put("Banana", 20);
        map.put("Orange", 30);

        System.out.println(map); // 输出: {Apple=10, Banana=20, Orange=30}

        // 按访问顺序排序
        Map<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);
        accessOrderMap.put("Apple", 10);
        accessOrderMap.put("Banana", 20);
        accessOrderMap.put("Orange", 30);

        accessOrderMap.get("Banana"); // 访问 Banana
        System.out.println(accessOrderMap); // 输出: {Apple=10, Orange=30, Banana=20}
    }
}

`PriorityQueue` 示例：

import java.util.PriorityQueue;
import java.util.Comparator;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 默认最小堆（自然顺序）
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(30);
        minHeap.offer(10);
        minHeap.offer(20);

        System.out.println(minHeap.poll()); // 输出: 10
        System.out.println(minHeap.poll()); // 输出: 20

        // 自定义最大堆（通过 Comparator）
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.offer(30);
        maxHeap.offer(10);
        maxHeap.offer(20);

        System.out.println(maxHeap.poll()); // 输出: 30
        System.out.println(maxHeap.poll()); // 输出: 20
    }
}

总结：

特性	LinkedHashMap	PriorityQueue
用途	存储键值对，保留插入或访问顺序	按优先级存储元素
内部实现	哈希表 + 双向链表	优先级堆（最小堆或最大堆）
查找性能	O(1)	O(1)（仅限队头元素）
插入/删除性能	O(1)	O(log n)
迭代顺序	插入顺序或访问顺序	不保证顺序（按堆结构）
适用场景	需要保留顺序的键值对存储	需要按优先级处理元素的场景