集合(补充篇)
说明
v1.0[2024.09]
本文主要取自小林coding
其实有了之前的上下已经非常全面,但是现在对我的进度来说,八股处在一个差不多完整的二刷阶段,有些新的理解和体会,也有一些先前没有掌握或者注意到的点,于是在这篇记录下来
v1.1[2025.04.27]
N刷之后的新内容
数组与集合区别,用过哪些?
数组和集合的区别:
数组是固定长度的数据结构,一旦创建长度就无法改变,而集合是动态长度的数据结构,可以根据需要动态增加或减少元素。
数组可以包含基本数据类型和对象,而集合只能包含对象。(经常被忽略的地方)
数组可以直接访问元素,而集合需要通过迭代器或其他方法访问元素
我用过的一些 Java 集合类:
- ArrayList: 动态数组,实现了List接口,支持动态增长
- LinkedList: 双向链表,也实现了List接口,支持快速的插入和删除操作。
- HashMap: 基于哈希表的Map实现,存储键值对,通过键快速查找值。
- Hashset: 基于HashMap实现的Set集合,用于存储唯一元素。
- TreeMap: 基于红黑树实现的有序Map集合,可以按照键的顺序进行排序。
- LinkedHashMap: 基于哈希表和双向链表实现的Map集合,保持插入顺序或访问顺序。
- PriorityQueue: 优先队列,可以按照比较器或元素的自然顺序进行排序。
Java中线程安全的集合
在 java.util 包中的线程安全的类主要 2 个,其他都是非线程安全的
Vector:线程安全的动态数组,其内部方法基本都经过 synchronized
修饰,如果不需要线程安全,并不建议选择,毕竟同步是有额外开销的。Vector 内部是使用对象数组来保存数据,可以根据需要自动的增加容量,当数组已满时,会创建新的数组,并拷贝原有数组数据。
Hashtable:线程安全的哈希表,HashTable 的加锁方法是给每个方法加上 synchronized 关键字,这样锁住的是整个 Table 对象,不支持 null 键和值,由于同步导致的性能开销,所以已经很少被推荐使用,如果要保证线程安全的哈希表,可以用ConcurrentHashMap。
java.util.concurrent 包提供的都是线程安全的集合:
并发Map:
- ConcurrentHashMap:它与 HashTable 的主要区别是二者加锁粒度的不同,在JDK1.7,ConcurrentHashMap加的是分段锁,也就是Segment锁,每个Segment含有整个table 的一部分,这样不同分段之间的并发操作就互不影响。在JDK1.8,它取消了Segment字段,直接在table元素上加锁,实现对每一行进行加锁,进一步减小了并发冲突的概率。对于put操作,如果Key对应的数组元素为null,则通过CAS操作(Compare and swap)将其设置为当前值。如果Key对应的数组元素(也即链表表头或者树的根元素)不为nul,则对该元素使用 synchronized 关键字申请锁,然后进行操作。如果该 put 操作使得当前链表长度超过一定阈值,则将该链表转换为红黑树,从而提高寻址效率。
- ConcurrentSkipListMap:实现了一个基于Skiplist(跳表)算法的可排序的并发集合,Skiplist是一种可以在对数预期时间内完成搜索、插入、删除等操作的数据结构,通过维护多个指向其他元素的“跳跃“链接来实现高效查找。
并发Set:
ConcurrentSkipListSet:是线程安全的有序的集合。底层是使用ConcurrentSkipListMap实现。
CopyOnWriteArraySet:是线程安全的Set实现,它是线程安全的无序的集合,可以将它理解成线程安全的HashSet。
有意思的是,
CopyOnWriteArraySet
和HashSet
虽然都继承于共同的父类AbstractSet
但是,HashSet是通过“散列表”实现的,而CopyOnWriteArraySet则是通过"动态数组(CopyOnWriteArrayList)"实现的,并不是散列表。
并发List:
- CopyOnWriteArrayList:它是 ArrayList 的线程安全的变体,其中所有写操作(add,set等)都通过对底层数组进行全新复制来实现,允许存储 null 元素。即当对象进行写操作时,使用 Lock 锁做同步处理,内部拷贝原数组,并在新数组上进行添加操作,最后将新数组替换掉旧数组:若进行读操作,则操作过程中不需要进行同步而直接返回结果。
并发 Queue:
- ConcurrentLinkedQueue:是一个适用于高并发场景下的队列,它通过无锁的方式(CAS),实现了高并发状态下的高性能。通常,ConcurrentLinkedQueue 的性能要好于 BlockingQueue。
- BlockingQueue:与 ConcurrentLinkedQueue 的使用场景不同,BlockingQueue 的主要功能并不是在于提升高并发时的队列性能,而在于简化多线程间的数据共享。BlockingQueue 提供一种读写阻塞等待的机制,即如果消费者速度较快,则 BlockingQueue 则可能被清空,此时消费线程再试图从 BlockingQueue 读取数据时就会被阻塞;反之,如果生产线程较快,则 BlockingQueue 可能会被装满,此时,生产线程再试图向 BlockingQueue 队列装入数据时,便会被阻塞等待。
并发 Deque:
- LinkedBlockingDeque:是一个线程安全的双端队列实现。它的内部使用链表结构,每一个节点都维护了一个前驱节点和一个后驱节点。LinkedBlockingDeque 没有进行读写锁的分离,因此同一时间只能有一个线程对其进行操作
- ConcurrentLinkedDeque:ConcurrentLinkedDeque是一种基于链接节点的无限并发链表。可以安全地并发执行插入、删除和访问操作。当许多线程同时访问一个公共集合时,ConcurrentLinkedDeque是一个合适的选择
Collections和Collection的区别
Collection是Java集合框架中的一个接口,它是所有集合类的基础接口。它定义了一组通用的操作和方法,如添加、删除、遍历等,用于操作和管理一组对象。Colection接口有许多实现类,如List、Set和Queue等。
Colections(注意有一个s)是Java提供的一个工具类,位于iava.uti包中。它提供了一系列静态方法,用于对集合进行操作和算法。Collections类中的方法包括排序、査找、替换、反转、随机化等等。这些方法可以对实现了Collection接口的集合进行操作,如List和Set。
集合遍历的方法
普通for循环,利用索引
增强for循环(for-each循环):用于循环访问数组或集合
Iterator 迭代器:可以使用迭代器来遍历集合,特别是用于需要删除元素的情况(remove是安全的在遍历中删除元素的方法)
javaIterator<String> iterator = list.iterator(); while(iterator.hasNext()){ String element = iterator.next(); System.out.println(element); }
ListIterator 列表迭代器: Listlterator是迭代器的子类,可以双向访问列表并在迭代过程中修改元素。
javaListIterator<string> listIterator = list.listIterator(); while(listIterator.hasNext()){ String element =listIterator.next(); System.out.println(element); }
使用 forEach 方法: Java 8引入了 forEach 方法,可以对集合进行快速遍历。
javalist.forEach(element ->System.out.println(element)); // list.forEach(System.out::println);
Stream APl: Java 8的Stream AP!提供了丰富的功能,可以对集合进行函数式操作,如过滤、映射等。
javalist.stream().forEach(element ->System.out.println(element));
为什么ArrayList不是线程安全的,具体来说是哪里不安全?
在高并发添加数据下,ArrayList会暴露三个问题
部分值为 null(我们并没有add null进去)
索引越界异常
size与我们add的数量不符
为了知道这三种情况是怎么发生的,ArrayList 对应 add 增加元素的代码如下:
public boolean add(E e){
ensureCapacityInternal(size + 1);//Increments modcount!!
elementData[size++]=e;
return true;
}
ensureCapacityInternal
这个方法的详细代码可以不看,它的作用是判断:如果将当前的新元素加到列表后面,列表的elementData数组的大小是否满足,如果 size + 1
这个需求长度大于了elementData的长度,那么就要对这个数组进行扩容。
大体可以分为三步:(这里的精髓在于 size
这个变量,它既表示了List当前容纳的数量,也是下一次要插入元素时的下标)
- 判断数组需不需要扩容,如果需要的话,调用grow方法进行扩容
- 将数组的size位置设置值(因为数组的下标是从0开始的)
- 将当前集合的大小 size 加1
具体是如何产生上面说到的三个情况的?
- 部分值为null:线程1发现当前size是9,而数组容量是10,所以不用扩容,这时线程2也进来了,发现size是9,而数组容量是10,所以也不用扩容,而这时线程1继续执行,将数组下标索引为9的位置set值,还没来得及执行size++,这时线程2也来执行了,又把数组下标索引为9的位置set了一遍(覆盖了),这时两个先后进行size++,导致下标索引10的地方就为null了。
- 索引越界异常:线程1发现当前size是9,数组容量是10不用扩容,此时线程1还没有执行到插入元素的逻辑,线程2执行发现不需要扩容,但线程1此时执行了set操作并让size++,这时轮到线程2再执行的时候size就已经是10也就是会发生越界的索引位置
- size与我们add的数量不符:基本上每次都会发生,主要因为size++本身就不是原子操作,可以分为三步:获取size的值,将size的值加1,将新的size值覆盖掉原来的。线程1和线程2拿到一样的size值然后对原来的值覆盖,其实其中一个线程的操作就成了覆盖性的操作
ArrayList 和 LinkedList 有什么区别?
- 底层数据结构
- ArrayList底层是基于数组实现的,LinkedList底层是基于双向链表实现的
- 适⽤的场景
- ArrayList更适合随机查找 index,LinkedList更适合删除和添加,查询、添加、删除的时间复杂度不同
- 接口实现
- ArrayList和LinkedList都实现了List接⼝,但是LinkedList还实现了Deque接口,LinkedList还可以当做队列来使用
- 内存占用
- 一般情况下,LinkedList的占用空间更大,因为每个节点要维护指向前后地址的两个节点,但也不是绝对,如果刚好数据量超过ArrayList默认的临时值时,ArrayList占用的空间也是不小的,因为扩容的原因会浪费将近原来数组一半的容量;
- 不过,因为ArrayList的数组变量是用
transient
关键字修饰的,如果集合本身需要做序列化操作的话,ArrayList这部分多余的空间不会被序列化。
线程安全的CopyOnWriteArrayList是怎么实现线程安全的?
首先,CopyOnWriteArrayList的底层是一个数组,并且使用volatile关键字修饰,保证当前线程对数组对象重新赋值后,其他线程可以及时感知
private transient volatile Object[] array;
在写入(add和set)操作时,添加一把互斥锁 ReentrantLock保证线程安全
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
E oldValue = get(elements, index);
// 精华还是len既是原数组长度,又是最新添加元素的索引
if (oldValue != element) {
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);
newElements[index] = element;
setArray(newElements);
} else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}
return oldValue;
} finally {
lock.unlock();
}
}
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
// 精华还是len既是原数组长度,又是最新添加元素的索引
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
读操作,读是没有加锁的,一直都能读
public E get(int index) {
return get(getArray(), index);
}
看到源码可以知道写入新元素时,首先会先将原来的数组拷贝一份得到新数组,新数组里的元素和旧数组的元素一样并且长度比旧数组多一个长度(新增时),然后将新加入的元素放置在新数组最后一个位置后,用新数组的地址替换掉老数组的地址就能得到最新的数据了。
在我们执行替换地址操作之前,读取的是老数组的数据,数据是有效数据;执行替换地址操作之后,读取的是新数组的数据,同样也是有效数据,而且使用该方式能比读写都加锁要更加的效率。
LinkedHashMap经典用法
LinkedHashMap除了可以保证迭代顺序外,还有一个非常有用的用法: 可以轻松实现一个采用了FIFO替换策略的缓存。具体说来,LinkedHashMap有一个子类方法protected boolean removeEldestEntry(Map.Entry<K,V> eldest)
,该方法的作用是告诉Map是否要删除“最老”的Entry,所谓最老就是当前Map中最早插入的Entry,如果该方法返回true
,最老的那个元素就会被删除。在每次插入新元素的之后LinkedHashMap会自动询问*removeEldestEntry()*是否要删除最老的元素。这样只需要在子类中重载该方法,当元素个数超过一定数量时让removeEldestEntry()返回true,就能够实现一个固定大小的FIFO策略的缓存。示例代码如下:
/** 一个固定大小的FIFO替换策略的缓存 */
class FIFOCache<K, V> extends LinkedHashMap<K, V>{
private final int cacheSize;
public FIFOCache(int cacheSize){
this.cacheSize = cacheSize;
}
// 当Entry个数超过cacheSize时,删除最老的Entry
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > cacheSize;
}
}
Java中的集合框架有哪些核心接口?
Java中的集合框架定义了一组接口和类,用于存储和操作对象集合。其中,核心接口包括以下几种:
- Collection接口:
- Collection接口是所有集合类的顶级接口,它定义了集合框架的基本操作。
- 包括常用的子接口:List、Set和Queue。
- List接口:
- List接口是有序的集合,可以包含重复元素。
- List接口继承自Collection接口,增加了按照索引访问元素的能力。
- 常见实现类有ArrayList、LinkedList、Vector等。
- Set接口:
- Set接口是无序且不允许包含重复元素的集合。
- Set接口继承自Collection接口,但不保证元素的顺序。
- 常见实现类有HashSet、TreeSet等。
- Queue接口:
- Queue接口代表一个先进先出(FIFO)的队列。
- Queue接口继承自Collection接口,提供了在队列尾部插入元素、从队列头部删除元素等操作。
- 常见实现类有LinkedList、ArrayDeque等。
- Map接口:
- Map接口表示一组键值对的集合,每个键唯一且与一个值关联。
- Map接口不是Collection的子接口,但仍然是集合框架的一部分。
- 常见实现类有HashMap、TreeMap、LinkedHashMap等。
除了上述核心接口外,集合框架还包括一些其他的接口和类,如Iterator接口、Iterable接口、ListIterator接口等。这些接口和类提供了对集合的迭代、遍历等操作。Java集合框架为开发者提供了丰富而灵活的数据结构和操作方法,使得在编写Java程序时能够更加高效地管理和操作集合数据。
List操作的一些常见问题
1. 并发修改异常(ConcurrentModificationException):
当使用迭代器或增强 for 循环遍历 List 时,如果在遍历过程中修改了 List 的结构(如添加或删除元素),就会抛出并发修改异常。解决方法是使用迭代器的 remove() 方法进行安全地删除元素,或者使用 ListIterator 迭代器。
在集合被修改时,会比较expectedModCount和modCount的值,如果不一致,则会触发fail-fast机制,抛出ConcurrentModificationException一个expectedModCount属性:这个迭代器预期,该集合被修改的次数一个modCount属性:该集合实际被修改的次数。
2. 索引越界异常(IndexOutOfBoundsException):
在访问 List 中的元素时,如果索引超出了有效范围,就会抛出索引越界异常。解决方法是在访问元素之前先检查索引的有效性,或者使用带有范围检查的方法,如 get(index)。
3. 空指针异常(NullPointerException):
当 List 中的元素为 null 时,如果没有进行空值检查就调用了该元素的方法或属性,就会抛出空指针异常。解决方法是在访问元素之前先进行空值检查,避免空指针异常的发生。
4. 集合的遍历和操作效率问题:
在对 List 进行遍历和操作时,需要考虑到不同方法的效率问题。例如,增强 for 循环、普通 for 循环、迭代器等方法的效率可能不同,需要根据具体情况选择合适的方法。
5. 删除元素导致后续元素位置变化问题:
当删除 List 中的某个元素时,后续元素的位置会发生变化,可能会影响到遍历或其他操作的结果。解决方法是使用迭代器的 remove() 方法安全地删除元素,或者使用倒序遍历删除元素。
6. 集合的线程安全性问题:
在多线程环境下,对 List 进行操作可能会导致线程安全性问题。解决方法是使用线程安全的 List 实现类,如 CopyOnWriteArrayList,或者在对 List 进行操作时使用同步机制保证线程安全。
7. 集合中元素重复或顺序问题:
当 List 中的元素需要保持唯一性或特定顺序时,可能需要对元素进行去重或排序操作。解决方法是使用 Set 来保持元素唯一性,或者使用 Collections.sort() 方法对 List 进行排序。
8. ArrayList的subList方法
该方法主要用于返回一个集合中的一段、可以理解为截取一个集合中的部分元素,返回值是一个List
(1)视图和原List相互影响
1、对父(sourceList)子(subList)List做的非结构性修改(non-structural changes),都会影响到彼此
2、对子List做结构性修改,操作同样会反映到父List上
3、对父List做结构性修改,会抛出异常ConcurrentModificationException
(2)ClassCastException异常原因:
1、调用subList方法,返回一个视图(ArrayList中的SubList内部类)
2、调用subList方法的时候,会通过调用ArrayList中的SubList内部类的构造函数创建一个SubList,没有重新创建一个List,而是直接引用了原有的List,只是指定了元素的使用范围而已(从fromIndex(包含),到toIndex(不包含))。
3、SubList只是ArrayList的内部类,他们之间并没有继承关系,故无法直接进行强制类型转换
如何删除HashMap元素?
推荐使用 removeIf() 方法或者使用 Stream API 进行删除,因为它们更加简洁、高效且安全。如果需要同时迭代和删除元素,建议使用 Iterator 迭代器。避免使用增强 for 循环或者 forEach 循环直接删除元素,因为可能会导致并发修改异常。
1. 使用增强 for 循环删除
这种方法比较简单直观,但是在遍历过程中直接删除元素可能会导致 ConcurrentModificationException 异常。
Map<String, Integer> map = new HashMap<>(); // 添加元素...
for (String key : map.keySet()) {
if (someCondition) {
map.remove(key);
}
}
2. 使用 forEach 循环删除
这种方法类似于增强 for 循环,但是在 Java 8 中引入了 forEach 方法,可以使用 Lambda 表达式更加优雅地遍历和操作集合,但是同样可能导致 ConcurrentModificationException 异常。
Map<String, Integer> map = new HashMap<>(); // 添加元素...
map.forEach((key, value) -> {
if (someCondition) {
map.remove(key);
}
});
3. 使用 Iterator 迭代器删除
使用 Iterator 迭代器遍历 HashMap 并删除元素是一种常见的做法,因为 Iterator 的 remove() 方法可以安全地删除元素。
Map<String, Integer> map = new HashMap<>(); // 添加元素...
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = iterator.next();
if (someCondition) {
iterator.remove();
}
}
4. 使用 removeIf 删除(推荐使用)
Java 8 引入了 removeIf() 方法,可以更加简洁地删除满足条件的元素。
Map<String, Integer> map = new HashMap<>(); // 添加元素...
map.entrySet().removeIf(entry -> someCondition);
5. 使用 Stream 删除(推荐使用)
也可以使用 Stream API 来处理并删除元素,这种方式更加灵活和强大。
Map<String, Integer> map = new HashMap<>(); // 添加元素...
map = map.entrySet().stream()
.filter(entry -> !someCondition)
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
HashMap 和 Hashtable 有什么区别?
1. 两者父类不同
- HashMap是继承自AbstractMap类
- Hashtable是继承自Dictionary类
- 都实现了同时实现了map、Cloneable(可复制)、Serializable(可序列化)这三个接口
2. 安全性不同
- HashMap 在多线程并发的环境下,线程是不安全的,效率远远高于Hashtable
- Hashtable在多线程并发的环境下,线程是安全的,它的每个方法上都有synchronized 关键字
3. 对null的支持不同
- HashMap允许键和值都为null,
- Hashtable不允许键或值为null。
- 如果尝试将null作为键或值存入Hashtable,将会抛出NullPointerException。
4. 初始容量大小和每次扩充容量大小不同
- Hashtable 的初始长度是 11,之后每次扩充容量变为之前的2n+1(n 为上一次的长度)
- HashMap 的初始长度为 16,之后每次扩充变为原来的两倍(位与)
5. 对外提供的接口不同
- Hashtable比HashMap多提供了elments() 和contains() 两个方法。
- elements() 返回此Hashtable中的value的枚举
- contains(V) 判断该Hashtable是否包含传入的value。作用与hashtable的containsValue()一致
Comparator 与 Comparable 有什么区别?
1. 实现Comparable 自然排序
**实现方式:**实现Comparable接口,重写compareTo方法,用于对象之间的比较
Collections.sort(List list) 参与排序的对象需实现comparable接口,缺点会入侵代码
public class Student implements Comparable<Student>{
private String name;
private int age;
@Override
public int compareTo(Student o) {
int flag = this.name.compareTo(o.name);
if(flag == 0) {
flag = this.age - o.age;
}
return flag;
}
}
Collections.sort(students);
2. 借助Comparator 比较器排序
**实现方式:**实现Comparator接口,重写compare方法,用于比较没有实现Comparable的类的对象
Collections.sort(List list,Comparator c) 需编写匿名内部类,优点不用修改排序对象代码
public class Student {
private String name;
private int age;
}
Collections.sort(students, (o1, o2) -> {
int flag = o1.getName().compareTo(o2.getName());
if(flag == 0) {
flag = o1.getAge() - o2.getAge();
}
return flag;
});
Collections.sort(
students,
Comparator.comparing(Student::getName).thenComparingInt(Student::getAge));
说说你对Lambda表达式的理解
Lambda表达式是Java 8引入的一种新特性,它提供了一种简洁、清晰的语法来表示匿名函数,使得代码更加简洁易读。Lambda表达式的主要作用是简化函数式接口的使用,它可以替代匿名内部类的写法,并且使得函数式编程更加方便。
1. 简洁性:
Lambda表达式可以用更简洁的方式来表示匿名函数,减少了冗余的代码,提高了代码的可读性和可维护性。相比于传统的匿名内部类,Lambda表达式的语法更加简洁明了。
2. 函数式编程:
Lambda表达式是函数式编程的一种重要特性,它可以使Java更接近函数式编程的范式。通过Lambda表达式,可以将函数作为参数传递给其他方法,或者在集合类的操作中使用函数式接口的方法,如Stream API中的各种操作方法。
3. 代码可读性:
Lambda表达式可以使代码更加易读,尤其是对于简单的操作,Lambda表达式可以减少冗余代码,使得代码更加清晰明了。Lambda表达式使得代码更加接近自然语言,更容易理解其意图。
4. 实现原理:
Lambda表达式是通过函数式接口来实现的,函数式接口是一个只有一个抽象方法的接口。Lambda表达式可以推断出函数式接口的抽象方法的参数类型和返回类型,并且可以通过上下文推断Lambda表达式的参数类型,从而省略参数类型的声明。
// 传统的匿名内部类写法
Runnable r1 = new Runnable() {
@Override
public void run() {
System.out.println("Hello World");
} };
// Lambda表达式写法
Runnable r2 = () -> System.out.println("Hello World");
怎么理解Java里面的双冒号::
在 Java 中,双冒号 :: 是方法引用(Method Reference)运算符,用于引用方法而不是调用方法。它可以简化代码,使得代码更加简洁和易读。
双冒号 :: 主要用于以下几种情况:
静态方法引用: 可以引用静态方法。语法为 类名::静态方法名。
java// 静态方法 public class Example { public static void print(String str) { System.out.println(str); } public static void main(String[] args) { // 静态方法引用 Consumer<String> consumer = Example::print; consumer.accept("Hello"); } }
实例方法引用: 可以引用实例方法。语法为 对象名::实例方法名。
java// 实例方法 public class Example { public void print(String str) { System.out.println(str); } public static void main(String[] args) { Example example = new Example(); // 实例方法引用 Consumer<String> consumer = example::print; consumer.accept("Hello"); } }
构造方法引用: 可以引用构造方法。语法为 类名::new。
java// 构造方法 public class Example { private String str; public Example(String str) { this.str = str; } public static void main(String[] args) { // 构造方法引用 Supplier<Example> supplier = Example::new; Example example = supplier.get(); System.out.println(example.str); // 这会导致编译错误,因为找不到匹配的无参构造方法 } }
需要配合函数式接口
javapublic class Example { private String str; public Example(String str) { this.str = str; } public static void main(String[] args) { // 使用Function接口匹配带String参数的构造方法 Function<String, Example> constructor = Example::new; Example example = constructor.apply("Hello"); System.out.println(example.str); // 输出Hello } }