多线程大厂面试题总结(2023最新版) | 您所在的位置:网站首页 › 一挺胸后背中间就响并且疼怎么回事 › 多线程大厂面试题总结(2023最新版) |
一、实现方式
1.1继承Thread类 重写run方法
/**
* 继承Thread类 重写run方法
*/
public class Thread1 extends Thread{
private String name;
public Thread1(String name) {
this.name=name;
}
@Override
public void run() {
for (int i = 0; i < 10; i++) {
System.out.println(name + "运行 : " + i);
try {
sleep((int) Math.random() * 10);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public static void main(String[] args) {
Thread1 mTh1=new Thread1("A");
Thread1 mTh2=new Thread1("B");
mTh1.start();
mTh2.start();
}
}
1.2实现Runnable接口 重写run方法
/**
* 实现Runnable接口 重写run方法
*/
public class Thread2 implements Runnable{
private String name;
public Thread2(String name) {
this.name=name;
}
@Override
public void run() {
for (int i = 0; i < 5; i++) {
System.out.println(name + "运行 : " + i);
try {
Thread.sleep((int) Math.random() * 10);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public static void main(String[] args) {
new Thread(new Thread2("C")).start();
new Thread(new Thread2("D")).start();
}
}
最常用的方式:
匿名内部类:
/**
* 匿名内部类创建线程
*/
Thread t1 = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 1000; i++) {
System.out.println("匿名内部类"+i);
}
}
});
lambad方式:
/**
* lambda方式创建线程
*/
Thread t2 = new Thread(()->{
for (int i = 0; i < 1000; i++) {
System.out.println("lambad"+i);
}
});
1.3实现Callable 重写call方法,配合FutureTask
一般用于有返回结果的非阻塞的执行方法同步非阻塞。 /** * 1.3实现Callable 重写call方法,配合FutureTask * 创建线程 */ public class Test02 { static class MyCallable implements Callable{ @Override public Object call() throws Exception { int count = 0; for (int i = 0; i < 100; i++) { count += i; } return count; } } public static void main(String[] args) throws ExceptionInInitializerError, InterruptedException, ExecutionException { //1、创建MyCallable MyCallable myCallable = new MyCallable(); //2、创建FutureTask,传入Callable FutureTask futureTask = new FutureTask(myCallable); //3、创建Thread线程 Thread t = new Thread(futureTask); //4、启动线程 t.start(); //5、业务操作 //。。。 //6、得到结果 Object o = futureTask.get(); System.out.println("o = " + o); } } 1.4基于线程池构建线程追其底层,其实只有一种,实现Runnable 二、线程的状态 2.1从操作系统层面来说总共有5种。这种说法实则是将RUNNABLE状态细分成了运行和就绪两种状态 2.4代码案例 /** * 线程各状态模拟 */ public class State { //NEW : 分配内存地址,创建线程 public static void NEW(){ Thread t1 = new Thread(()->{ }); System.out.println("t1 = " + t1.getState()); } //RUNNABLE:(就绪/运行)调用start()之后(/没有调度CPU调度) public static void RUNNABLE() throws InterruptedException { Thread t2 = new Thread(()->{ while (true){ } }); t2.start(); Thread.sleep(500); System.out.println("t2 = " + t2.getState()); } //BLOCKED:还未拿到锁,等待、被阻塞(拿到synchronized失败状态) public static void BLOCKED() throws InterruptedException { Object obj = new Object(); Thread t3 = new Thread(()->{ synchronized (obj){ } }); //main线程拿到obj的锁资源 synchronized (obj){ t3.start(); Thread.sleep(500); System.out.println("t3 = " + t3.getState()); } } //WAITNG:挂起线程、wait(),需要手动唤醒 public static void WAITNG() throws InterruptedException { Object obj = new Object(); Thread t4 = new Thread(()->{ synchronized (obj){ try { obj.wait(); } catch (InterruptedException e) { e.printStackTrace(); } } }); t4.start(); Thread.sleep(500); System.out.println("t4 = " + t4.getState()); } //TIMED_WATING:睡眠,sleep()、join();会被自动唤醒,无需手动唤醒 public static void TIMED_WATING() throws InterruptedException { Thread t5 = new Thread(()->{ try { Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); } }); t5.start(); Thread.sleep(500); System.out.println("t5 = " + t5.getState()); } //TERMINATED:run方法执行完毕,线程生命周期结束 public static void TERMINATED() throws InterruptedException { Thread t6 = new Thread(()->{ try { Thread.sleep(500); } catch (InterruptedException e) { e.printStackTrace(); } }); t6.start(); Thread.sleep(1000); System.out.println("t6 = " + t6.getState()); } public static void main(String[] args) throws InterruptedException { NEW(); RUNNABLE(); BLOCKED(); WAITNG(); TIMED_WATING(); TERMINATED(); } } 三、如何停止线程本质:使正在运行的run方法结束,无论是return还是抛出异常都可以。 3.1 stop方法(不推荐)强制结束,已过时 3.2 使用共享变量(很少会用)根据业务决定,有的线程可能会通过死循环保证一直运行。 可用过修改共享变量破坏死循环,使线程退出循环,结束run方法。 3.3 interrupt方式共享变量方式(类似),线程内部提供中断标记位 interrupt标记默认false 线程执行过程中如果修改了终端标记位,会抛出异常 四、sleep和wait方法的区别 sleepwait来源Thread中的static修饰的方法Object类的方法状态TIMED_WATING,可自动唤醒WAITNG,需手动唤醒持有锁时执行不会释放锁资源释放锁资源执行前提都可执行必须持有锁时才能执行wait方法会将持有锁的线程从owner扔到WaitSet集合中,这个操作是在修改ObjectMonitor对象, 如果没有持有synchronized锁,则无法操作ObjectMonitor对象。 五、并发编程三大特性 5.1原子性定义:一个操作不可分割,不可中断,一个线程在执行时,另一个线程不会影响到它。 目的:为了方式多线程操作共享变量,带来线程安全问题 5.1.1 synchronize 同步线程锁互斥锁,需要先获取到锁资源,才能执行后面的命令。 //synchronize public static void syn(){ Object obj = new Object(); Thread t = new Thread(()->{ synchronized (obj){ //执行业务 try { Thread.sleep(500); } catch (InterruptedException e) { e.printStackTrace(); } } }); t.start(); new Thread(()->{ synchronized (obj){ System.out.println("我获取到了"); } }).start(); } 5.1.2 CAS操作系统CPU层面的并发原语。 替换内存某个位置的值时,首先查看其中的值是否与预期值一致,一致才执行替换操作。原子性操作。 优点:避免内核态和用户态的切换,线程不会挂起,且保证数据的原子性。 缺点:通过while循环,执行CAS的操作,性能较差。 自旋时间过长问题: 指定循环次数,超过则挂起/失败 一次失败后,暂存该操作,后续需要获取结果时,将暂存的操作全部执行,再返回最后的结果。 //CAS锁 private static AtomicInteger atomicInteger = new AtomicInteger(0); public static void CASTest() throws InterruptedException { Thread t1 = new Thread(()->{ for (int i = 0; i < 100; i++) { atomicInteger.incrementAndGet(); } }); Thread t2 = new Thread(()->{ for (int i = 0; i < 100; i++) { atomicInteger.incrementAndGet(); } }); t1.start(); t2.start(); t1.join(); t2.join(); System.out.println("atomicInteger = " + atomicInteger); } ABA问题:解决方式:通过版本号区分 5.1.3 Lock锁相当于jdk1.6之前的synchronize 锁性能较好,1.6之后相差不大。 并发较多时,推荐使用ReentrantLock锁。 //Lock锁 private static int count; private static ReentrantLock lock = new ReentrantLock(); public static void increment(){ //加锁 lock.lock(); try { count++; try { Thread.sleep(10); } catch (InterruptedException e) { e.printStackTrace(); } }finally { //释放锁 lock.unlock(); } } 5.1.3 ThreadLock锁保证原子性的方式:不让多线程去操作临界资源,让每个线程只去操作属于自己的数据。 //ThreadLock锁 static ThreadLocal tl1 = new ThreadLocal(); static ThreadLocal tl2 = new ThreadLocal(); public static void main(String[] args) { tl1.set("123"); tl2.set("456"); Thread t1 = new Thread(()->{ System.out.println("t1:"+tl1.get()); System.out.println("t1:"+tl2.get()); }); t1.start(); System.out.println("main:"+tl1.get()); System.out.println("main:"+tl2.get()); } 5.2 可见性概念:基于CPU位置出现,CPU提供了L1、L2、L3的三级缓存,每次去主内存拿完数据之后,会存储在三级缓存,下次会去缓存中取。 问题:如今的CPU都是多核的,每个线程的工作内存(三级缓存)都是独立的,每个线程中做修改后只改自己的工作内存,没有及时同步到主内存,导致数据不一致。 解决方式: 5.2.1 volatile (彻底解决)作用:告知CPU当前属性的操作,不允许使用缓存,必须去主内存操作。 5.2.2 synchronize同步代码块/同步方法,获取到锁资源后,将内部涉及到的变量从CPU缓存中移除,必须去主内存中重新拿数据,释放锁后,会立即将CPU缓存中的数据同步到主内存。 注意:仅在加锁的时刻,同步数据 5.2.3 Lock基于volatile 实现,对其修饰的属性操作时,CPU会执行带有Lock前缀的指令,将修改的数据以及其他属性立即同步到主内存中。还会将其他CPU缓存中的和这个数据设置为无效。 注意:仅在执行的时刻,同步数据 5.2.4 final修饰的属性在运行期间不允许修改,简介保证了可见性。 5.3 有序性为发挥CPU的性能,在不影响最终结果的前提下,会对指令进行重排。 核心解决方式 5.3.1 volatile实现原理:内存屏障概念。将内存屏障看成一条指令。 在两个操作之间,添加上一道指令,这个指令可避免上下执行的其他指令进行重新排序。 5.4 四种引用类型 5.4.1 强当一个对象被强引用时,始终处于可达状态,不可能被垃圾回收清理。 内存泄漏主要原因之一。 User user = new User(); 5.4.2 软系统内存不足时会被回收,通常用在对内存敏感的程序中,作为缓存使用。 SoftReference 5.4.3 弱生命周期更短,不管JVM内存空间是否足够,垃圾回收一运行,总会回收该对象占用的内促。 5.4.4 虚不能单独使用,必须和引用队列联合使用。 作用:跟踪对象的垃圾回收状态。 六、锁的分类 6.1 可重入锁、不可重入锁 重入:当前线程获取到锁后,尝试再次获取时可以直接拿到 synchronize、ReentrantLock、ReentrantReadWriteLock 不可重入:当前线程获取到锁后,尝试再次获取时不能直接拿到,需要等待自己释放(死锁)。 6.2 乐观锁、悲观锁 乐观:获取不到锁资源,可以再次让CPU调用,重新尝试获取锁资源。不会挂起,不断尝试。 CAS 悲观:当没有获取到锁资源时,大概率挂起线程(BLOCKED、WAITING),涉及用户态和内核态的切换,消耗资源。 用户态:JVM可以自行执行的命令,不需要借助操作系统。 内核态:JVM不可以自行执行的命令,需要借助操作系统才可以执行。synchronize、ReentrantLock、ReentrantReadWriteLock 6.3 公平锁、非公平锁 公平:排队线程A获取到锁资源,B来排队,此时C来了必须排到B后面。 ReentrantLock、ReentrantReadWriteLock都可实现 非公平:可以插队线程A获取到锁资源,B来排队,此时C来了先尝试竞争一波。 拿到锁资源:插队成功。 没拿到锁资源:依然排在B后面,等B释放后,可再次尝试竞争。synchronize只能实现非公平 6.4 互斥锁、共享锁ReentrantReadWriteLock两者都有 互斥:同一时间点,只会有一个线程持有 synchronize、ReentrantLock 共享:同一时间,可以有多个线程持有 七、synchronize 7.1 实现原理基于对象实现
MarkWord 标记了不同的锁在不同状态下所存储的对象信息 若代码块中不存在操作临界资源的情况,触发 public synchronized void test(){ //synchronized相当于没有 } 7.3.2 锁膨胀循环中频繁获取和释放锁资源,则将锁的范围扩大,避免频繁竞争和获取带来不必要的消耗。 public void test(){ Object object = new Object(); for (int i = 0; i < 99999999; i++) { synchronized (object){ } } //上方代码触发锁膨胀等同于如下代码 synchronized (object){ for (int i = 0; i < 99999999; i++) { } } } 7.3.3 锁升级(获取锁资源的成本降低)jdk1.6之前:获取不到锁资源时,会立即挂起当前线程,因此性能较差。 7.3.3.1 无锁、匿名偏向:当前对象没有作为锁存在。 7.3.3.2 偏向锁:当前不存在资源竞争,当前线程再次尝试获取锁资源时,进过判断是否是再次申请 是:直接拿走资源。 不是:基于CAS方式,尝试将偏向锁指向当前线程,如果获取不到,触发锁升级->轻量级锁。 7.3.3.3 轻量级锁:采用自旋锁的方式,频繁的以CAS形式获取锁资源(自适应自旋锁) 成功:直接拿走资源。 失败:自旋一定次数,还未获取资源,触发锁升级。 7.3.3.4 重量级锁:传统synchronized方式,拿不到锁资源则直接挂起。(用户态&内核态切换) 7.4 ReentrantLock与synchronized的区别 ReentrantLocksynchronized使用方式执行lock()同步方法、同步代码块释放执行unlock()不需要手动释放本质对象,功能性更强关键字公平性公平、非公平非公平自定义可以设置尝试竞争的时间,可设置拿不到资源时自定义返回无原理基于AQS实现(JUC下一个基类,Java开发)基于ObjectMonitor(底层为C语言编写)性能不存在锁升级概念,效率略高竞争过于激烈时,总会升级为重量级锁,舍弃jdk1,8这个层面,基于C语言优化潜力更高 八、AQSJUC包下的一个基类AbstractQueuedSynchronizer 提供了一个有volatile修饰的采用cas方式修改的state属性 AQS队列:双向链表。 九、ReentrantReadWriteLock 8.1 为什么要出现读写锁ReentrantLock与synchronized都是互斥锁 业务场景:读多写少,互斥锁效率较低 读和读之间不互斥,读写互斥 8.2 实现原理基于AQS,还是对state进行操作,拿到资源就去干活儿,没拿到依然去AQS队列中排队。 可重入锁,相比于ReentrantLock锁可重入次数降低。 8.2.1 读锁:基于state的高16位操作。 读锁重入:共享锁,多个读线程持有锁资源,无法确认每个线程读锁重入次数。每个读线程都有一个ThreadLocal记录重入的次数。 8.2.2 写锁:基于state的低16位操作。 写锁重入:state+1,确认持有锁的线程,是当前写锁线程即可,state取值范围缩小。 8.2.3 写锁饥饿:写操作要等到所有读操作执行完成之后再执行。读操作过多时,会出现前面的读操作还未执行完,后续的读操作插队继续执行,造成写的操作等待时间过长。 当写线程开始等待时,新来的读操作需要去AQS队列排队。如果队列的前面需要写锁资源的线程,那么后续线程是无法拿到锁资源的。 持有读锁的线程,只会让写锁线程之前的读线程拿到锁资源。 十、JDK提供了哪些线程池一般情况下不推荐使用jdk自带的线程池,很多参数无法控制。 10.1 newFixedThreadPool 定长线程池线程数是固定的,参数作为核心线程数和最大线程数,不会创建非核心线程,超过最大线程数时,放入阻塞队列等待。 //10.1 newFixedThreadPool 定长线程池 public static ExecutorService newFixedThreadPool(int nThreads){ return new ThreadPoolExecutor(nThreads, //主线程数 nThreads, //最大线程数 0L, TimeUnit.MILLISECONDS, new LinkedBlockingQueue()); //阻塞队列 } 10.2 newSingleThreadExecutor 单例线程池线程池中只有一个工作线程在处理任务,顺序消费。 10.3 newCacheThreadPool 缓存线程池默认没有核心工作线程,创建时会直接构建一个工作线程,每次任务先丢入阻塞队列。 10.4 newScheduleThreadPool 定时任务线程池只对阻塞队列做了更改,可以设置出阻塞队列的等待时间。 10.5 newWorkStealingPool 基于工作窃取每个线程都有属于自己的阻塞队列。基于ForkJoinPool。 十一、线程池的核心参数有哪些?无法处理任务时,直接抛出异常。 public void rejectedExecution(Runnable r, ThreadPoolExecutor e) { throw new RejectedExecutionException("Task " + r.toString() + " rejected from " + e.toString()); } 11.1.2 CallerRunsPolicy无法处理任务时,将任务交给调用者处理。 public void rejectedExecution(Runnable r, ThreadPoolExecutor e) { if (!e.isShutdown()) { r.run(); } } 11.1.3 DiscardPolicy无法处理任务时,直接丢掉任务。 public void rejectedExecution(Runnable r, ThreadPoolExecutor e) { } 11.1.4 DiscardOldestPolicy无法处理任务时,将队列中最早的任务丢掉,将当前任务再次尝试交给线程池处理 public void rejectedExecution(Runnable r, ThreadPoolExecutor e) { if (!e.isShutdown()) { e.getQueue().poll();//将队列中最早的任务丢掉 e.execute(r); } } 十二、线程池的状态核心参数ctl,维护了工作线程的个数、核心状态 private final AtomicInteger ctl = new AtomicInteger(ctlOf(RUNNING, 0)); private static final int RUNNING = -1 = 0) { binCount = 1; for (Node e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node pred = e; if ((e = e.next) == null) { pred.next = new Node(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { Node p; binCount = 2; if ((p = ((TreeBin)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; } static final int HASH_BITS = 0x7fffffff; //计算当前Node的hash值的方法 static final int spread(int h) { //将key的hashCode值的高16位进行^运算,最终又与HASH_BITS进行&运算 //将最高位的hash也参与到计算索引位置的运算中 //为什么HashMap、ConcurrentHashMap都要求数组长度为2^n //HASH_BITS让hash值的最高位符号位肯定为0,代表当前hash值默认情况下一定为正数,因为hash值为负数时,有特殊的含义 //static final int MOVED = -1; // 代表当前hash位置的数据正在扩容! //static final int TREEBIN = -2; // 代表当前hash位置下挂载的是一个红黑树 //static final int RESERVED = -3; // 预留当前索引位置 return (h ^ (h >>> 16)) & HASH_BITS; //计算数组放在哪个索引位置的方法(f = tabAt(tab, i = (n-1) & hash)) //n 是数组的长度 } 二十、ConcurrentHashMap初始化数组的流程?懒加载:第一次添加数据时,才会初始化数组。 //数组在初始化和扩容操作时的一个控制变量 //-1:代表当前数组正在初始化 //小于-1:低16位代表当前数组正在扩容的线程个数(如果1个线程扩容,值为-2;如果2个线程扩容,值为-3) //0:代表数组还没初始化 //大于0:代表当前数组的扩容阈值,或者是当前数组的初始化大小 private transient volatile int sizeCtl; //初始化数组方法 private final Node[] initTable() { //声明标识 Node[] tab; int sc; //再次判断数组没有初始化,并且完成tab赋值 while ((tab = table) == null || tab.length == 0) { //将sizeCtl赋值给sc变量,并判断是否小于0 if ((sc = sizeCtl) < 0) Thread.yield(); // 可以尝试初始化数组,线程会以CAS的方式,将sizeCtl修改为-1,代表当前线程可以初始化数组 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //尝试初始化 try { //再次判断当前数组是否已经初始化完毕 if ((tab = table) == null || tab.length == 0) { //开始初始化 //如果sizeCtl > 0 ,就初始化sizeCtl长度的数组 //如果sizeCtl ==0 ,就初始化默认的长度 int n = (sc > 0) ? sc : DEFAULT_CAPACITY; //初始化数组! @SuppressWarnings("unchecked") Node[] nt = (Node[])new Node[n]; //将初始化的数组nt,赋值给tab和table table = tab = nt; //sc赋值为了数组长度 - 数组长度 右移 2位 16-4=12 //将sc赋值为下次扩容的阈值 sc = n - (n >>> 2); } } finally { //将赋值好的sc,设置给sizeCtl sizeCtl = sc; } break; } } return tab; } 二十一、ConcurrentHashMap扩容的流程? 确认什么时候触发扩容 计算扩容标识戳 将扩容表示戳往左移16位+2(代表第一个进来扩容的) 计算每个线程迁移的长度 初始化一个全新的数组 线程领取任务,从多少索引位置迁移到多少索引位置 开始扩容、迁移数据 判断是否为最后一个完成迁移的 如果是则全局检查一次有没有遗漏的数据 //链表长度大于等于8时,尝试将链表转为红黑树 private final void treeifyBin(Node[] tab, int index) { Node b; int n, sc; //数组不能为空 if (tab != null) { //数组的长度n,是否小于64 if ((n = tab.length) < MIN_TREEIFY_CAPACITY) //如果数组长度小于64,不能将链表转为红黑树,先尝试扩容 tryPresize(n = 0) { synchronized (b) { if (tabAt(tab, index) == b) { TreeNode hd = null, tl = null; for (Node e = b; e != null; e = e.next) { TreeNode p = new TreeNode(e.hash, e.key, e.val, null, null); if ((p.prev = tl) == null) hd = p; else tl.next = p; tl = p; } setTabAt(tab, index, new TreeBin(hd)); } } } } } 21.2 tryPresize方法-针对putAll初始化操作 //size是将之前的数组长度 左移1位得到的结果 private final void tryPresize(int size) { //如果扩容的长度达到了最大值,就使用最大值 //否则需要保证数组的长度为2的n次幂 //这块的操作,是为了初始化操作准备的,因为调用putAll方法时,也会触发tryPresize方法 //如果刚刚new的ConcurrentHashMap直接调用饿了putAll方法,会通过tryPresize方法进行初始化 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1); //这些代码和initTable一模一样 //声明sc int sc; //将sizeCtl的值赋给sc,并且判断是否大于0,这里代表没有初始化操作,也没有扩容操作 while ((sc = sizeCtl) >= 0) { //将ConcurrentHashMap的table值赋值给tab,并声明数组长度n Node[] tab = table; int n; //数组是否需要初始化 if (tab == null || (n = tab.length) == 0) { n = (sc > c) ? sc : c; if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { if (table == tab) { @SuppressWarnings("unchecked") Node[] nt = (Node[])new Node[n]; table = nt; sc = n - (n >>> 2); } } finally { sizeCtl = sc; } } } else if (c = MAXIMUM_CAPACITY) break; else if (tab == table) { //计算扩容表示戳,根据当前数组的长度计算一个16位的扩容戳 //第一个作用是为了保证后面的sizeCtl赋值时,保证sizeCtl为小于-1的负数 //第二个作用用来记录当前是从什么长度开始扩容的 int rs = resizeStamp(n); //如果sc小于0,代表有线程正在扩容 if (sc < 0) { Node[] nt; if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex >> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // 根据CPU计算每个线程一次迁移多长的数据到新数组,如果结果大于16,使用计算结果; //如果小于16,就使用最小长度。 } 二十二、ConcurrentHashMap读取数据的流程? 不会阻塞读取数据的线程。 先判断当前key对应的value,是否在数组上。 其次判断当前位置是否属于特殊情况:数据被迁移、位置被占用、红黑树结构。 最后判断链表上是否有对应的数据。 22.1 get方法-查询数据的入口 public V get(Object key) { //tab:数组;e:查询指定位置的节点;n:数组长度 Node[] tab; Node e, p; int n, eh; K ek; //基于传入的key,计算hash值 int h = spread(key.hashCode()); //数组不为null,数组得有数据,拿到指定位置的数组上的数据 if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { //数组上数据的hash值,是否和查询条件key的hash值一样 if ((eh = e.hash) == h) { //key的==或者equals是否一致,一致则数组上就是要查询的数据 if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } //如果数组上的数据的hash值为负数,有特殊情况 else if (eh < 0) //三种情况:数据迁移、节点位置被占、红黑树结构 return (p = e.find(h, key)) != null ? p.val : null; //肯定走链表操作 while ((e = e.next) != null) { //如果hash值一致,并且key的==或者equals一致,返回当前链表位置的数据 if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } //如果上述三个流程都没有找到指定key对应的value,那就是key不存在,返回null return null; }数据迁移: Node find(int h, Object k) { //找到迁移后的新数组 outer: for (Node[] tab = nextTable;;) { Node e; int n; if (k == null || tab == null || (n = tab.length) == 0 || (e = tabAt(tab, (n - 1) & h)) == null) return null; for (;;) { int eh; K ek; if ((eh = e.hash) == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; if (eh < 0) { if (e instanceof ForwardingNode) { tab = ((ForwardingNode)e).nextTable; continue outer; } else return e.find(h, k); } if ((e = e.next) == null) return null; } } }红黑树: final Node find(int h, Object k) { if (k != null) { for (Node e = first; e != null; ) { int s; K ek; //判断你是否正在有写的操作或者有写的操作在等待 //查询转换红黑树时保留的双向链表 if (((s = lockState) & (WAITER|WRITER)) != 0) { if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; e = e.next; } //如果已经没有写操作在进行了,直接去红黑树上查找 else if (U.compareAndSwapInt(this, LOCKSTATE, s, s + READER)) { TreeNode r, p; try { p = ((r = root) == null ? null : r.findTreeNode(h, k, null)); } finally { Thread w; if (U.getAndAddInt(this, LOCKSTATE, -READER) == (READER|WAITER) && (w = waiter) != null) LockSupport.unpark(w); } return p; } } } return null; } 二十三、ConcurrentHashMap中计数器的实现 addCount方法中:记录Map中存储了多少个元素 为防止效率过低, 除了baseCount之外,还准备了多个CounterCell数组, 最后将baseCount的值以及每个CounterCell数组中值进行累加 private final void addCount(long x, int check) { CounterCell[] as; long b, s; //baseCount:记录某个元素组个数 //并发量较大时,向 CounterCell[] as中添加数据 if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { CounterCell a; long v; int m; boolean uncontended = true; if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null || !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { fullAddCount(x, uncontended); return; } if (check = 0) { Node[] tab, nt; int n, sc; while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) { int rs = resizeStamp(n); if (sc < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex |
CopyRight 2018-2019 实验室设备网 版权所有 |