java的数据结构有什么

java的数据结构有什么|全面解析Java核心数据结构体系

深入解析Java中各类数据结构的定义、实现原理、适用场景与性能对比。涵盖数组、链表、栈、队列、树、图、哈希表等核心结构,附真实代码示例、时间复杂度分析及开发实践建议,助您构建扎实的数据结构认知体系。

① 概览:Java数据结构全景图谱

在Java语言体系中,java的数据结构有什么是每位开发者必须深入理解的核心基础。数据结构作为程序设计的基石,直接影响算法效率、内存使用及系统可维护性。Java通过其标准库(JDK)提供了高度封装、线程安全、泛型支持的数据结构实现,尤其以java.util包下的集合框架(Collection Framework)为典型代表。

从逻辑结构角度,Java数据结构可分为线性结构(如数组、链表、栈、队列)与非线性结构(如树、图、哈希表);从物理存储角度,又可分为顺序存储(如ArrayList)与链式存储(如LinkedList)。掌握这些结构的特性与适用边界,是编写高性能Java应用的前提。

⚡ Java核心数据结构分类速览

逻辑类型 物理实现 典型类/接口 适用场景
线性结构 顺序存储 ArrayList, Vector 频繁随机访问,少量插入/删除
线性结构 链式存储 LinkedList 频繁首尾插入/删除,较少随机访问
栈(LIFO) 顺序/链式 Stack, Deque 方法调用栈、表达式求值、括号匹配
队列(FIFO) 链式 LinkedList, PriorityQueue 任务调度、缓冲区、广度优先搜索
树(层次结构) 链式 TreeMap, TreeSet, HashMap$TreeNode 有序数据存储、范围查询、文件系统
图(网络结构) 邻接表/矩阵 自定义实现 社交网络、路径规划、依赖分析
哈希表(键值映射) 数组+链表/红黑树 HashMap, ConcurrentHashMap 快速查找、去重、缓存

需特别注意:Java中并无独立的“图”类实现,开发者需基于邻接表或邻接矩阵自行构建;而树结构多以二叉搜索树(BST)变体(如红黑树)形式存在于集合类中,如JDK 8+的HashMap在链表长度≥8且数组长度≥64时自动转为红黑树以优化查找性能。

〈提示〉:在JDK 1.8中,java的数据结构有什么的演进尤为关键——HashMap的底层结构从“数组+链表”升级为“数组+链表+红黑树”,在高冲突场景下将时间复杂度从O(n)降至O(log n),显著提升大数据量下的性能稳定性。

② 数组:最基础的线性结构

数组(Array)是Java中最基础、最高效的数据结构,支持O(1)时间复杂度的随机访问。其本质是连续内存空间的线性序列,适用于元素个数固定、频繁读取的场景。Java中数组分为原生数组(如int[])与封装类数组(如Integer[]),后者支持泛型与对象操作。

尽管ArrayList底层基于数组实现,但原生数组因其零开销抽象,在性能敏感场景(如算法竞赛、底层库开发)中仍具不可替代性。以下对比说明二者差异:

⚙️ 原生数组 vs ArrayList核心特性

原生数组
ArrayList
  • ✅ 固定长度,内存紧凑,无额外对象头开销
  • ✅ 支持基本类型(int、char等),避免装箱/拆箱
  • ✅ 深拷贝简单(clone()或System.arraycopy)
  • ❌ 扩容需手动创建新数组并复制
  • ❌ 缺乏泛型支持,类型安全依赖编译器检查

示例:二维数组模拟矩阵乘法

// Java原生二维数组实现矩阵乘法
public static int[][] multiply(int[][] A, int[][] B) {
    int m = A.length, n = B[0].length, p = B.length;
    int[][] C = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < p; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}
  • ✅ 动态扩容(默认增长50%),支持增删查操作
  • ✅ 泛型支持,编译期类型检查
  • ✅ 提供丰富方法(add、remove、contains等)
  • ❌ 扩容时需复制整个数组,O(n)开销
  • ❌ 插入/删除中间元素需移动后续元素

示例:ArrayList动态添加与遍历

// ArrayList动态操作示例
import java.util.ArrayList;
import java.util.List;
List names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
names.add("Charlie");
// O(1)尾部插入
names.add(1, "David"); // O(n)中间插入(需移动元素)
for (String name : names) {
    System.out.println(name);
}

在高频访问场景中,数组性能显著优于链表。例如对100万整数求和,原生int[]平均耗时约1.2ms,而Integer[]因装箱/拆箱开销升至3.8ms,LinkedList则高达22ms(需遍历指针)。因此,当数据规模固定且以读为主时,应优先选择数组。

③ 链表:动态内存的线性结构

链表(Linked List)通过节点(Node)存储数据与指向下一节点的引用,实现动态内存分配。其核心优势在于插入/删除操作的O(1)时间复杂度(已知节点位置),适用于频繁修改结构的场景。Java中LinkedList是双向链表实现,每个节点包含prev、next指针及数据域。

⚡ 链表 vs 数组:核心性能对比

操作 数组(ArrayList) 链表(LinkedList)
随机访问(get(i)) O(1) O(n)
尾部插入(add(e)) 均摊O(1) O(1)
中间插入(add(i,e)) O(n-i) O(n)(需遍历)
删除元素(remove(i)) O(n-i) O(n)(需遍历)
内存开销 仅数据+数组头 数据+prev+next指针(约24字节/节点)

【典型场景】:浏览器历史记录管理使用LinkedList,因用户回退/前进操作本质是栈/队列混合行为,频繁在头部/尾部插入/删除节点;而游戏开发中的粒子系统需动态增删粒子,LinkedList的O(1)删除特性可显著减少卡顿。

〈技巧〉:LinkedList的get(i)方法在JDK 1.8中采用“二分法”优化——当i < size/2时从头遍历,否则从尾遍历,将平均时间复杂度从O(n)降至O(n/2)。但整体仍远低于数组的O(1)。

自定义单向链表实现示例(面试高频):

// 单向链表基础实现
class MyNode {
    int val;
    MyNode next;
    MyNode(int v) { val = v; }
}
class MyLinkedList {
    private MyNode head;
    private int size;
    public void add(int val) {
        MyNode newNode = new MyNode(val);
        if (head == null) {
            head = newNode;
        } else {
            MyNode curr = head;
            while (curr.next != null) curr = curr.next;
            curr.next = newNode;
        }
        size++;
    }
    public void print() {
        MyNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " → ");
            curr = curr.next;
        }
        System.out.println("NULL");
    }
}

④ 栈:后进先出的结构

栈(Stack)遵循后进先出(LIFO)原则,仅允许在栈顶进行插入(push)与删除(pop)操作。Java中Stack类(继承Vector)已过时,推荐使用Deque接口的ArrayDeque实现,因其线程非安全、性能更优。

⚙️ 栈的三大典型应用场景

方法调用
括号匹配
表达式求值

Java虚拟机(JVM)通过调用栈(Call Stack)管理方法执行:每个方法调用创建栈帧(Stack Frame),包含局部变量表、操作数栈等。当方法返回时,栈帧弹出。递归深度过深会导致StackOverflowError。

// 递归导致栈溢出示例
public static int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n-1); // 每次调用压栈
}
// factorial(10000) → StackOverflowError

括号匹配是栈的经典应用。遍历字符串时,遇左括号压栈,遇右括号弹栈并检查是否匹配。最终栈应为空。

// 括号匹配算法
public static boolean isValid(String s) {
    Deque stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else if (c == ')' && !stack.isEmpty() && stack.pop() == '(') {
            continue;
        } else if (c == '}' && !stack.isEmpty() && stack.pop() == '{') {
            continue;
        } else if (c == ']' && !stack.isEmpty() && stack.pop() == '[') {
            continue;
        } else {
            return false;
        }
    }
    return stack.isEmpty();
}

中缀表达式转后缀(逆波兰表达式)需栈暂存运算符。例如"3 + 4 * 2" → "3 4 2 * +",遍历时数字直接输出,运算符根据优先级压栈/弹栈。

【性能提示】:ArrayDeque作为栈使用时,push/pop时间复杂度均为O(1),且比Vector/Stack少去了同步开销。在单线程场景中,性能提升可达30%以上。

⑤ 队列:先进先出的结构

队列(Queue)遵循先进先出(FIFO)原则,支持在队尾插入(offer)、队首删除(poll)。Java中Queue是接口,常用实现包括LinkedList(双端队列)、ArrayDeque(循环数组)、PriorityQueue(堆实现的优先队列)。

⚡ 队列类型与典型用例

FIFO队列
优先队列
双端队列

标准FIFO队列用于任务调度、消息缓冲。例如线程池中任务队列:生产者线程提交任务至队列,消费者线程从队列取出执行。

// FIFO队列任务处理示例
Queue taskQueue = new LinkedList<>();
taskQueue.offer("Task-1");
taskQueue.offer("Task-2");
while (!taskQueue.isEmpty()) {
    String task = taskQueue.poll();
    System.out.println("Processing: " + task);
}

PriorityQueue基于最小堆实现,每次poll返回最小元素。适用于需要按优先级处理的场景,如Dijkstra最短路径算法中的优先队列优化。

// 优先队列按任务紧急度排序
Queue pq = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority));
pq.offer(new Task("Low", 3));
pq.offer(new Task("High", 1));
pq.offer(new Task("Medium", 2));
// poll顺序:High → Medium → Low

Deque(Double Ended Queue)支持两端插入/删除,可作为栈或队列使用。ArrayDeque比LinkedList更高效(无节点对象开销)。

// Deque实现双端操作
Deque deque = new ArrayDeque<>();
deque.addFirst(1);  // [1]
deque.addLast(3);   // [1, 3]
deque.addFirst(0);  // [0, 1, 3]
// pollFirst() → 0, pollLast() → 3
〈注意〉:PriorityQueue非线程安全。多线程场景需使用PriorityBlockingQueue,其内部使用ReentrantLock保证线程安全。

⑥ 树:层次化数据结构

树(Tree)由节点与边组成,具有层次结构,无环路。Java中无直接树类,但TreeMap、TreeSet基于红黑树(自平衡BST)实现,保证O(log n)时间复杂度的增删查操作。

⚙️ 红黑树核心特性

  • ① 节点为红色或黑色
  • ② 根节点为黑色
  • ③ 叶子节点(null)为黑色
  • ④ 红色节点的子节点必为黑色
  • ⑤ 任一节点到其叶子节点的简单路径,黑节点数相同

这些规则确保最长路径≤最短路径的2倍,从而维持近似平衡。

【HashMap中的树化】:JDK 1.8中,当HashMap某链表长度≥8且数组长度≥64时,链表转为红黑树;当长度≤6时退化为链表。此举在高哈希冲突场景下将查找复杂度从O(n)降至O(log n)。

TreeMap
TreeSet

TreeMap基于红黑树实现,键值对有序存储,支持范围查询(subMap、headMap)。要求键实现Comparable或传入Comparator。

// TreeMap范围查询示例
TreeMap map = new TreeMap<>();
map.put(3, "C");
map.put(1, "A");
map.put(5, "E");
map.put(2, "B");
map.put(4, "D");
// 获取键在[2,4]的子映射
NavigableMap sub = map.subMap(2, true, 4, true);
// 输出:2=B, 3=C, 4=D

TreeSet基于TreeMap实现,仅存储值,内部使用PRESENT作为Value。支持去重与排序。

// TreeSet自动排序
TreeSet set = new TreeSet<>();
set.add("banana");
set.add("apple");
set.add("cherry");
// 输出:apple, banana, cherry
〈技巧〉:TreeMap的put/get/remove时间复杂度均为O(log n),但常数因子大于HashMap的O(1)。因此当不需要排序时,优先选择HashMap。

⑦ 图:网络化数据结构

图(Graph)由顶点(Vertex)与边(Edge)组成,分为有向图与无向图。Java标准库未提供图类,需开发者自定义实现。典型存储结构包括邻接矩阵(适合稠密图)与邻接表(适合稀疏图)。

⚡ 图的邻接表实现示例

// 简单有向图实现
import java.util.*;
class Graph {
    private Map> adj = new HashMap<>();
    public void addVertex(String v) {
        adj.putIfAbsent(v, new ArrayList<>());
    }
    public void addEdge(String from, String to) {
        adj.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
    }
    public List getNeighbors(String v) {
        return adj.getOrDefault(v, Collections.emptyList());
    }
    // BFS遍历
    public List bfs(String start) {
        Queue queue = new LinkedList<>();
        Set visited = new HashSet<>();
        List result = new ArrayList<>();
        queue.offer(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            String curr = queue.poll();
            result.add(curr);
            for (String neighbor : getNeighbors(curr)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        return result;
    }
}

【应用场景】:社交网络中的好友关系(无向图)、网页链接分析(有向图)、依赖管理(如Maven项目构建顺序)均需图结构。Java中Apache Commons Graph、JGraphT是第三方图库选择,但简单场景建议自定义轻量实现。

〈提示〉:在分布式系统中,图常用于依赖拓扑排序(如任务调度),可用Kahn算法(BFS)或DFS实现环检测与排序。

⑧ 哈希表:键值映射的利器

哈希表(Hash Table)通过哈希函数将键映射到数组索引,实现O(1)平均时间复杂度的查找。Java中HashMap是核心实现,其底层为数组+链表/红黑树的混合结构。

⚡ HashMap核心机制详解

put过程
扩容机制
线程安全

① 计算键的hashCode → ② 高低位异或扰动函数优化 → ③ 与数组长度-1按位与得索引 → ④ 若冲突则链表/红黑树插入 → ⑤ 元素数≥阈值时扩容

默认初始容量16,加载因子0.75。当size > capacity * 0.75时扩容为2倍。扩容需重新哈希(rehash),开销O(n),应预估容量避免频繁扩容。

HashMap非线程安全。多线程场景可选:① Collections.synchronizedMap → 性能差;② ConcurrentHashMap → 分段锁(JDK 8+用CAS+synchronized);③ CopyOnWriteArrayList(仅读多写少场景)。

【自定义键的注意事项】:重写equals()必须重写hashCode()!否则HashMap无法正确识别相等键。例如:

// 错误示例:未重写hashCode
class Person {
    String name;
    Person(String n) { name = n; }
    // 仅重写equals,未重写hashCode
}
Map map = new HashMap<>();
map.put(new Person("Alice"), 1);
map.get(new Person("Alice")); // 返回null(哈希值不同)
〈最佳实践〉:使用IDE生成equals/hashCode,或采用Lombok的@EqualsAndHashCode注解。JDK 14+可使用record自动处理。

⑨ 集合框架:java的数据结构有什么全景

Java集合框架(Collection Framework)统一了数据结构的接口与实现,核心接口包括Collection(List、Set、Queue)与Map。其设计遵循“接口-实现分离”,支持泛型、迭代器、线程安全扩展。

⚙️ 集合框架层级结构

Collection (接口)
├── List (有序,可重复)
│   ├── ArrayList (数组)
│   ├── LinkedList (双向链表)
│   └── Vector (线程安全数组)
├── Set (无序,不可重复)
│   ├── HashSet (HashMap实现)
│   ├── LinkedHashSet (LinkedHashMap实现)
│   └── TreeSet (红黑树实现)
└── Queue (队列)
    ├── PriorityQueue (堆)
    └── Deque (双端队列)
        └── ArrayDeque (循环数组)
Map (键值对)
├── HashMap (数组+链表/红黑树)
├── LinkedHashMap (双向链表维护插入顺序)
├── TreeMap (红黑树)
└── Hashtable (线程安全,已过时)

【选择指南】:

  • • 需要有序 → List/LinkedHashSet/LinkedHashMap
  • • 需要去重 → Set/Map
  • • 需要排序 → TreeSet/TreeMap
  • • 需要线程安全 → ConcurrentHashMap/Vector/Collections.synchronizedXxx
  • • 需要高性能 → ArrayList/HashMap/ArrayDeque
〈陷阱〉:Vector的synchronized方法粒度过大,性能远低于ConcurrentHashMap。JDK 1.2后已不推荐使用。