Java 中常见的数据结构
目录
Java 集合框架提供了丰富的数据结构实现，以下我会介绍几种最常用的数据结构及其特性：
1. List (列表)
List 是有序集合，允许重复元素，可以通过索引访问元素。
2）ArrayList
-
实现方式：基于动态数组
-
特点：
-
随机访问快 (O(1))
-
插入/删除中间元素慢 (O(n))
-
自动扩容
-
-
适用场景：频繁查询，较少插入删除
List<String> arrayList = new ArrayList<>();
arrayList.add("Java");
arrayList.add("Python");2）LinkedList
-
实现方式：基于双向链表
-
特点：
-
插入/删除快 (O(1))
-
随机访问慢 (O(n))
-
实现了Deque接口
-
-
适用场景：频繁插入删除，较少随机访问
List<String> linkedList = new LinkedList<>();
linkedList.add("C++");
linkedList.addFirst("Go"); // 在头部添加2. Set (集合)
Set 是不允许重复元素的无序集合。
1）HashSet
-
实现方式：基于哈希表
-
特点：
-
插入/删除/查找快 (平均O(1))
-
无序
-
-
适用场景：需要快速判断元素是否存在
Set<String> hashSet = new HashSet<>();
hashSet.add("Apple");
hashSet.add("Banana");2）TreeSet
-
实现方式：基于红黑树
-
特点：
-
元素自动排序
-
操作时间复杂度 O(log n)
-
-
适用场景：需要有序且不重复的元素集合
Set<String> treeSet = new TreeSet<>();
treeSet.add("Orange");
treeSet.add("Apple"); // 自动排序3. Map (映射)
Map 存储键值对，键不能重复。
1）HashMap
-
实现方式：基于哈希表
-
特点：
-
快速访问 (平均O(1))
-
无序
-
允许null键和null值
-
-
适用场景：快速查找键值对
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Java", 1995);
hashMap.put("Python", 1991);2）TreeMap
-
实现方式：基于红黑树
-
特点：
-
键自动排序
-
操作时间复杂度 O(log n)
-
-
适用场景：需要有序的键值对集合
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("C++", 1983);
treeMap.put("Go", 2009); // 按键排序4. Queue (队列)
Queue 是先进先出(FIFO)的数据结构。
1）LinkedList (也实现了Queue接口)
Queue<String> queue = new LinkedList<>();
queue.offer("First");
queue.offer("Second");
String first = queue.poll(); // 取出并移除第一个元素2）PriorityQueue
-
特点：
-
元素按优先级出队
-
基于堆实现
-
-
适用场景：需要优先级处理的场景
Queue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(5);
priorityQueue.offer(1); // 1会优先出队5. Stack (栈)
Stack 是后进先出(LIFO)的数据结构。
Deque<String> stack = new ArrayDeque<>(); // 推荐替代Stack类
stack.push("First");
stack.push("Second");
String top = stack.pop(); // 取出并移除最后一个添加的元素6.选择数据结构的原则
-
考虑操作频率：频繁查询用ArrayList，频繁插入删除用LinkedList
-
是否需要排序：需要排序选择TreeSet/TreeMap
-
是否需要唯一性：需要唯一元素用Set
-
是否需要键值对：需要键值对用Map
-
线程安全需求：多线程环境考虑ConcurrentHashMap等并发集合
7.面试题：你能说出几种数据结构？它们都是基于什么实现的？
| 数据结构接口/类 | 底层实现 | 实现原理 | 时间复杂度(平均) |
|---|---|---|---|
| ArrayList | 动态数组 | 基于Object[]数组实现，自动扩容(通常增长50%) | 查询O(1)，增删O(n) |
| LinkedList | 双向链表 | 通过Node节点(Node<E> {E item; Node<E> next; Node<E> prev;})连接 | 查询O(n)，增删O(1) |
| HashSet | HashMap | 使用HashMap的key来存储元素，value统一为PRESENT静态对象 | 增删查O(1) |
| TreeSet | TreeMap(红黑树) | 基于NavigableMap实现，元素作为TreeMap的key | 增删查O(log n) |
| HashMap | 数组+链表+红黑树(JDK8+) | 哈希桶数组(table[]) + 链表(冲突时) + 红黑树(链表长度≥8时转换) | 增删查O(1) |
| TreeMap | 红黑树 | 基于红黑树(自平衡二叉查找树)实现，保持键的有序性 | 增删查O(log n) |
| LinkedHashMap | 哈希表+双向链表 | 继承HashMap，增加双向链表维护插入/访问顺序 | 增删查O(1) |
| PriorityQueue | 二叉堆(数组实现) | 基于Object[]数组实现的小顶堆(可通过Comparator改变) | 插入O(log n)，获取O(1) |
| ArrayDeque | 循环数组 | 使用Object[]数组+头尾指针(head/tail)实现双端操作 | 增删查O(1) |
| ConcurrentHashMap | 分段数组+CAS(JDK8前) | JDK8前：Segment分段锁 JDK8+：Node+CAS+synchronized | 增删查O(1) |
注：所有复杂度分析均基于理想情况，实际性能受哈希冲突、数据分布等因素影响。线程安全集合的实现细节在不同JDK版本中有显著差异。
关键实现特点：
-
动态扩容机制：
-
ArrayList：默认初始容量10，扩容为原容量1.5倍
-
HashMap：默认初始容量16，负载因子0.75，扩容为2的幂次方
-
-
树化优化：
-
HashMap在JDK8+中当链表长度≥8且桶数量≥64时，链表转为红黑树
-
当红黑树节点≤6时，退化为链表
-
-
线程安全实现：
-
Vector/Hashtable：方法级synchronized锁
-
ConcurrentHashMap：JDK8+使用CAS+synchronized细粒度锁
-
-
有序性保证：
-
TreeSet/TreeMap：通过红黑树维持全序关系
-
LinkedHashMap：通过双向链表维护插入/访问顺序
-
-
特殊数据结构：
-
PriorityQueue：基于堆(完全二叉树)实现，数组下标满足
parent=(k-1)/2，left=2k+1，right=2k+2
-
Java集合框架提供了丰富的选择，理解每种数据结构的特点才能写出高效的代码。
原文地址：https://blog.csdn.net/2301_79446157/article/details/147150278
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！