02-Java集合

2025-01-15 19:43:35   0  举报





AI智能生成

Java集合框架为Java程序员提供了一套性能优化的、标准化的数据结构和算法接口。该框架核心内容包括一系列接口（如Collection、Set、List、Map等）、实现类（如ArrayList、LinkedList、HashMap等）以及辅助性工具类（如Collections）。集合框架不仅支持泛型，还注重线程安全和效率，覆盖了数组无法提供的动态性需求。例如，List接口允许重复且有序，而Set接口则不允许重复元素。Map接口则是无序的键值对集合。Java集合框架对数据操作提供了丰富的方法，如增加、删除、修改、查询以及排序等，极大地简化了数据管理和算法实现的复杂性。集合框架还是多种数据处理操作的核心，例如排序（如Arrays.sort()和Collections.sort()）以及搜索操作。其用途广泛，是Java开发中不可或缺的一部分。

Java

八股文

作者其他创作

大纲/内容

2.6 算法题

实现LRU

实现线程安全的LRU

实现Set

实现线程安全的Set

2.5 场景题

2.5.1 如何实现一个线程安全的LRU

可以参考LinkedHashMap和ConcurrentHashMap共同实现（易宝外派阿里达摩院的算法题）

2.5.2 如何实现一个Map

可以参考HashMap去实现，这道题就是HashMap的八股文变相回答

2.4 ConcurrentModificationException

抛出时段：集合被遍历时出现修改操作会抛出

抛出原理：

在集合内维护了一个和修改次数有关的变量（Iterator的modCount），如果发生修改，modCount会增加，如果 modCount != expectedModCount，就会抛出异常

ArrayList的modCount机制就是如此，在Iterator的next() 方法中，就有检查 modCount 和 expectedModCount 是否相同的逻辑

2.1 序章

集合分类

Collection 接口

Set

HashSet：基于HashMap实现

LinkedHashSet：基于LinkedHashMap实现

TreeSet：基于TreeMap实现

List

ArrayList：动态数组，查询快，插入删除慢

LinkedList：链表，查询慢，插入删除快，亦可充当FIFO队列

Vector：线程安全的动态数组，开销较大

Queue

PriorityQueue：基于优先级堆

LinkedList

Map（不允许键重复）

HashMap：哈希表，键值对无序

LinkedHashMap：基于链表和哈希表，维护插入顺序

TreeMap：基于红黑树，键值对有序

Hashtable：线程安全的哈希表，不允许键为null

ConcurrentHashMap：线程安全，更适合高并发环境

2.2 Map

2.2.1 HashMap（所有的Map都会围绕它展开）

把键的哈希值映射到数组索引的位置，通过**数组+链表**来处理哈希冲突

自JDK8开始，除了**数组**和**链表**外，**红黑树**也参与哈希冲突的处理

当哈希冲突较多时，链表中的元素增多，插入、查找以及删除的时间复杂度会从原来的O(1)退化到O(n)

因此加入红黑树后，机制变化如下：

链表长度超过`TREEIFY_THRESHOLD`（=8），且数组长度大于等于`MIN_TREEIFY_CAPACITY`（=64）时会转换成红黑树，否则不转换，以避免性能的急剧下降

当链表长度缩短到6以下时，才会退化回链表，保持简单高效

如果抛弃链表，直接使用红黑树可以吗？

由于红黑树节点大小是普通节点的两倍，所以为了节省空间，不会直接使用红黑树，而是当节点达到某一数量`TREEIFY_THRESHOLD`时才会转换成红黑树

`TREEIFY_THRESHOLD = 8`的原因是泊松分布有关

为何节点数小于等于6才会退化

平衡时间和空间，节点少链表遍历也很快，没必要转，用链表还节省内存

无论是红黑树转链表，还是链表转红黑树，都有一定的开销，需要留一个缓冲余地，避免突然的变化，反复横跳

Hash碰撞

由于Hash值相同，这些键会映射到Hash表的同一个位置，从而引发碰撞

解决方法

**拉链法（链地址法）**：将Hash表中的每个槽位变成一个链表，当多个Hash值相同时，把它们放在同一链表中

**开放寻址法**：如果出现碰撞，寻找下一个可用位置

**线性探查法**：在哈希表中查找下一个连续的空槽，将碰撞的键存入该槽中

**平方探查法**：类似于线性探查，但步长为二次方，减少了聚集问题

**双散列法**：使用两个不同的哈希函数，第一次哈希决定初始位置，第二次决定步长

**再哈希法（双重哈希）**：在出现碰撞时，使用第二个哈希函数重新计算索引位置，减少碰撞概率

方法对比| 方法 | 优点 | 缺点 | | ---- | ------------------------------------ | ----------------------------------------------------------------------------- | | 拉链法 | 简单易实现，扩展性好<br/>在处理大量数据时，性能更稳定 | 需要额外的内存开销<br/>若频繁碰撞，链表变长，查询性能下降 | | 开放寻址 | 无需额外内存来存储指针和数据结构<br/>若负载因子低，查找、插入效率高 | 若哈希表填充度增加，探查次数也会增加，性能会下降<br/>删除元素时，只能使用删除标记，否则会导致查询错误，必须等到下一个元素插入时，发现标记后才可以替换 | | 再哈希 | - | - |

hashCode()和equals()的重要性

HashMap的键必须实现hashCode()和equals()方法

hashCode()用于计算Hash值，决定键的存储位置

euqals()用于比较键是否相同

在put操作时，如果Hash值相同，但equals为false，两个键会视为不同的键

误用它们会导致HashMap的元素无法正常查找或插入

分支主题

默认容量和负载因子

数值：默认容量16，负载因子0.75，这个组合是在性能（时间复杂度）和空间（复杂度）之间找到的平衡

若负载因子较高，比如1.0，确实会减少空间浪费，但增加Hash冲突的概率

若负载因子较低，会有空间的开销，但Hash冲突概率会更小

提升性能小技巧

合理设置初始容量，在new HashMap时，就需要根据需求确定一个初始容量，但不确定的情况下，在新建HashMap时，把初始容量设定为默认的初始容量（16）

调整负载因子，可根据使用场景来调整数目，如果不确定，也要设置默认的数量（0.75）

确保hashCode均匀分布，在重写key所属类的hashCode方法时，确保其生成的哈希值能够均匀分布，减少冲突。避免使用质量不高的hash函数，防止大量键映射到相同的槽位上，造成性能瓶颈

扩容机制

使用2的n次方倍作为扩容容量，以提高哈希值的分布均匀性和哈希计算效率（n为数组长度）

HashMap通过 (n-1) & hash 来计算元素索引存储位置，这种位运算，必须确保在2的n次方的情况下才能确保索引均匀分布。

位运算的效率高于模取运算，即 hash mod n，提高了hash计算的计算速度

扩容时只需通过简单的位运算判断是否需要迁移，减少重新计算的开销，提升refresh效率

JDK1.8 以后都有哪些优化

链表与红黑树的转换 - 略，已提到

改进了哈希函数的计算：让哈希值的分布更加均匀，减少了哈希冲突的发生

扩容机制的优化：扩容过程中不再对每个元素重新计算哈希值，而是根据原数组长度的高位来判断元素是迁移还是保留，减少了不必要的计算，扩容效率得到提升

头插法改尾插法：头插法确实在插入时不需要遍历，直接替换成头节点，但扩容时会产生逆序的情况，在多线程下可产生环，造成死循环的产生，才改回了尾插法

HashMap与HashSet的联系

基于HashMap实现，由于HashSet元素的本质就是HashMap的键，所以不允许重复元素

2.2.2 Hashtable 和 ConcurrentHashMap

共同点：线程安全，且不允许键或值为null

**为了避免混淆和潜在的并发问题**：要不然不好判断到底是key不存在，还是value就是null（go语言的map做得就不错，go语言map有两个值，一个确实表示值，另一个就是表明它是否存在，但go语言map线程也不安全，有个线程安全版叫sync.Map，扯远了）

**简化实现**：如果key或value为null，会给诸如put、get、containsKey等操作带来复杂性。需要加额外的逻辑来区分key的存在性

总之，如果允许了，并发修改或删除时，就会导致多线程下不一致的状态，增加调试及维护难度

差异点

Hashtable：使用全表锁机制，所有的操作都要用synchronized来保障线程安全，在多线程环境下效率极低

ConcurrentHashMap：JDK1.8 用的是 `CAS + synchronized`的方式进行线程安全控制。CAS源于无锁操作，若某个Node节点为空，则通过CAS的方式将数据插入节点，否则退化回synchronized，只锁定特定的冲突节点，不会锁全表，因而并发效能更好

ConcurrentHashMap 1.7 到 1.8 的变化

锁的方式不同

1.7 版本采用的是分段锁，每个Segment是独立的，可以并发访问不同的Segment，默认是16个，所以最多只能有16个线程可以并发执行

1.8 剔除了Segment，锁只在链表或红黑树的节点上进行，粒度更细了，通过CAS进行插入操作，只有做更新和红黑树操作时才会用synchronized，并且只锁住链表或树的头节点，进一步减锁的竞争，并发度大大增加

扩容机制变化

1.7 基于Segment扩容，每个Segment中包括一个HashMap，当某个Segment内的HashMap达到扩容阈值时，按照HashMap的扩容标准对这个Segment单独扩容，不影响其它的Segment

1.8 的扩容机制更加往HashMap的方式靠拢

由于Segment没了，就直接是一个全局数组，只要某个位置的元素超过阈值，就会被扩容

通过CAS操作确保线程安全

使用渐进式扩容手段，不会一次性把所有数据重新分配，而是多个线程共同参与，逐步迁移，以降低开销

size逻辑的区别，具体可以看它们的源码

ConcurrentHashMap的get方法还加锁吗？

不用，通过volatile关键字，ConcurrentHashMap能确保get方法的线程安全，即使在写入发生时，读取线程仍能获取到最新的数据，不会引发并发问题‘

具体是对Unsafe#getXXXVolatile和用volatile来修饰节点的val和next指针来实现的

与HashMap的区别一览| 类型 | HashMap | Hashtable | ConcurrentHashMap | | ----- | ------------------------- | -------------------------------------------------------------------- | ---------------------------------------------------------- | | 线程安全 | 否 | 是 | 是 | | 性能差异 | 没有线程同步开销，单线程性能优于Hashtable | 由于方法的同步机制，单线程环境下性能必然低于HashMap；由于使用单一锁机制，多线程环境下也明显不如ConcurrentHashMap | 高并发场景下，优于前两者，无论是1.7使用Segment方式还是1.8使用CAS + synchronized的方式 | | 继承结构 | 继承自AbstractMap，是Map接口的实现类 | 继承自~~Dictionary~~（已废弃），后来也实现Map接口，由于比较古老，在Java 2 后被HashMap取代了 | 继承自AbstractMap，是ConcurrentMap接口的实现类，ConcurrentMap又继承自Map | | 允许空值 | 是 | 否 | 否 | | 迭代器类型 | 快速失败型，迭代时修改会抛出异常 | 弱一致型，迭代时修改不会抛出异常 | 弱一致型，迭代时其它线程修改不会抛出异常 |

其它Map

WeakHashMap: 用于缓存（内存敏感场景）的实现

LinkedHashMap: 继承自HashMap，只是引入了一个双向链表来记录元素插入顺序或访问顺序，用于

TreeMap：基于红黑树实现

IdentityHashMap：通过==作为键的比较方式，只有两个键的引用相同，才能视为同一个键，至于使用的哈希码，是System.identityHashCode

2.3 List

2.3.1 基本方法

add：有两种实现方法，add(E e) 和 add(int index, E element)，前者实现末端添加一个元素，后者实现指定元素插入

remove(int index)：删除指定index的元素

set(int index, E element)：修改index中的元素为element

get(int index)：获取index中的值

indexOf(Object o)，lastIndexOf(Object o)：查找元素所在位置，前者查找第一个指定元素出现的位置，后者查找最后一个指定元素所在位置，查不到就是-1