Java 中常见的数据结构

目录

1. List (列表)

2）ArrayList

2）LinkedList

2. Set (集合)

1）HashSet

2）TreeSet

3. Map (映射)

1）HashMap

2）TreeMap

4. Queue (队列)

1）LinkedList (也实现了Queue接口)

2）PriorityQueue

5. Stack (栈)

6.选择数据结构的原则

7.面试题：你能说出几种数据结构？它们都是基于什么实现的？

关键实现特点：

---

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.选择数据结构的原则

1. 考虑操作频率：频繁查询用ArrayList，频繁插入删除用LinkedList

2. 是否需要排序：需要排序选择TreeSet/TreeMap

3. 是否需要唯一性：需要唯一元素用Set

4. 是否需要键值对：需要键值对用Map

5. 线程安全需求：多线程环境考虑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版本中有显著差异。 

关键实现特点：

1. 动态扩容机制：

   • ArrayList：默认初始容量10，扩容为原容量1.5倍

   • HashMap：默认初始容量16，负载因子0.75，扩容为2的幂次方

2. 树化优化：

   • HashMap在JDK8+中当链表长度≥8且桶数量≥64时，链表转为红黑树

   • 当红黑树节点≤6时，退化为链表

3. 线程安全实现：

   • Vector/Hashtable：方法级synchronized锁

   • ConcurrentHashMap：JDK8+使用CAS+synchronized细粒度锁

4. 有序性保证：

   • TreeSet/TreeMap：通过红黑树维持全序关系

   • LinkedHashMap：通过双向链表维护插入/访问顺序

5. 特殊数据结构：

   • PriorityQueue：基于堆(完全二叉树)实现，数组下标满足parent=(k-1)/2，left=2k+1，right=2k+2

 Java集合框架提供了丰富的选择，理解每种数据结构的特点才能写出高效的代码。