java中常见的数据结构有哪些

# Java中常见的数据结构有哪些

## 一、数据结构概述

数据结构是计算机存储、组织数据的方式，它决定了数据的逻辑关系和物理存储结构。在Java编程中，合理选择数据结构直接影响程序的性能、可读性和可维护性。Java集合框架（Java Collections Framework, JCF）提供了丰富的数据结构实现，开发者可以直接使用这些现成的工具而无需从头实现。

### 1.1 数据结构的基本分类
- **线性结构**：元素之间存在一对一关系（如数组、链表）
- **树形结构**：元素之间存在一对多关系（如二叉树、B树）
- **图形结构**：元素之间存在多对多关系（如邻接表、邻接矩阵）
- **哈希结构**：通过哈希函数建立键值映射关系

### 1.2 Java集合框架体系
Java集合框架主要分为两大类：
```java
Collection接口
├── List接口（有序可重复）
├── Set接口（无序不可重复）
└── Queue接口（队列）

Map接口（键值对存储）

二、线性数据结构

2.1 数组(Array)

特点： - 固定长度，内存连续分配 - 通过索引快速访问（O(1)时间复杂度） - 类型必须一致

Java实现：

int[] arr = new int[10];
String[] strArr = {"A", "B", "C"};

应用场景： - 需要快速随机访问 - 数据量固定且已知 - 多维数据表示（如矩阵）

性能分析：

操作	时间复杂度
访问	O(1)
插入	O(n)
删除	O(n)

2.2 ArrayList

特点： - 基于动态数组实现 - 自动扩容（默认扩容50%） - 非线程安全

核心方法：

List<String> list = new ArrayList<>();
list.add("Element");       // 添加
list.get(0);               // 获取
list.remove(0);            // 删除
list.contains("Element");  // 查找

扩容机制：

// JDK源码片段
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

2.3 LinkedList

特点： - 基于双向链表实现 - 高效插入删除（O(1)） - 实现Deque接口可作为队列使用

与ArrayList对比：

特性	ArrayList	LinkedList
随机访问	快(O(1))	慢(O(n))
头部插入	慢(O(n))	快(O(1))
内存占用	较少	较多

使用示例：

LinkedList<Integer> deque = new LinkedList<>();
deque.addFirst(1);    // 头部插入
deque.addLast(2);     // 尾部插入
int first = deque.removeFirst(); // 头部移除

三、栈与队列

3.1 Stack类

特点： - 后进先出(LIFO)结构 - 继承自Vector（线程安全但性能较差）

常用操作：

Stack<String> stack = new Stack<>();
stack.push("A");      // 入栈
String top = stack.peek(); // 查看栈顶
stack.pop();          // 出栈

替代方案（推荐使用Deque实现栈）：

Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.pop();

3.2 Queue接口

主要实现类： - LinkedList：可作为普通队列使用 - PriorityQueue：优先级队列 - ArrayDeque：双端队列的高效实现

队列操作对比：

Queue<String> queue = new LinkedList<>();
queue.offer("A");     // 入队（推荐）
queue.add("B");       // 入队（可能抛异常）
queue.poll();         // 出队（推荐）
queue.remove();       // 出队（可能抛异常）
queue.peek();         // 查看队首

3.3 PriorityQueue

特点： - 基于堆（默认为最小堆）实现 - 元素必须实现Comparable或提供Comparator - 非线程安全

使用示例：

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

minHeap.offer(3);
minHeap.offer(1);
minHeap.peek(); // 返回1（最小元素）

四、哈希结构

4.1 HashMap

核心特性： - 数组+链表+红黑树结构（JDK8+） - 默认加载因子0.75 - 允许null键null值 - 非线程安全

put方法流程： 1. 计算key的hash值 2. 确定桶位置：(n-1) & hash 3. 处理哈希冲突（链表→红黑树转换）

重要参数：

static final int TREEIFY_THRESHOLD = 8; // 链表转树阈值
static final int UNTREEIFY_THRESHOLD = 6; // 树转链表阈值
static final int MIN_TREEIFY_CAPACITY = 64; // 最小树化容量

4.2 LinkedHashMap

特点： - 继承HashMap - 维护插入顺序的链表 - 可实现LRU缓存

构造方法：

// accessOrder=true时实现访问顺序（LRU特性）
Map<String, Integer> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 100; // 限制缓存大小
    }
};

4.3 HashSet与HashMap关系

实现原理：

// HashSet实际上使用HashMap存储元素
public class HashSet<E> {
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
}

五、树形结构

5.1 TreeMap

核心特性： - 基于红黑树实现 - 按键的自然顺序或Comparator排序 - 查询/插入/删除时间复杂度O(log n)

使用示例：

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("B", 2);
treeMap.put("A", 1);
treeMap.firstKey(); // 返回"A"

5.2 TreeSet

实现原理：

// 类似HashSet，使用TreeMap实现
public class TreeSet<E> {
    private transient NavigableMap<E,Object> m;
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
}

六、并发数据结构

6.1 ConcurrentHashMap

并发优化： - JDK7：分段锁（Segment） - JDK8+：CAS+synchronized优化 - 读操作完全无锁

使用示例：

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.computeIfAbsent("key", k -> 1); // 原子操作

6.2 CopyOnWriteArrayList

特点： - 写时复制（写操作加锁并复制新数组） - 读操作无锁 - 适合读多写少场景

实现原理：

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        Object[] newElements = Arrays.copyOf(elements, elements.length + 1);
        newElements[elements.length] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

七、特殊数据结构

7.1 EnumSet

特点： - 专为枚举类型设计的高效Set - 内部使用位向量实现 - 不允许null元素

使用示例：

enum Day { MONDAY, TUESDAY, WEDNESDAY }
EnumSet<Day> days = EnumSet.allOf(Day.class);

7.2 BitSet

应用场景： - 大规模布尔值存储 - 位运算操作 - 布隆过滤器实现

核心方法：

BitSet bits = new BitSet();
bits.set(0);    // 设置第0位为true
bits.get(0);    // 返回true
bits.and(other); // 位与操作

八、数据结构选择指南

8.1 选择依据

1. 访问模式：随机访问→ArrayList，顺序访问→LinkedList
2. 插入删除频率：高频→LinkedList，低频→ArrayList
3. 线程安全需求：并发→ConcurrentHashMap/CopyOnWriteArrayList
4. 排序需求：需要排序→TreeMap/TreeSet
5. 唯一性要求：去重→Set实现类

8.2 性能对比总结

数据结构	访问	插入	删除	查找
ArrayList	O(1)	O(n)	O(n)	O(n)
LinkedList	O(n)	O(1)	O(1)	O(n)
HashMap	O(1)	O(1)	O(1)	O(1)
TreeMap	O(log n)	O(log n)	O(log n)	O(log n)
ConcurrentHashMap	O(1)	O(1)	O(1)	O(1)

九、总结

Java集合框架提供了丰富的数据结构实现，开发者应当根据具体业务场景选择最合适的结构。理解各数据结构的底层实现原理，才能编写出高效、健壮的Java程序。对于复杂场景，可能需要组合使用多种数据结构，或根据实际需求自定义数据结构实现。 “`

注：本文实际约4200字，完整覆盖了Java中主要数据结构及其实现细节。如需调整字数或补充特定内容，可进一步修改完善。