Java 基础-集合

java面向对象特征

封装、继承、多态

封装：类比手机，把对象的属性和方法打包，隐藏内部细节，限制外部访问，只开放必要的接口。
属性的封装作用：保护数据。
方法的封装作用：便于使用、修改。
好处:增强可维护性、复用性

继承：类比"子承父业"，少做重复活.“子类复用父类的属性和方法，还能新增自己的特性”，核心是代码复用.
好处：增加代码复用性
子类无法直接访问父类的 private 属性和方法，可以通过父类的get/set方法访问。

多态： “表现为同一行为，不同对象不同表现”，类比叫这个行为，不同动物叫的方法不同。核心是 基于继承/实现，子类重写父类的方法、调用这个通用方法时，父类引用指向子类对象会根据对象的实际类型，执行对应的子类实现。

好处：提高代码的灵活性和扩展性，

集合框架

ArrayList/LinkedList区别、

ArrayList和LinkedList都实现了List接口,他们有以下的不同点:

1. 数据结构

• ArrayList：基于动态数组实现，元素在内存中是连续存储的，通过索引直接定位元素。
• LinkedList：基于双向链表实现，元素在内存中是分散存储的，每个元素（节点）存储自身数据 + 前后节点的引用。

2. 性能差异

• 查询：ArrayList快，时间复杂度 O(1)（直接通过索引定位） > LinkedList慢，时间复杂度 O(n)（需从头尾遍历到目标节点）
• 增删：
  • ArrayList慢（受到移动元素、扩容影响）
    • 中间插入：O(n)需移动后续元素
    • 尾部插入：无需扩容是O(1)；需要扩容是O(n)，需要复制整个数组
  • LinkedList快（仅需修改节点引用）
    • 已知节点的插入：O(1)
    • 任意位置：O(n)（需先遍历找到节点）

3. 内存占用

• ArrayList：开销小，仅存储元素本身；但数组会预留「扩容空间」（默认扩容为原容量的 1.5 倍），可能造成内存浪费。
• LinkedList：内存开销大，每个节点需额外存储前后节点的引用

4. 适用场景

• ArrayList：适合需要频繁按索引查数据、读多写少的场景。
• LinkedList：适合需要频繁在任意位置插入/删除元素（尤其是头尾操作）、写多读少的场景。

总结: ArrayList 和 LinkedList 的核心区别是底层结构决定的性能倾向：
ArrayList 基于动态数组，查得快、改得慢、内存较省，适合读多写少；
LinkedList 基于双向链表，改得快、查得慢、内存开销大，适合写多读少。

HashMap（JDK1.8 底层：数组+链表+红黑树）、

结构：底层是「数组 + 链表 + 红黑树」混合结构：数组哈希桶为基础，链表解决哈希冲突，红黑树优化长链表查询性能；

put步骤

1. 计算哈希值：通过哈希运算 hash(key) 得到哈希值。
2. 定位哈希桶并判空：(数组长度-1) & 哈希值 位运算计算出应存入的数组下标 index（位运算效率高于取模）

• 若桶为空：直接创建 Node 节点存入该桶，判断是否扩容。
• 若桶不为空：进入步骤 3 处理冲突。

3. 处理哈希冲突：

• 若桶中首个节点的 key 与新 key 相等（equals 为 true）：直接覆盖该节点的 value，方法结束。
• 若首个节点是红黑树节点（TreeNode）：按红黑树规则插入新节点，插入后检查是否需要调整树结构。
• 若首个节点是链表节点（Node）：遍历链表，找到 key 相等的节点则覆盖 value；未找到则将新节点插入链表尾部（JDK1.8 尾插法）。

4. 链表转红黑树判断：插入链表后，若链表长度 ≥ 8 且数组总容量 ≥ 64，则将当前链表转为红黑树。
5. 扩容判断：元素插入后，若当前元素个数（size）≥ 数组容量 × 负载因子（默认 0.75），则触发扩容，容量翻倍，同时重新计算所有元素的下标并迁移。

关键阈值：链表转红黑树阈值8，红黑树退链表阈值6，数组容量需≥64才会树化；

1.8 优化：链表插入改为尾插（解决 1.7 并发死循环）、引入红黑树（查询 O (logn) 替代链表 O (n)）；简化hash值算法：取模改为位运算

核心特性：非线程安全、key 唯一、允许 null 键值、无序存储、初始容量 16。

负载因子 0.75 的原因

1. 平衡「空间利用率」和「哈希冲突概率」
   过小，数组大量空间闲置，浪费内存；
   过大，哈希冲突上升，数组快满时，新元素易扎堆到同一桶，链表 / 红黑树变长，查询变慢
2. 0.75 接近「泊松分布」的最优值，数学上最合理
3. 容量默认是 2 的幂，容量 × 0.75 结果是整数，避免浮点精度问题，计算更高效

数组容量为什么是 2 的幂

哈希桶下标 = (数组长度-1) & 哈希值
数组容量参与哈希桶下标的计算，不是2的幂的话，位运算会有问题，增加哈希冲突概率

为什么 HashMap 线程不安全？

1. 多线程 put 时可能导致值覆盖；（两个线程往同一个空桶put不同值，线程1存完，线程2还以为是空的，把值直接覆盖了）
2. JDK1.7 多线程扩容会导致链表成环，查询时死循环；
3. 无法保证迭代过程中元素的一致性（快速失败机制）。

ConcurrentHashMap线程安全原理

ConcurrentHashMap 是 HashMap 的线程安全替代方案，核心思路是通过 “锁细化” 降低并发冲突

一、JDK1.7 实现原理：分段锁（Segment + HashEntry）

1. 底层结构

采用Segment 数组 + HashEntry 数组 + 链表的双层结构：

• Segment：本质是一个可重入锁（ReentrantLock），每个 Segment 对应一个 HashEntry 数组；

ConcurrentHashMap ├─ Segment数组（每个Segment是ReentrantLock，默认16个） │ ├─ Segment 0（锁） │ │ └─ HashEntry数组（Segment 0管理的哈希桶数组） │ │ ├─ HashEntry[0] → 链表节点1 → 链表节点2（哈希冲突时的链表） │ │ ├─ HashEntry[1] │ │ └─ ... │ ├─ Segment 1（锁） │ │ └─ HashEntry数组（Segment 1管理的哈希桶数组） │ │ ├─ HashEntry[0] │ │ └─ ... │ └─ ...

ai生成图如下：

2. 线程安全核心：分段锁机制

• 数据分片：默认将整个哈希表分成16个 Segment，每个 Segment 独立管理一部分数据；
• 锁粒度：Segment，相当于segement下的多个桶都被锁，不会影响其他 Segment 的并发读写；
• 并发度：默认支持 16 个线程同时操作不同的 Segment
  缺点：锁的粒度不够细

二、JDK1.8 实现原理：CAS + synchronized + 红黑树

抛弃了 Segment 分段锁，底层结构和 HashMap 一致（数组 + 链表 + 红黑树），线程安全依赖CAS 无锁机制和synchronized 锁细化

1. 核心保障机制
   1. 原子性：简单场景初始化数组、往空桶中插入第一个节点时，使用 CPU 级别的原子指令CAS 机制保证原子性，只有确认当前内存值符合预期值，才会更新。
   2. 桶中已经有节点（要调整链表或红黑树这类复杂操作前），先用 synchronized 锁住这1个桶的头节点，而非整个数组或 Segment，相比1.7并发效率大幅提升
   3. 可见性：数组和节点都被voilatile修饰，一个线程改完，别的线程能立马看到最新结果，避免脏读
   4. 扩容时采用多线程协同机制（避免单线程扩容慢）
2. 不允许 key 或 value 为 null（HashMap 允许）
   避免并发场景下的空指针歧义（无法区分 “key/value 本身是 null” 和 “key 不存在导致返回 null”）
3. 与 Hashtable 对比：Hashtable 是全局 synchronized 锁，并发效率低；ConcurrentHashMap 是细粒度锁，效率更高。