恬静荒芜的时光
数据结构与java集合框架的关系
song
  2025-02-11 13:57:00   2025-12-29 11:04:00

常见的数据结构 vs java中常用的集合

  • 数组
  • 链表
  • 哈希表
  • 栈
  • 队列
  • 二叉树
    • 红黑树
    • 平衡二叉树

数组结构

  • 数组（Array）是一种定长的线性数据结构，用于存储相同类型的数据。
  • 数组在内存中是连续存储的，可以通过索引（index）快速访问元素
  • 查询快，删除慢
  • 适用于需要高效随机访问的场景
1
int [] arr= new int[5];

执行后，JVM 内存布局如下：

  • 栈（Stack）： 存放数组引用 arr。
  • 堆（Heap）： 分配一块连续内存用于存储 5 个 int 元素，每个 int 占 4 字节。
  • 方法区（Method Area）： 存储数组的类信息（int[] 的 Class 对象）。
1
2
3
4
Stack (栈)           Heap(堆)
----------------    -------------------------
arr (引用)  ----->  | 0 | 0 | 0 | 0 | 0 |  (int[] 数组)
----------------    -------------------------

数组的优缺点

  • 缺点
    1. 固定大小（定长） → 创建后不能动态扩展，需要提前确定大小，扩容需要创建新数组并复制数据（O(n)）
    2. 插入和删除效率低（O(n)） → 插入或删除时需要移动大量数据。
    3. 不能存储不同类型的数据 → 只能存储相同类型的数据（可以存 Object，但仍然是同一类型）。
  • 优点
    1. 索引访问速度快（O(1)） → 由于数组采用连续内存存储，可以直接通过索引访问元素，不需要遍历查找。
    2. 空间利用率高 → 由于没有额外的指针或对象开销（对于基本数据类型），比链表等数据结构更节省内存。
    3. 容易实现缓存优化 → CPU 访问数组比访问链表等非连续结构更快，能够提高缓存命中率。

链表结构

  • 是一种线性数据结构，每个节点（Node）存储数据并指向下一个节点
  • 链表在内存中不连续存储，每个元素（节点）包含：数据、下一个节点引用
  • 有多种不同类型的链表
    • 单向链表 Singly Linked List
    • 双向链表 Doubly Linked List
    • 循环链表 Circular Linked List

单向链表

  • 每个节点只包含 数据 和 指向下一个节点的指针（next）。
  • 只能 从头遍历到尾部，不能向后回溯。

示意图

1
Head → [A | Next] → [B | Next] → [C | Next] → null

双向链表

  • 每个节点包含 数据、前指针（prev） 和 后指针（next）。
  • 可以 从头遍历到尾，也可以从尾部回溯到头。

示意图

1
null ← [A | Prev, Next] <--> [B | Prev, Next] <--> [C | Prev, Next] → null

循环链表

  • 单向循环链表：最后一个节点的 next 指向头节点，形成闭环。
  • 双向循环链表：双向链表的 prev 指向最后一个节点，next 指向第一个节点。

单向循环链表示意图

1
2
Head → [A | Next] → [B | Next] → [C | Next] ┐
        └────────────────────────────────────┘

双向循环链表示意图

1
2
[A | Prev, Next] ↔ [B | Prev, Next] ↔ [C | Prev, Next]
      ↖────────────────────────────────────↗

链表的优缺点

  • 优点
    1. 插入和删除操作快 (O(1))
      • 插入/删除时不需要移动其他元素，不像数组那样涉及大量数据搬移。
      • 适用于频繁插入/删除的场景，如队列、缓存（LRU）等。
    2. 支持动态扩展
      • 没有固定大小，适用于数据量变化较大的情况。
    3. 双向链表可双向遍历
      • prev 指针让我们可以从后往前遍历。
  • 缺点
    1. 索引访问慢 (O(n))
      • 由于链表不连续存储，无法像数组一样通过索引直接访问，必须从头遍历到目标位置。
      • 适用于插入/删除频繁的场景，不适用于索引访问频繁的场景！
    2. 额外的空间开销
      • 每个节点都存有 prev 和 next 指针，会额外占用额外的内存。
    3. 不利于缓存优化
      • 数组存储在连续内存块中，CPU 缓存访问快；链表由于节点分散在堆中，访问速度较慢。

哈希表结构

  • 哈希是什么
    • 哈希是一种将数据映射到固定大小数组（哈希表）的技术，用于计算索引值。通过哈希函数（Hash Function）计算存储位置。
    • 用一个函数将数据映射成一个索引，以便快速查找。
  • 哈希表是什么
    • 哈希表（Hash Table）是一种基于哈希函数（Hash Function）实现的 键值对（Key-Value）存储数据结构。
    • 它使用哈希函数将键（Key）转换成数组索引（Bucket），从而快速存取数据。

hashtable的存储原理

  1. 计算key的哈希值
    • 使用key.hashCode() 计算哈希值
  2. 确定存储索引
    • index = hashCode % 数组长度
  3. 存储到数组的对应位置
    • 如果该位置已有数据（哈希冲突），则采用链表或其他方式存储
      • 栈存储方式的链表，新入数据在顶部，老数据一往下压
1
2
3
4
5
6
[0] -> null
      [1] -> (Key1, Value1) -> (Key5, Value5) -> null
      [2] -> (Key2, Value2) -> null
      [3] -> null
      [4] -> (Key3, Value3) -> (Key7, Value7) -> null
      [5] -> (Key4, Value4) -> null
1
2
计算Key的哈希值

其他

  • Collection
    • List
      • ArrayList
      • LinkedList
    • Set
      • HashSet
        • LinkedHashSet
      • [[TreeSet]]
      • aaa

Collection集合特点

  • List集合特点

    • 有索引
    • 数据有序
    • 可存储重复的数据

  • Set集合特点

    • 没有索引
    • 存取元素不保证顺序（无序）
    • 不允许重复的元素（唯一）

  • ArrayList 集合特点

    • 底层是数组 ，一段连续的存储空间
    • 有索引，可以通过索引存取数据
    • 数据有序，取出的顺序与存储的顺序一致
    • 可以存储重复的数据

  • LinkedList集合特点

    • 底层是双向链表（有头，有尾）
      • 增删快，查询慢
      • 有有自己特有的方法 getFirst() getLast()
    • 有索引，可以通过索引取数据
      • 需避免大量索引访问（get(i)）
      • LinkedList.get(i) 需要从头遍历到索引 i，性能比 ArrayList 差。
    • 数据有序，取出的顺序与存储的顺序一致
    • 可以存储重复的数据

  • HashSet

    • 底层使用的哈希表
      • 存在相同元素必须重新类型的hashCode 、equals方法
      • java1.8前 Hashtable 数组+ 链表
      • java1.8后 HashMap 数组+ 链表/红黑树
    • 无须、不允许重复、没有索引

  • LinkedHashSet

    • HashSet的子类
    • 底层使用了 HashSet+双向链表结构
    • 哈希表用来去重、链表保证存取元素的顺序
    • 无索引、不允许重复、保证存取顺序

  • TreeSet

    • 底层使用红黑树结构
    • 不能存储重复元素
    • 没有索引
    • 存储的元素会按照规则进行排序

LinkedHashSet存储过程

1
2
3
4
LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Cherry");
  1. 计算 hashCode()，确定存储索引（基于 HashMap 计算）。
  2. 如果索引处无元素，直接存入数组，并记录插入顺序。
  3. 如果索引处已有元素（哈希冲突），则使用链表或红黑树存储，但仍会维护插入顺序。

LinkedHashSet vs HashSet

对比项 HashSet LinkedHashSet
底层实现 HashMap<K, Object> LinkedHashMap<K, Boolean>
元素存储顺序 无序 按插入顺序存储
遍历性能 快（无序） 稍慢（因维护链表）
适用场景 只需要快速查找、不关心顺序 既要去重，又要保持插入顺序
特性 Hashtable（Java 8 之前） HashMap（Java 8 之后）
数据存储 数组 + 链表 数组 + 链表 / 红黑树
冲突处理 仅使用链表存储 链表 + 红黑树（当链表长度超过 8）
线程安全 是（synchronized） 否（但可以用 ConcurrentHashMap）

其他2

  • Map

    • 存储2个元素 ，键值对
    • key元素不可重复，value可以重复
    • 一个key对应一个value元素
    • 存储元素不保证顺序
    • 没有索引

  • Map

    • HashMap 哈希表
    • LinkedHashMap 哈希表+链表
    • TreeMap 红黑树
  1. 1. 常见的数据结构 vs java中常用的集合
  2. 2. 数组结构
    1. 2.1. 数组的优缺点
  3. 3. 链表结构
    1. 3.1. 单向链表
    2. 3.2. 双向链表
    3. 3.3. 循环链表
    4. 3.4. 链表的优缺点
  4. 4. 哈希表结构
    1. 4.1. hashtable的存储原理
  5. 5. 其他
    1. 5.1. LinkedHashSet vs HashSet
  6. 6. 其他2
© 2024 - 2025    song
由 Hexo 驱动 & 主题 Keep
  1. 1. 常见的数据结构 vs java中常用的集合
  2. 2. 数组结构
    1. 2.1. 数组的优缺点
  3. 3. 链表结构
    1. 3.1. 单向链表
    2. 3.2. 双向链表
    3. 3.3. 循环链表
    4. 3.4. 链表的优缺点
  4. 4. 哈希表结构
    1. 4.1. hashtable的存储原理
  5. 5. 其他
    1. 5.1. LinkedHashSet vs HashSet
  6. 6. 其他2