Java基础面试笔记
2025-10-20 12:40:03 0 举报
AI智能生成
Java基础面试笔记
作者其他创作
大纲/内容
并发编程
Java内存模型(JMM)
JMM是什么
- JMM是Java内存模型,计算机内存架构的抽象概念(并不实际存在),是为了解决并发场景下可能产生的缓存一致性问题、处理器优化而进行指令重排序产生的系列问题所定义的抽象模型。JSR-133:Java内存模型与线程规范。
为什么会有JMM
- 背景
1、Java程序本质是运行在物理机之上,依赖CPU的运算,而绝大多数情况下CPU的运算都依赖存储设备,即会与内存交互(读写数据)。
2、现代计算机发展至今,CPU的运算速度与内存的运算速度仍然存在几个数量级的差距,为了让CPU运算时无需等待内存缓慢的读写,所以加入高速缓存来屏蔽CPU对内存的直接依赖(每个CPU都有自己的高速缓存,共享同一个内存;运算时将数据复制到缓存,运算结束再将缓存中的数据同步回内存),以达到提升计算性能的目的。
- 问题
3、但加入高速缓存后,在多任务处理的并发场景下又出现了缓存一致性问题,为了解决这一问题,处理器要遵循缓存一致性协议来进行读写操作,但不同的硬件厂商对于缓存一致性处理协议有差异。
4、另外处理器为了达到更好的运行效率,在保证代码运行结果正确的前提下,可能会对代码进行乱序执行优化(指令重排序),即代码实际执行顺序可能与代码编写顺序不一致。
- 解决
5、基于以上问题Java定义了JMM抽象模型:
1)规范了程序中变量的读写访问规则、虚拟机中变量存储到内存和从内存中取出变量这样的底层细节,保证数据的可见性和程序的有序性;
2)屏蔽了不同硬件与操作系统之间的访问差异(在特定的操作协议下,对特定的内存或高速缓存进行读写访问的过程抽象),让Java程序在各种平台下都能达到一致的内存访问效果,这也是Java程序一次编译到处运行的体现之一。
可见性和有序性的保证
- 可见性(Visibility)
JMM通过Happens-Before关系来保证可见性。Happens-Before关系是一种在多线程程序中定义操作执行顺序的规则。如果一个操作A Happens-Before另一个操作B,那么A的结果对于B是可见的。通过这种关系,JMM确保在一个线程中的写操作对于后续对该变量的读操作是可见的。这样可以避免数据的脏读和数据的不一致性。 - 有序性(Ordering)
JMM通过As-If-Serial语义和Happens-Before关系来保证有序性。As-If-Serial语义指的是,程序在单线程执行时的结果必须与按顺序执行的结果一致。也就是说,JMM允许对操作进行重排序,但是保证程序的执行结果与按照代码顺序执行的结果一致。Happens-Before关系则规定了一些操作之间的顺序关系,从而限制了重排序行为,确保程序的执行顺序符合预期。
JMM定义的一系列规范
1、所有变量都存储在主内存中。
2、每条线程都有自己的工作内存,线程的工作内存中保存了主内存中共享变量的副本。
3、线程对变量的所有操作(读/写)都必须在工作内存中进行,而不能直接读写主内存中的数据。
4、不同的线程之间也无法直接访问对方工作内存中的变量,线程间变量值的传递均需要通过主内存来完成。
1、所有变量都存储在主内存中。
2、每条线程都有自己的工作内存,线程的工作内存中保存了主内存中共享变量的副本。
3、线程对变量的所有操作(读/写)都必须在工作内存中进行,而不能直接读写主内存中的数据。
4、不同的线程之间也无法直接访问对方工作内存中的变量,线程间变量值的传递均需要通过主内存来完成。
主内存与工作内存之间具体的交互协议,JMM中定义了8种操作来完成
- lock(锁定):作用于主内存的变量,它把一个变量标识为一条线程独占的状态(如果对一个变量执行lock操作,那将会清空工作内存中此变量的值)。
- unlock(解锁):作用于主内存的变量,它把一个处于锁定状态的变量释放出来,释放后的变量才可以被其他线程锁定(对一个变量执行unlock操作之前,必须先把此变量同步回主内存中)。
- read(读取):作用于主内存的变量,它把一个变量的值从主内存传输到线程的工作内存中,以便随后的load动作使用。
- load(载入):作用于工作内存的变量,它把read操作从主内存中得到的变量值放入工作内存的变量副本中。
- use(使用):作用于工作内存的变量,它把工作内存中一个变量的值传递给执行引擎,每当虚拟机遇到一个需要使用变量的值的字节码指令时将会执行这个操作。
- assign(赋值):作用于工作内存的变量,它把一个从执行引擎接收的值赋给工作内存的变量,每当虚拟机遇到一个给变量赋值的字节码指令时执行这个操作。
- store(存储):作用于工作内存的变量,它把工作内存中一个变量的值传送到主内存中,以便随后的write操作使用。
- write(写入):作用于主内存的变量,它把store操作从工作内存中得到的变量的值放入主内存的变量中。
volatile
volatile关键字遵循happens-before原则,用于确保变量的更新对所有线程都是可见的,并防止指令重排序,从而在多线程编程中实现正确的同步和协作,是多线程环境中确保变量的可见性和一定程度的有序性的手段。但volatile不提供操作的原子性,复杂同步场景可能需要配合synchronized块或java.util.concurrent包中的原子类来使用。
- 保证变量的可见性
1、当写一个volatile变量时,线程首先在自己的工作内存中更新 volatile 变量的值。
2、JVM插入一个写内存屏障,确保所有在写 volatile 变量之前的操作都不会被重排序到写操作之后。
3、变更后的 volatile 变量的值被同步回主内存中。
4、同步回主内存的操作会触发(CPU)缓存一致性协议的总线嗅探机制,使其他线程工作内存中该volatile变量的副本失效,当其他线程尝试访问这个volatile变量时,它们将不得不从主内存中重新读取最新值。 - 保证部分有序性(i++除外)
1、当写入volatile变量时,JVM会在写操作后插入一个写内存屏障(Store Barrier),确保对该volatile变量的写操作在任何后续的内存写操作之前完成,在之前的所有普通写操作(对普通变量的写操作)都不会被重排序到这个volatile写操作之后。
2、当读取volatile变量时,JVM会在读操作前插入一个读内存屏障(Load Barrier),确保对该volatile变量的读操作在任何后续的内存读操作之前完成,在之后的所有普通读操作都不会被重排序到这个volatile读操作之前。
非volatile修饰的变量
- 多线程环境下,对共享变量的修改最终可能会对其他线程可见,但是这个“最终”是不可预测的。当需要确保一个变量的更改对所有线程立即可见时,使用volatile是必要的。这不仅仅是关于性能,更重要的是关于程序的正确性和可预测性。在多线程环境中应该始终假设代码会在最不利的条件下运行,并使用适当的同步机制来保证线程安全。
内存屏障
- 内存屏障是一种CPU指令,使得处理器或编译器在对内存进行操作时按照预定的顺序执行指令的机制,确保某些操作的执行顺序符合预期。
缓存一致性协议
总线嗅探机制
- 为了保证数据的一致性,许多现代处理器都实现了某种形式的缓存一致性协议,例如著名的MESI协议(修改、独占、共享、无效)。这些协议确保了一个核心对数据的修改能够及时地传播到其他核心。
总线嗅探机制
- 总线嗅探机制是缓存一致性协议的一部分,它允许各种缓存之间检测到对共享数据的写操作,并相应地更新它们的缓存行。
AQS
AbstractQueuedSynchronizer(抽象的队列同步器),是一个用于构建锁和其他同步组件的框架。它使用一个 int 成员变量来表示同步状态,并通过内置的 FIFO 队列来管理那些阻塞的线程。
AbstractQueuedSynchronizer核心抽象类
关键属性:
static final class Node(AQS中的静态内部类,用于构造一个双向队列,用来存放等待获取资源的线程)
private transient volatile Node head;(指向队列头节点,通常是一个虚拟的哨兵节点,用于唤醒后续等待的节点)
private transient volatile Node tail;(指向队列尾节点)
private volatile int state;(是一个通用的同步状态表示,其具体含义取决于同步器的具体实现,在不同的同步器实现中,state字段的具体含义可能会有所不同)
关键属性:
static final class Node(AQS中的静态内部类,用于构造一个双向队列,用来存放等待获取资源的线程)
private transient volatile Node head;(指向队列头节点,通常是一个虚拟的哨兵节点,用于唤醒后续等待的节点)
private transient volatile Node tail;(指向队列尾节点)
private volatile int state;(是一个通用的同步状态表示,其具体含义取决于同步器的具体实现,在不同的同步器实现中,state字段的具体含义可能会有所不同)
- 独占锁:对于简单的独占锁(比如ReentrantLock、ReadWriteLock的写锁),state通常是0或1,0:没有线程占用锁,1:有线程占用锁。
- 可重入锁:对于可重入锁,state字段表示一个线程获取锁的次数。这意味着,如果一个线程重复获取了锁,state的值会增加,而不仅仅是1。
- 共享锁:在共享锁(比如ReadWriteLock的读锁或Semaphore)中,state可以表示当前可用的共享资源数量。例如,对于Semaphore,state可能表示当前可用的许可数量,而不是简单的0或1。
- 其他同步器:对于其他类型的同步器,比如CountDownLatch或CyclicBarrier,state的含义也会根据它们的具体实现而有所不同。例如,在CountDownLatch中,state表示倒数计数,而在CyclicBarrier中,它可能表示等待线程的数量。
Node静态内部类(在AQS内部声明)
关键属性:
volatile int waitStatus;(记录当前节点的等待状态)
volatile Node next;(指向后一个节点,尾节点该值为null)
volatile Thread thread;(当前该节点上等待的线程)
关键属性:
volatile int waitStatus;(记录当前节点的等待状态)
- CANCELLED (1): 表示因为超时或中断,节点被取消了,节点的线程不再等待锁。一旦设置为此状态,节点将保持此状态不变。
- SIGNAL (-1): 表示后继节点的线程需要在当前节点的线程释放锁或者取消时被唤醒。也就是说,当前节点的线程释放锁后,将会通知后继节点的线程。
- CONDITION (-2): 表示节点在条件队列中等待。条件队列是AQS中另一种类型的队列,用于实现Condition接口,它允许线程以特定条件等待和唤醒。
- PROPAGATE (-3): 仅在共享模式下使用,表示下一个共享模式的节点应该无条件地传播。
- 0: 初始状态,表示当前节点在等待队列中,但其后继节点的线程不需要被唤醒或者没有设置其他状态。
volatile Node next;(指向后一个节点,尾节点该值为null)
volatile Thread thread;(当前该节点上等待的线程)
CLH队列
AQS使用的队列是基于CLH锁的变体,是一个先进先出的双向队列。传统的CLH锁中,线程节点表示的是自旋锁的状态,而且是一个单向链表。
AQS的队列和传统的CLH队列的主要区别在于:
AQS使用的队列是基于CLH锁的变体,是一个先进先出的双向队列。传统的CLH锁中,线程节点表示的是自旋锁的状态,而且是一个单向链表。
AQS的队列和传统的CLH队列的主要区别在于:
- AQS的队列是双向的,而传统的CLH队列是单向的。
- AQS的队列中的节点包含了被阻塞的线程的引用,而在传统的CLH队列中,线程不会阻塞,而是自旋等待状态变化。
- AQS支持条件变量,允许线程在特定条件下等待,而CLH锁是一个简单的自旋锁。
关键方法:AQS提供了一系列被子类覆盖的保护方法,用于实现同步器的获取和释放逻辑:
tryAcquire(int arg):尝试获取资源,成功则返回true,失败则返回false。
tryRelease(int arg):尝试释放资源,成功则返回true,失败则返回false。
tryAcquireShared(int arg):尝试获取共享资源。
tryReleaseShared(int arg):尝试释放共享资源。
tryAcquire(int arg):尝试获取资源,成功则返回true,失败则返回false。
tryRelease(int arg):尝试释放资源,成功则返回true,失败则返回false。
tryAcquireShared(int arg):尝试获取共享资源。
tryReleaseShared(int arg):尝试释放共享资源。
队列操作:AQS还提供了一系列用于操作同步队列的方法,例如:
enq(Node node):将节点加入队列尾部。
addWaiter(Node mode):将当前线程包装成节点并加入队列。
acquireQueued(Node node, int arg):在队列中等待获取资源。
enq(Node node):将节点加入队列尾部。
addWaiter(Node mode):将当前线程包装成节点并加入队列。
acquireQueued(Node node, int arg):在队列中等待获取资源。
LockSupport
一个线程阻塞工具类,底层由Unsafe类中的native方法实现,是线程等待/唤醒机制(wait/notify)的增强版,是用来创建锁和其他同步类的基本线程阻塞原语。
park()、unpark(Thread thread)用于对线程进行阻塞和解除阻塞操作,无需在锁块中使用。每个使用LockSupport的线程都会关联一个许可证(permit),permit默认0,最大为1。
一个线程阻塞工具类,底层由Unsafe类中的native方法实现,是线程等待/唤醒机制(wait/notify)的增强版,是用来创建锁和其他同步类的基本线程阻塞原语。
park()、unpark(Thread thread)用于对线程进行阻塞和解除阻塞操作,无需在锁块中使用。每个使用LockSupport的线程都会关联一个许可证(permit),permit默认0,最大为1。
- unpark()用于发放许可证(解锁)
可以在park()前被调用,提前给某线程发放许可证,重复调用,对某线程许可证数量的影响最大也是1。 - park()用于消费许可证(加锁)
线程运行到park()时,如果当前线程没有许可证则阻塞(permit=0),如果有许可证则消费掉许可证并继续执行(permit=1)。
从ReentrantLock分析
ReentrantLock默认实现非公平锁,可以通过构造器参数修改
高并发情况下可能会导致显著的性能差异:非公平锁通常有更高的吞吐量,因为它减少了上下文切换和队列管理的开销,但可能会导致等待时间较长的线程出现“饥饿”现象。公平锁则提供了更加均匀的线程调度,但可能以降低吞吐量为代价。
- NonfairSync:(默认false)非公平锁,继承自Sync
在尝试获取锁时不会检查等待队列,而是直接尝试抢占锁。如果锁恰好是可用的,新来的线程可能会立即获取锁,即使有其他线程已经在等待队列中等待了一段时间。只有在新来的线程未能获取锁时,它才会加入到等待队列的尾部。 - FairSync:(true)公平锁,继承自Sync(区别:加锁时通过hasQueuedPredecessors()判断等待队列中是否有线程在等待,有则进入队列)
在线程获取锁时会先检查等待队列,如果队列中已经有线程在等待,即使锁在当前时刻是可用的,新来的线程也不会直接获取锁,而是会加入到队列中等待,这样做确保了按照请求锁的顺序来依次分配锁,从而实现了公平性。
高并发情况下可能会导致显著的性能差异:非公平锁通常有更高的吞吐量,因为它减少了上下文切换和队列管理的开销,但可能会导致等待时间较长的线程出现“饥饿”现象。公平锁则提供了更加均匀的线程调度,但可能以降低吞吐量为代价。
3个线程并发
抢占非公平锁
1、T1尝试加锁,通过CAS修改state值为1
2、成功,抢占到资源
2、成功,抢占到资源
1、T2尝试加锁,通过CAS修改state值为1
2、失败(当前锁已被T1抢占),判断CLH队列是否为空,不为空则将T2加入到队列尾部
3、队列为空,则先创建一个空的Node做为头节点(等同于当前占用锁的线程节点),同步器的头尾节点都指向该节点
4、再创建T2线程Node加入到队列尾部
5、判断T2节点前指针是否指向头节点(这表示除头节点外,T2就是抢占锁优先级最高的节点),是则再次尝试抢占锁
6、抢锁失败,进行LockSupport.park()阻塞
2、失败(当前锁已被T1抢占),判断CLH队列是否为空,不为空则将T2加入到队列尾部
3、队列为空,则先创建一个空的Node做为头节点(等同于当前占用锁的线程节点),同步器的头尾节点都指向该节点
4、再创建T2线程Node加入到队列尾部
5、判断T2节点前指针是否指向头节点(这表示除头节点外,T2就是抢占锁优先级最高的节点),是则再次尝试抢占锁
6、抢锁失败,进行LockSupport.park()阻塞
1、T3尝试加锁,通过CAS修改state值为1
2、失败(当前锁已被T1抢占),此时队列已被T2初始化过不为空,将T3加入到队列尾部
2、失败(当前锁已被T1抢占),此时队列已被T2初始化过不为空,将T3加入到队列尾部
释放锁
1、T1运行结束,将state修改为0,资源占用线程指向null,通知队列中当前优先级最高的T2线程节点unpark
2、T2修改state为1,抢占到资源
3、同步器头节点指向原来的T2节点,将队列中T2线程引用指向null,前指针指向null
4、将队列中原来的头节点next指向null(等待GC)
5、此时队列中原来的T2节点作为头节点(哨兵节点)
2、T2修改state为1,抢占到资源
3、同步器头节点指向原来的T2节点,将队列中T2线程引用指向null,前指针指向null
4、将队列中原来的头节点next指向null(等待GC)
5、此时队列中原来的T2节点作为头节点(哨兵节点)
虚拟head初始化时机
首次使用时初始化:具体来说,当第一个线程尝试获取同步状态(例如,尝试获取锁)但失败时,它会被加入到等待队列中。在这个加入队列的过程中,如果发现头节点为null(实际上判断的是tail节点是否为null),AQS会初始化一个虚拟的头节点。这个操作发生在addWaiter(Node mode)方法的enq(node)中,这个方法负责将当前线程封装成一个节点(Node)并添加到队列中。如果队列为空(即头节点为null),则会创建一个新的Node作为头节点,然后将当前线程的节点作为头节点的后继节点。
首次使用时初始化:具体来说,当第一个线程尝试获取同步状态(例如,尝试获取锁)但失败时,它会被加入到等待队列中。在这个加入队列的过程中,如果发现头节点为null(实际上判断的是tail节点是否为null),AQS会初始化一个虚拟的头节点。这个操作发生在addWaiter(Node mode)方法的enq(node)中,这个方法负责将当前线程封装成一个节点(Node)并添加到队列中。如果队列为空(即头节点为null),则会创建一个新的Node作为头节点,然后将当前线程的节点作为头节点的后继节点。
为什么需要一个虚拟的head节点?
虚拟头节点简化了队列的操作逻辑,提高了执行效率,例如,它使得插入和移除操作不需要进行特殊的空检查,因为队列永远不会完全为空(至少有一个虚拟头节点)。
虚拟头节点简化了队列的操作逻辑,提高了执行效率,例如,它使得插入和移除操作不需要进行特殊的空检查,因为队列永远不会完全为空(至少有一个虚拟头节点)。
CAS
Compare And Swap(比较并交换),是一条CPU并发源语,原语的执行必须是连续的,在执行过程中不允许中断,也就是说CAS是一条原子指令,不会造成所谓的数据不一致的问题。
这种操作涉及三个操作数:内存值V、旧的预期值A、要更新的值B,当且仅当内存值V的值等于旧的预期值A时才会将内存值V的值修改为B,否则什么都不干。CAS操作是非阻塞同步机制的核心,相对于传统的锁机制,CAS可以在不阻塞线程的情况下提供线程安全性,从而在某些情况下提高性能。
这种操作涉及三个操作数:内存值V、旧的预期值A、要更新的值B,当且仅当内存值V的值等于旧的预期值A时才会将内存值V的值修改为B,否则什么都不干。CAS操作是非阻塞同步机制的核心,相对于传统的锁机制,CAS可以在不阻塞线程的情况下提供线程安全性,从而在某些情况下提高性能。
优点:避免加互斥锁、提高程序运行效率。
缺陷:
缺陷:
- 自旋时间可能很长,消耗CPU。
解决方式:并发不算太高的时候选择CAS,本身乐观锁就是假设冲突不多。 - 线程安全的范围不能灵活控制、CAS操作的是单个对象,不能同时保证多个对象的原子性。
解决方案:利用一个新的类,来整合刚才这一组共享变量,这个新的类中的多个成员变量就是刚才的那多个共享变量,然后再利用 atomic 包中的 AtomicReference 来把这个新对象整体进行 CAS 操作,这样就可以保证线程安全。
ABA问题
使用 CAS 会产生 ABA 问题,这是因为 CAS 算法是在某一时刻取出内存值然后在当前时刻进行比较,中间存在一个时间差,在这个时间差里就可能会产生 ABA 问题。(ABA 问题的过程是当有两个线程 T1 和 T2 从内存中获取到值A,线程 T2 通过某些操作把内存值修改为B,然后又经过某些操作将值修改为回值A,T2退出。线程 T1 进行操作的时候,使用预期值同内存中的值比较,此时均为A,修改成功退出。但是此时的A已经不是原先的A了,这就是 ABA 问题。)
解决方案:AtomicStampedReference增加版本号
使用 CAS 会产生 ABA 问题,这是因为 CAS 算法是在某一时刻取出内存值然后在当前时刻进行比较,中间存在一个时间差,在这个时间差里就可能会产生 ABA 问题。(ABA 问题的过程是当有两个线程 T1 和 T2 从内存中获取到值A,线程 T2 通过某些操作把内存值修改为B,然后又经过某些操作将值修改为回值A,T2退出。线程 T1 进行操作的时候,使用预期值同内存中的值比较,此时均为A,修改成功退出。但是此时的A已经不是原先的A了,这就是 ABA 问题。)
解决方案:AtomicStampedReference增加版本号
- 如果CAS操作只需要保证最终的值没有变化,不关心中间状态,那么ABA问题不是关注点。
- 如果CAS操作依赖于值的历史不变性,或者这个值的变化代表了更复杂的状态变化,那么您需要关心ABA问题,并可能需要采取措施来解决它,例如通过使用版本号或其他机制来跟踪值的变化历史。
线程
什么是线程安全
创建线程的方式
- 是编程中的术语,指某个函数、函数库在并发环境中被调用时,能够正确地处理多个线程之间的共享变量,使程序功能正确完成。
创建线程的方式
- 继承Thread类
- 实现Runnable接口
- 实现Callable接口和Future
- 使用线程池Executor
- 使用CompletableFuture
- object.wait() :阻塞线程并释放锁,让持有锁的线程进入等待队列,停在wait()处,被唤醒后继续执行后面代码,object.wait() 必须在 synchronzied 语句中调用。
- object.notify(): 随机唤醒等待队列的一个线程。
- object.notifyAll(): 唤醒等待队列的所有线程。
- join() :t. join()方法阻塞调用此方法的线程,直到线程t完成,调用线程再继续。注:将当前线程“加入”t线程“之后”执行,当前线程在t线程执行期间一直处于等待状态,直至t线程执行完成后被唤醒。Thread.join底层是通过wait/notifyall来实现线程的通信达到线程阻塞的目的;
- yield(): 是线程的“谦让”机制,可以理解为当线程抢到 cpu 资源时,放弃这次资源重新抢占,yield() 是 Thread 里的一个静态方法。
Thread.start()、Thread.run()区别
- run()
仅仅是调用实例方法,run()是同步执行。 - start()
Thread.start()是内部调用了native标记的start0(),该方法是调用本地接口(即外部C++编写的接口),首先是启动线程,然后由JVM通过跨平台的特性,针对不同操作系统来创建线程,Java中的线程是由操作系统提供的。
线程中断的方式
- 调用线程的
stop()
立即停止调用stop()的线程,官方标记过时,不建议使用。
原因:大多数情况是在线程T1中对线程T2进行T2.stop(),而T1并不知道T2内部的执行阶段,这种由外部停止一个线程的方式可能造成T2内部数据不一致或原子性被破坏。 - 定义volatile中断标识
这种方法可以解决一部分问题,但是当线程可能会被阻塞的时候就会出现问题。
原因:比如生产者、消费者模式,如果生产者通过循环往队列里面加元素,在每次循环之前都要判断中断标志位,如果结束了就不往队列中put数据了,当消费者在某些情况下可能停止消费数据并设置标志位为已结束。此时如果阻塞队列是满的导致生产者在put阻塞中,由于消费者不再消费,生产者线程就会永远处于阻塞状态。 - 使用interrupt
interrupt():不会真正的中断一个正在运行的线程,而只是发出中断请求,会将线程的中断标识设置为true,然后由线程在下一个合适的时刻中断自己,这样才能保证数据结构不会被破坏。
isInterrupted():返回调用线程的中断状态(true:需要中断,flase:不需要中断)。
interrupted():返回调用线程的中断状态,并清除中断状态(设置为flase:不需要中断),该方法是Thread的静态方法。
InterruptedException:当线程进行wait()、sleep()、join()时,必须捕获该异常,该异常触发后当前线程中断状态变更为false。
线程处于阻塞或者等待状态时进行interrupt()中断,就会触发该异常(也可以理解为中断状态为true时就会触发,比如在线程开始时就调用interrupt()将中断状态变更为true),可以在该异常的catch块中对中断进行业务控制或恢复中断。 - Future.cancel()
如果是通过ExecutorService提交的任务,可以使用Future对象的cancel()方法来请求取消任务。如果任务还未开始,它将不会被执行;如果任务已经开始,根据cancel方法的参数,可以选择是否中断正在执行的任务。
状态
- 新建(NEW)
线程已经被创建,但还没有开始执行。也就是说,线程的实例已经被创建(通过new Thread()),但是start()方法还没有被调用。 - 就绪(RUNNABLE)
线程可能正在Java虚拟机中运行,也可能正在等待CPU分配时间片。此状态包括了传统操作系统线程状态中的“就绪”和“运行”两种情况。当调用线程的start()方法后,线程进入可运行状态。 - 阻塞(BLOCKED)
线程因为试图获取一个内部的对象锁(不是由java.util.concurrent库中的锁实现),而该锁被其他线程持有,则该线程进入阻塞状态。当持有锁的线程释放锁后,阻塞状态的线程将有机会进入可运行状态。 - 等待(WAITING)
线程因为调用了以下方法之一而进入等待状态:
不带超时值的Object.wait()
不带超时值的Thread.join()
LockSupport.park()
在等待状态的线程需要等待另一个线程特别地进行通知或中断,才能返回到可运行状态。 - 计时等待(TIMED_WAITING)
线程在指定的等待时间内等待另一个线程的特定操作。它通过调用以下方法之一进入此状态:
带有超时值的Thread.sleep()
带有超时值的Object.wait()
带有超时值的Thread.join()
LockSupport.parkNanos()
LockSupport.parkUntil()
当等待时间结束,或者线程在等待时间内被通知或中断,线程将返回到可运行状态。 - 终止(TERMINATED)
线程的运行已经结束。无论是因为run()方法正常退出,还是因为未捕获的异常导致线程终止,都会使线程进入此状态。
守护线程
- 守护线程(Daemon Thread)也被称为后台线程或服务线程,守护线程是为用户线程服务的,当程序中的用户线程全部执行结束之后,守护线程也会跟随结束(main线程属于用户线程)。通过Thread.setDaemon(true) 将线程设置为守护线程,必须在start()之前。
- 使用场景:
资源清理和回收:例如,JVM的垃圾回收线程就是一个守护线程,负责监控和回收不再使用的对象内存。
后台服务:如日志记录、监控系统状态、定时检查、配置文件的自动重载等,这些服务需要持续运行,但不应阻止程序退出。
其他辅助功能:定时任务、后台数据处理、缓存清理等,这些任务通常不是程序的主要工作流程,但对于应用程序的稳定和性能很重要。
锁
锁类型
- 内置锁(Intrinsic Locks)/监视器锁(Monitor Locks)
使用synchronized关键字实现,每个Java对象都可以作为一个同步锁。这些锁是互斥的,意味着同一时刻只有一个线程可以持有锁。
分为两种形式:同步方法(synchronized method)和同步代码块(synchronized block)。 - 可重入锁(Reentrant Locks)
指同一个线程可以多次获得同一个锁,可重入锁内部维护了一个计数器,当线程首次获得锁时,计数变为1,同一个线程每次获得这个锁,计数加1,每次释放锁时,计数减1,当计数变为0时,锁被完全释放。
(ReentrantLock、ReentrantReadWriteLock、synchronized关键字) - 读写锁(Read-Write Locks)
主要用于提高程序在多线程环境下读操作的性能,分为读锁(共享锁)和写锁(排他锁),允许多个线程同时读取,但写入时需要独占。 - 条件锁(Condition Locks)
与ReentrantLock结合使用,通过ReentrantLock.newCondition()获取Condition实例。允许线程在特定条件下等待(await())或者在条件成立时通知其他线程(signal()或signalAll())。 - 公平锁和非公平锁
公平锁指等待时间最长的线程会优先获取锁。
非公平锁则允许插队,不保证等待时间最长的线程首先获取锁。
ReentrantLock在创建时可以指定是公平锁还是非公平锁。 - 偏向锁、轻量级锁、重量级锁
这些锁是JVM为了优化锁的竞争而实现的锁优化技术。它们并不是通过API直接使用,而是JVM在运行时根据竞争情况自动应用的。
偏向锁针对一个线程多次加锁的情况进行优化;
轻量级锁用于线程交替执行同步块的场景;
重量级锁则是传统的互斥锁,用于有明显竞争的情况。 - 乐观锁和悲观锁
这些锁不是Java语言特有的概念,而是广泛应用于数据库和并发编程中的概念。
乐观锁通常通过版本号机制实现,适用于读多写少的场景,如:版本号机制、CAS机制。
悲观锁假设最坏的情况,即总是假设会发生冲突,因此在访问任何资源之前都会先加锁,如:synchronized和Lock实现都是悲观锁。
synchronized
- 同步方法(Synchronized Method):如果是实例方法,锁是当前实例对象;如果是静态同步方法,锁是当前类的Class对象。在编译后的字节码文件中,会被标记为ACC_SYNCHRONIZED方法。
- 同步代码块(Synchronized Block):锁是括号里面指定的对象。当线程执行完方法或代码块后自动释放锁。字节码层面通过monitorenter和monitorexit控制锁的获取和释放。
- 特性
互斥性:同一时刻,只有一个线程能够执行同步方法或同步代码块内的代码。
可见性:保证一个线程修改的状态对其他线程是可见的。
重入性:同一个线程可以多次获得同一个锁。
- 锁升级
JDK 6引入了锁升级的概念,JVM根据不同的竞争情况动态调整锁状态,在保证线程安全的同时,提高执行效率。这个版本之前synchronized关键字在实现同步时主要依赖于操作系统级别的重量级互斥锁(Mutex),其性能开销相对较大。
1. 无锁状态:在刚开始时,对象处于无锁状态。这时对象头中的Mark Word(对象头标记字段)存储的是对象的基本信息,如哈希码、GC分代年龄等。
2. 偏向锁:当第一个线程访问同步块时,假设没有竞争,JVM会将对象头的状态设置为偏向锁状态,并将偏向锁偏向于该线程。对象头的Mark Word被更新为包含偏向线程ID。此后该线程再次进入同步块时,只需检查Mark Word中的线程ID是否为自己的ID,如果是,就可以直接进入同步块,无需进行额外的同步。
3. 轻量级锁:如果有另一个线程尝试获取这个已经偏向某个线程的锁,偏向锁就不能继续使用了。此时JVM会暂停拥有偏向锁的线程,并撤销偏向锁,将锁升级为轻量级锁。轻量级锁的实现是通过在当前线程的栈帧中创建一个名为锁记录(Lock Record)的空间,用来存储锁对象头的Mark Word的拷贝。通过CAS操作尝试将对象头的Mark Word更新为指向锁记录的指针。如果成功,当前线程获得锁;如果失败,表示有竞争。
4. 重量级锁:当多个线程竞争同一个轻量级锁时,如果CAS操作多次失败,表明有激烈的锁竞争。此时,JVM会将锁升级为重量级锁,以减少线程之间的竞争。轻量级锁升级为重量级锁是通过将对象头的Mark Word指向一个监视器(Monitor)对象,该监视器对象中包含两个队列:Entry Set和Wait Set,用于管理那些尝试进入同步块的线程和调用wait方法的线程。一旦锁升级为重量级锁,进入同步块的线程将会被阻塞,直到锁被释放。
死锁及排查
- 原因:
两个线程都试图获取对方的锁 - 案例:
1、定义两个锁对象Obj1与Obj2
2、启动两个线程A与B
3、A线程中先获取Obj1、再获取Obj2,B线程中先获取Obj2,再获取Obj1 - 排查
1、jps -l:查询进程编号;jstack 进程编号:打印堆栈信息排查
2、jconsole:图形化工具查看-线程-检测死锁 - 提前规避
1、一次性申请所有资源,就不会存在等待的问题
2、尝试几次都无法获取资源时,主动释放自己占用的资源
JUC
同步器
- CountDownLatch
通过一个计数器来实现同步功能,在计数器=0之前,所有线程都阻塞在await()方法处,直到调用countDown()方法将计数器的值减为0时,才继续await()后的逻辑,内部采用共享锁来实现。
与CyclicBarrier区别:CountDownLatch的计数器无法被重置,CyclicBarrier的计数器可以被重置后使用,因此它被称为是循环的barrier。 - CyclicBarrier
它允许一组线程互相等待,直到到达某个公共屏障点(common barrier point),底层采用ReentrantLock + Condition实现。
通俗讲:让一组线程到达一个屏障时被阻塞,直到最后一个线程到达屏障时,屏障才会开门,所有被屏障拦截的线程才会继续干活。
应用场景:多线程结果合并的操作,用于多线程计算数据,最后合并计算结果。 - Semaphore
一个控制访问共享资源的计数器,内部采用共享锁实现。
可以设定一个保护范围,定义同时可以进入范围的线程数,如果占用线程数满了,其他线程需要等待释放许可才能进入保护范围。
应用场景:通常用于限制可以访问某些资源(物理或逻辑的)的线程数目。 - Exchanger
允许在并发任务之间交换数据。具体来说,Exchanger类允许在两个线程之间定义同步点,当两个线程都达到同步点时,可以交换数据,内部使用等待/通知机制来确保数据在两个线程间正确传递。
线程池
通过重复利用已创建的线程降低线程创建和销毁造成的消耗,当任务到达时,任务可以不需要等到线程创建就能立即执行,进行统一分配、调优和监控。
ThreadPoolExecutor
Executors
Executors是一个工具类,提供了静态方法来创建不同类型的线程池,内部实际上是通过调用ThreadPoolExecutor的构造函数来实现。
ScheduledThreadPoolExecutor
线程池工作流程
通过重复利用已创建的线程降低线程创建和销毁造成的消耗,当任务到达时,任务可以不需要等到线程创建就能立即执行,进行统一分配、调优和监控。
ThreadPoolExecutor
- ThreadPoolExecutor是ExecutorService接口的一个实现,是线程池的核心实现类,Executors类中创建线程池的方法内部都是通过调用ThreadPoolExecutor的构造方法来实现。
- 7个参数:
corePoolSize:核心线程数(已创建的核心线程可复用)
maximumPoolSize:最大线程数(包含核心线程数)
keepAliveTime:非核心线程的空闲存活时间
unit:keepAliveTime的单位
workQueue:工作队列
threadFactory:创建线程的工厂
handler:拒绝策略
(AbortPolicy:直接抛出异常(默认策略)
Discard Policy:直接丢弃任务,不作任何处理
DiscardOldestPolicy:丢弃阻塞队列中最早的任务,并执行当前任务
CallerRunsPolicy:用调用者所在的线程来执行任务) - allowCoreThreadTimeOut(boolean value)设置核心线程是否可以被超时回收。
Executors
Executors是一个工具类,提供了静态方法来创建不同类型的线程池,内部实际上是通过调用ThreadPoolExecutor的构造函数来实现。
- newSingleThreadExecutor(单线程的线程池)
1、corePoolSize和maximumPoolSize被设置为1
2、使用“无界”队列LinkedBlockingQueue作为workerQueue
可以保证所有任务都按照FIFO顺序执行,阻塞队列长度过长将导致OOM。 - newFixedThreadPool(可重用固定线程数的线程池)
1、corePoolSize和maximumPoolSize一致
2、使用“无界”队列LinkedBlockingQueue作为workerQueue
核心线程消耗完则后续任务加入到(无界)阻塞队列等待,阻塞队列长度过长将导致OOM。 - newCachedThreadPool(可缓存的线程池)
1、corePoolSize=0、maximumPoolSize=Integer.MAX_VALUE
2、使用“无容量”队列SynchronousQueue,所以每提交一个任务都会申请一个工作线程进行处理
3、线程存活时间60s
可用于处理短期大量突发流量,如果提交任务的速度高于maximumPool中线程处理任务的速度,会不断创建新线程,可能会耗尽CPU和内存资源导致OOM。 - newScheduledThreadPool(延迟周期性的线程池)
1、maximumPoolSize=Integer.MAX_VALUE
2、使用“延时”队列DelayedWorkQueue作为WorkerQueue
可用于实现定时任务调度 - newWorkStealingPool(JDK1.8加入)
实现用到了ForkJoinPool,利用“工作窃取”算法并行处理请求。
ScheduledThreadPoolExecutor
- 继承自ThreadPoolExecutor,实现了ScheduledExecutorService接口。提供了在指定延迟后运行任务,或者定期执行任务的能力。适合需要多次执行任务的场景,例如,定时清理资源、周期性进行数据同步等。通过Executors类提供的newScheduledThreadPool方法可以创建一个ScheduledThreadPoolExecutor的实例。
线程池工作流程
- 当新任务提交到线程池时,如果当前运行的线程数<核心线程数,线程池会创建并启动一个新的核心线程来执行任务。
- 如果当前运行的线程数>=核心线程数,新提交的任务会被加入到工作队列中等待执行。
- 如果工作队列已满,且当前运行的线程数<最大线程数,线程池会创建新的非核心线程来执行任务。
- 当线程池中的线程数达到最大线程数时,新提交的任务将会根据线程池的拒绝策略来处理,例如抛出异常、在调用者线程中执行任务等。
线程池状态
线程池状态的转换流程如下:
- RUNNING(运行中)
线程池可以接受新任务,也可以处理阻塞队列中的任务。
这是线程池的初始状态。 - SHUTDOWN(关闭)
线程池不接受新任务,但可以处理阻塞队列中的任务。
调用shutdown()方法时,线程池会进入这个状态。 - STOP(停止)
线程池不接受新任务,不处理阻塞队列中的任务,并且会中断正在处理的任务。
调用shutdownNow()方法时,线程池会进入这个状态。 - TIDYING(整理)
所有任务都已终止,workerCount(有效线程数)为0,线程池将会转换到TIDYING状态。
在转换到TIDYING状态时,会执行terminated()钩子方法。 - TERMINATED(终止)
terminated()钩子方法完成后,线程池会进入这个状态。
在此状态下,线程池的执行已完全终止。
线程池状态的转换流程如下:
- 线程池创建时,处于RUNNING状态。
- 当调用shutdown()方法时,线程池状态转为SHUTDOWN状态。
- 如果调用shutdownNow()方法,线程池状态立即转为STOP状态。
- 当线程池中正在运行的任务全部完成后,线程池会从SHUTDOWN状态转为TIDYING状态。如果线程池处于STOP状态,一旦所有线程停止执行,也会转为TIDYING状态。
- 在TIDYING状态下,一旦terminated()方法执行完毕,线程池状态会变为TERMINATED状态。
CompletableFuture
- Java 8引入的一个功能强大的异步编程工具,它实现了Future接口和CompletionStage接口。与传统的Future相比,CompletableFuture提供了更灵活的操作,允许以声明式的方式处理异步计算的结果,组合多个异步操作,无需手动管理线程池或等待Future的结果,极大地简化了异步编程的复杂性。
- 使用场景
异步执行长时间运行的任务,而不阻塞当前线程。
组合多个依赖的异步任务。
在异步操作完成时触发某些操作,如回调。
处理异步操作的结果,无论是成功还是异常。
并发集合
ConcurrentHashMap
- 应用场景
需要频繁读写操作的共享数据集。
实现高性能的并发缓存机制。
在多线程环境下作为映射表使用,如统计、监控信息的收集等。
- 底层实现
JDK 1.8之前(数组(Segment数组+HashEntry数组)+链表,Segment继承ReentrantLock实现分段锁)使用分段锁(Segment Locking)技术。整个Map被分为若干段(Segment),每个段就是一个小的哈希表,拥有自己的锁。当需要对Map进行操作时,只需锁定对应段即可,不同段的操作可以并发进行。
JDK 1.8及之后(数组(Node数组)+单向链表/红黑树,CAS + Synchronized节点锁),提高了并发性能。主要改进有:
1、数据结构由Segment[]数组改为Node[]数组,使用链表和红黑树来处理哈希冲突。
2、采用了更细粒度的锁定策略,即仅在链表转红黑树、添加节点时加锁,大幅减少锁竞争。
3、通过CAS操作来实现无锁的读取和更新,进一步提高并发性能。 - put 方法实现流程(JDK 1.8及以后)
计算哈希值:首先计算key的哈希值。
无锁检查:尝试使用CAS操作直接插入节点,如果成功则直接返回。
加锁插入:如果CAS操作失败,说明有其他线程正在操作这个桶(bucket),此时当前线程会锁定这个桶对应的第一个节点,然后再次尝试插入或更新节点。
链表转红黑树:如果链表长度超过阈值(TREEIFY_THRESHOLD,默认为8),则将链表转换为红黑树,以减少搜索时间。 - get 方法实现流程(JDK 1.8及以后)
计算哈希值:计算key的哈希值。
快速访问:直接通过哈希值定位到具体的桶(bucket),然后遍历链表或红黑树查找节点。
返回结果:如果找到对应的节点,则返回节点的值;否则返回null。
get方法的实现主要利用了CAS和volatile读的无锁机制,确保了高效的并发读取,而不需要加锁。
CopyOnWriteArrayList
- Java并发包中的一个线程安全的ArrayList实现,主要作用是避免了ConcurrentModificationException,让列表具备并发操作的能力,通过"写时复制"(Copy-On-Write)技术来实现线程安全,当列表进行修改操作(如添加、删除元素)时,CopyOnWriteArrayList不直接在当前数组上进行修改,而是先复制出一个新的数组,然后在新数组上执行修改,最后将新数组赋值给原数组引用。
- CopyOnWriteArrayList并不能保证数据的实时可见性,因为写操作在数组的副本上进行,直到写操作完成后,这个修改过的副本才会替换原来的数组。因此在写操作完成并且副本替换原数组之前,其他线程的读操作是无法看到这些写操作所做的更改的。
Atomic原子类
- 内部实现利用volatile保证可见性和有序性,利用底层硬件的原子指令CAS来实现对单个变量的原子性更新,避免了使用同步锁的开销。
- 基本类型
AtomicBoolean、AtomicInteger、AtomicLong - 数组类型
AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray - 引用类型
AtomicReference、AtomicStampedReference、AtomicMarkableReference - 字段类型
AtomicIntegerFieldUpdater、AtomicLongFieldUpdater、AtomicReferenceFieldUpdater - 增强类型
LongAdder、DoubleAdder、LongAccumulator、DoubleAccumulator
其他线程工具
ThreadLocal
ThreadLocal提供线程独享的变量,通过get或set操作本线程独享的副本变量,从而避免线程安全问题,为了方便每个线程处理自己的状态而引入的一个机制。
方法
set(T value):将此线程局部变量的当前线程副本中的值设置为指定值
1、获取当前线程ThreadLocalMap,不为null则set值
2、为null,则创建ThreadLocalMap,set值
实际是往ThreadLocalMap设置值,key为ThreadLocal,value为传递进来的对象
2、为null,则创建ThreadLocalMap,set值
实际是往ThreadLocalMap设置值,key为ThreadLocal,value为传递进来的对象
get():返回此线程局部变量的当前线程副本中的值
1、获取当前线程ThreadLocalMap,为null则设置初始值并返回
2、不为null,用当前线程做为key,从ThreadLocalMap中获取Entry
3、从Entry中获取value
实际是从ThreadLocalMap获取值,key为ThreadLocal
2、不为null,用当前线程做为key,从ThreadLocalMap中获取Entry
3、从Entry中获取value
实际是从ThreadLocalMap获取值,key为ThreadLocal
initialValue():返回此线程局部变量的当前线程的“初始值”
1、获取当前线程ThreadLocalMap,不为null则set初始值
2、为null,则创建ThreadLocalMap,初始化Entry(当前线程,初始值)
2、为null,则创建ThreadLocalMap,初始化Entry(当前线程,初始值)
remove():移除此线程局部变量当前线程的值
1、获取当前线程ThreadLocalMap,不为null则remove当前线程对应的key
2、处理脏Entry:寻找脏Entry(key=null的Entry)删除
2、处理脏Entry:寻找脏Entry(key=null的Entry)删除
withInitial(Supplier<? extends S> supplier):创建一个线程局部变量
问题
1、ThreadLocal中ThreadLocalMap的数据结构和关系?
Thread包含ThreadLocal.ThreadLocalMap(ThreadLocal包含ThreadLocalMap静态内部类)
ThreadLocalMap包含Entry静态内部类(继承弱引用)
Thread包含ThreadLocal.ThreadLocalMap(ThreadLocal包含ThreadLocalMap静态内部类)
ThreadLocalMap包含Entry静态内部类(继承弱引用)
2、ThreadLocal的key为什么是弱引用?
ThreadLocalMap的Entry对ThreadLocal的引用为弱引用,避免了ThreadLocal对象无法被回收的问题,会通过expungeStaleEntry、cleanSomeSlots、replaceStaleEntry回收key为null的Entry对象的值,及Entry对象本身从而防止内存泄漏,实现安全加固。
ThreadLocalMap的Entry对ThreadLocal的引用为弱引用,避免了ThreadLocal对象无法被回收的问题,会通过expungeStaleEntry、cleanSomeSlots、replaceStaleEntry回收key为null的Entry对象的值,及Entry对象本身从而防止内存泄漏,实现安全加固。
3、ThreadLocal内存泄漏问题?
在线程池场景下,线程会被复用,(如Integer类型)ThreadLocal变量可能影响后续业务逻辑和造成内存泄漏问题,线程使用完后在try-finally块调用remove方法进行回收。
在线程池场景下,线程会被复用,(如Integer类型)ThreadLocal变量可能影响后续业务逻辑和造成内存泄漏问题,线程使用完后在try-finally块调用remove方法进行回收。
最佳实践
1、初始化:ThreadLocal.withInitial(()->0);
2、static修饰:ThreadLocal实现线程的数据隔离,不在于自己本身,而在于ThreadLocalMap,所以ThreadLocal声明为static
3、使用后remove
2、static修饰:ThreadLocal实现线程的数据隔离,不在于自己本身,而在于ThreadLocalMap,所以ThreadLocal声明为static
3、使用后remove
Fork/Join
一个用于并行执行任务的框架,是一个把大任务分割成若干个小任务,最终汇总每个小任务结果后得到大任务结果的框架
核心思想
“分治”
fork分解任务,join收集数据
工作窃取
某个线程从其他队列里窃取任务来执行
执行块的线程帮助执行慢的线程执行任务,提升整个任务效率
队列要采用双向队列
核心类
ForkJoinPool
执行任务的线程池
ForkJoinTask
表示任务,用于ForkJoinPool的任务抽象
ForkJoinWorkerThread
执行任务的工作线程
阻塞队列
ArrayBlockingQueue
一个由数组实现的FIFO有界阻塞队列
ArrayBlockingQueue有界且固定,在构造函数时确认大小,确认后不支持改变
在多线程环境下不保证“公平性”
实现
ReentrantLock
Condition
LinkedBlockingQueue
基于链接,无界的FIFO阻塞队列
PriorityBlockingQueue
支持优先级的无界阻塞队列
默认情况下元素采用自然顺序升序排序,可以通过指定Comparator来对元素进行排序
二叉堆
分类
最大堆
父节点的键值总是大于或等于任何一个子节点的键值
最小堆
父节点的键值总是小于或等于任何一个子节点的键值
添加操作则是不断“上冒”,而删除操作则是不断“下掉”
实现
ReentrantLock + Condition
二叉堆
DelayQueue
支持延时获取元素的无界阻塞队列
应用
缓存:清掉缓存中超时的缓存数据
任务超时处理
实现
ReentrantLock + Condition
根据Delay时间排序的优先级队列:PriorityQueue
Delayed接口
用来标记那些应该在给定延迟时间之后执行的对象
该接口要求实现它的实现类必须定义一个compareTo方法,该方法提供与此接口的getDelay方法一致的排序。
SynchronousQueue
一个没有容量的阻塞队列
应用
交换工作,生产者的线程和消费者的线程同步以传递某些信息、事件或者任务
难搞懂,与Exchanger有一拼
LinkedTransferQueue
链表组成的的无界阻塞队列
相当于ConcurrentLinkedQueue、SynchronousQueue(公平模式下)、无界的LinkedBlockingQueues等的超集
预占模式
有就直接拿走,没有就占着这个位置直到拿到或者超时或者中断
LinkedBlockingDeque
由链表组成的双向阻塞队列
容量可选,在初始化时可以设置容量防止其过度膨胀,如果不设置,默认容量大小为Integer.MAX_VALUE
运用
“工作窃取”模式
集合框架
Collection
List
有序可重复,有下标
有序可重复,有下标
Arraylist
LinkedList
Vector
- 实现方式:数组(连续的存储空间)
- 查询快,增删慢(涉及到数组的移动和复制)
- 线程不安全
- 空间占用:list列表结尾需要预留空间
LinkedList
- 实现方式:双向链表实现(存储空间不连续)
- 查询慢,增删快(只需要更改前后节点引用)
- 线程安全
- 空间占用:每个元素所占空间较大,需要保存前后节点信息
- 内部:Node节点,头节点,尾节点(Node:item元素,前指针,后指针)
Vector
- 实现方式:数组
- 查询快,增删慢
- 线程安全
Set
无序不可重复,无下标
无序不可重复,无下标
HashSet
LinkedHashSet
TreeSet
- 实现方式:HashMap,底层维护了一个数组+链表/红黑树
- 线程不安全
- 查询:不支持随机访问,需要使用元素查询
- 遍历顺序和插入顺序不一致
LinkedHashSet
- 实现方式:LinkedHashMap
- 线程不安全
- 查询:不支持随机访问,需要使用元素查询
- 遍历顺序和插入顺序一致
TreeSet
- 实现方式:TreeMap
- 线程不安全
- 查询:不支持随机访问,需要使用元素查询
- 遍历顺序按照插入顺序升序排列
Queue
提供队列结构
提供队列结构
Deque
提供双端队列
提供双端队列
Map
无序,key不可重复,value可重复
无序,key不可重复,value可重复
HashMap
特点
- 实现方式:数组+链表/红黑树
- 线程不安全
- 迭代顺序和插入顺序不一致
put方法过程?
什么是hash?
为什么引入红黑树?
红黑树转回链表的情况?
为什么加载因子是0.75?
什么时候进行扩容?
为什么数组长度要求2的n次幂?
构造HashMap时传入非2的n次幂作为数组长度(如10)?
什么算法计算key的hash值?(扰动函数)
JDK8做了哪些优化?
- 判断数组是否已初始化,未初始化进行初始化;
- 已初始化,则计算key的hash值,通过 (n - 1) & hash计算应当存放在数组中的下标 index ;
- 查看 table[index] 是否存在数据,没有数据就构造一个 Node 节点存放在 table[index] 中;
- 存在数据,说明发生了 hash 冲突,继续判断 key 是否相等,如果相等,用新的 value 替换原数据(onlyIfAbsent 为 false);
- 如果不相等,判断当前节点类型是不是树型节点,如果是树型节点,创建树型节点插入红黑树中;
- 如果不是树型节点,创建普通 Node 加入链表尾部;判断链表长度是否>8且数组长度>=64, 是则将链表转换为红黑树;
- 插入完成之后判断当前节点数是否大于阈值,如果大于开始扩容为原数组的二倍;
什么是hash?
- 将任意长度输入通过hash算法得到一个固定长度输出。
为什么引入红黑树?
- 解决过多hash冲突导致链化后查询效率低的问题。
红黑树转回链表的情况?
- 红黑树的元素数量<6时转回链表。
- 因为维护红黑树的成本比链表高,而在元素数量较少时链表的性能与红黑树相当,不需要维护更复杂的树结构。
为什么加载因子是0.75?
- 主要是时间和空间的权衡,减少哈希冲突避免过多的性能消耗。
- 当加载因子较小时,扩容的概率会增加,且浪费数组空间。
- 当加载因子较大时,扩容的概率会降低,且链表的长度可能很长,查询效率下降。
什么时候进行扩容?
- 数组中元素数量=数组容量与加载因子的乘积(默认16×0.75=12)时进行扩容。
- 链表节点数>8,且数组长度<64。
为什么数组长度要求2的n次幂?
- 为了让索引值计算尽量分散,尽量减少哈希碰撞,达到高效存取的目的。反过来说就是避免链表或红黑树过长,导致效率下降。
- 索引值的计算:key的hash值 & (数组长度-1)
- 数组长度为2的n次幂可以保证(数组长度-1时)二进制数低位有1或者有连续的1(例如1的二进制为00000001,3为00000010,7为00000111,15为00001111),保证在key的hash值与数组长度-1的二进制数进行按位与运算时得到的索引值尽量分散。
- 按位与运算:相同的二进制数位上都是1,结果为1,否则为0。
- 例如3的二进制数为00000011,15为00001111,按位与运算后的结果为00000011,等于3。
构造HashMap时传入非2的n次幂作为数组长度(如10)?
- (调用tableSizeFor方法)在构造方法中会对传入的数组长度值进行无符号右移和按位或运算计算出一个大于当前值的最近2的n次幂数(如10就是16,18就是32)。
- 按位或运算:相同的二进制数位上都是0,结果为0,否则为1。
什么算法计算key的hash值?(扰动函数)
- 首先通过hashCode方法计算key的hash值h1
- 然后将h1无符号右移16位得到h2
- 之后将h1与h2进行按位异或(^)运算得到最终hash值h3
- 之后将h3与(length-1)进行按位与(&)运算得到hash表索引
按位异或:参与运算的两个值,如果两个相应位相同,则结果为0,否则为1。
其他可以计算出hash值的算法有:平方取中法、取余数、伪随机数法。
JDK8做了哪些优化?
- 1、1.8前是数组+链表,1.8后是数组+链表或红黑树。
- 2、链表的插入方式从头插法改成了尾插法,简单说就是插入时,如果数组位置上已经有元素,1.7 将新元素放到数组中,原始节点作为新节点的后继节点,1.8 遍历链表,将元素放置到链表的最后。
- 3、扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置;1.8 采用更简单的判断逻辑,位置不变或索引+旧容量大小(二进制高位为0时,用原来索引值,高位为1时,索引值等于原来索引值+原来数组长度)。
- 4、在插入时,1.7 先判断是否需要扩容再插入,1.8 先进行插入再判断是否需要扩容。
HashTable
实现方式:数组(主体)和链表(解决哈希冲突)
线程安全
迭代顺序和插入顺序不一致
实现方式:数组(主体)和链表(解决哈希冲突)
线程安全
迭代顺序和插入顺序不一致
LinkedHashMap
实现方式:HashMap(存储数据)和双向链表(维持顺序)
线程不安全
迭代顺序和插入顺序一致
实现方式:HashMap(存储数据)和双向链表(维持顺序)
线程不安全
迭代顺序和插入顺序一致
TreeMap
实现方式:红黑树(自平衡的排序二叉树)
线程不安全
迭代顺序和插入顺序一致,默认按照 key 升序排列,也可使用 compare() 方法指定顺序
实现方式:红黑树(自平衡的排序二叉树)
线程不安全
迭代顺序和插入顺序一致,默认按照 key 升序排列,也可使用 compare() 方法指定顺序
0 条评论
下一页