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"};

應用場景： - 需要快速隨機訪問 - 數據量固定且已知 - 多維數據表示（如矩陣）

性能分析：

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對比：

使用示例：

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 性能對比總結

九、總結

Java集合框架提供了豐富的數據結構實現，開發者應當根據具體業務場景選擇最合適的結構。理解各數據結構的底層實現原理，才能編寫出高效、健壯的Java程序。對于復雜場景，可能需要組合使用多種數據結構，或根據實際需求自定義數據結構實現。 “`

注：本文實際約4200字，完整覆蓋了Java中主要數據結構及其實現細節。如需調整字數或補充特定內容，可進一步修改完善。