面试突击-基础篇

发表于 | 分类于

HashMap

存储结构

数组+链表+红黑树，链表的存在是为了解决hash冲突，当链表长度大于8的时候，后面的数据存放在红黑树中。

特点

  1. 快速存储
  2. 快速查找（时间复杂度为o(1)）
  3. 可伸缩
  4. 线程不安全

数组下标计算

数组默认大小为：16
数组下标： hash & （16-1） = hash % 16

扩容

初始容量16，最大容量2的30次方，加载因子系数为 0.75，即容量达到四分之三时，开始扩容，扩容增量为原容量的一倍，即一次扩容后容量为32

操作流程

put 操作：

  1. 首先判断key是否为null，若为null，直接插入数组第一个位置，数组原来有的数据，下标依次后移加一

  2. 若key不为null，计算key的hash值，取数组长度的模，得到其应该存储的数组位置

  3. 若该位置无值，直接插入

  4. 若该位置有值，判断链表中是否有key一样，有一样的话，覆盖原值，无一样的话，保存在链头

get 操作：

  1. 判断key是否为null，若为null，直接返回null的值

  2. 若key不为null，根据key的hash值，确定数组位置

  3. 遍历链表，返回key的hash值相同，且key一样的value

JDK1.8 对 HashMap 的优化

  • 由 数组+链表 的结构改为 数组+链表+红黑树 。
    拉链过长会严重影响hashmap的性能，所以1.8的hashmap引入了红黑树。
    在链表元素数量超过8时改为红黑树，少于6时改为链表，中间7不改是避免频繁转换降低性能。
    相对于链表，改为红黑树后碰撞元素越多查询效率越高。链表O(n)，红黑树O(logn)。
  • 优化了高位运算的hash算法：h^(h>>>16)，将hashcode无符号右移16位，让高16位和低16位进行异或。
  • 扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。
    不需要重新计算hash，只需要根据原来hash值新增的bit是1还是0分别放进两个链表lo和hi（非红黑树的情况）里，0的话索引没变，1的话索引变为原索引加原来的数组长度。
    因为用的尾插法所以新数组链表不会倒置，多线程下不会出现死循环。
  • put 方法链表头插改为尾插

线程池

四大组件

1、线程池管理器（ThreadPoolManager）:用于创建并管理线程池
2、工作线程（WorkThread）: 线程池中线程
3、任务接口（Task）:每个任务必须实现的接口，以供工作线程调度任务的执行。
4、任务队列:用于存放没有处理的任务。提供一种缓冲机制。

四大种类

1.CachedThreadPool（可缓存的线程池，只有非核心线程）
2.SecudleThreadPool（周期性执行任务的线程池）
3.SingleThreadPool（单线程线程池，适用于有顺序的任务场景）
4.FixedThreadPool（定长的线程池，只有核心线程）

1
2
3
4
5
6
7
8
9
10
public void threadpool(){
      Executor executor1 = Executors.newSingleThreadExecutor();
      Executor executor2 = Executors.newFixedThreadPool(5);
      Executor executor3 = Executors.newCachedThreadPool();
      ScheduledExecutorService executor4 = Executors.newScheduledThreadPool(5);
      //ScheduleAtFixedRate 每次执行时间为上一次任务开始起向后推一个时间间隔,上个任务没结束，会等待其结束再执行下个任务
      executor4.scheduleAtFixedRate(()->{},1,1,TimeUnit.SECONDS);
      //ScheduleWithFixedDelay 每次执行时间为上一次任务结束起向后推一个时间间隔
      executor4.scheduleWithFixedDelay(()->{},1,1,TimeUnit.SECONDS);
  }

拒绝策略

1.AbortPolicy：不执行新任务，直接抛出异常
2.DisCardPolicy：不执行新任务，也不抛异常
3.DisCard OldSetPolicy，新任务替换任务队列的第一个任务
4.CallerRunsPolicy：直接调用execute执行当前任务。

死锁

必要条件

互斥条件：一个资源每次只能被一个进程使用，即在一段时间内某 资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。

请求与保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源 已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。

不可剥夺条件:进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能 由获得该资源的进程自己来释放（只能是主动释放)。

循环等待条件: 若干进程间形成首尾相接循环等待资源的关系

避免死锁

1、加锁顺序，即当需要获取a，b两个锁时，只能先获取到a锁，才能获取b锁。
2、加锁时限，即在指定的时间内获取不到锁，就放弃等待锁，并释放自己现在所持有的锁。
3、破坏必要条件

死锁实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class HoldLockThread implements Runnable{
    private String locka;
    private String lockb;
    public HoldLockThread(String locka,String lockb){
        this.locka = locka;
        this.lockb = lockb;
    }
    @Override
    public void run() {
        synchronized (locka){
            System.out.println(Thread.currentThread().getName() + " 自己持有：" + locka + " 尝试获得: " + lockb);
            try {
                Thread.sleep(2000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            synchronized (lockb){
                System.out.println(Thread.currentThread().getName() + " 自己持有：" + lockb + " 尝试获得: " + locka);
            }
        }
    }
}

public class DeadLockDemo {
    public static void main(String[] args) throws InterruptedException {
        String locka = "locka";
        String lockb = "lockb";
        new Thread(new HoldLockThread(locka,lockb),"AAA").start();
        new Thread(new HoldLockThread(lockb,locka),"BBB").start();
    }
}

volatile

volatile 保证了变量的可见性、有序性、不保证原子性（只保证极少数原子性操作）。

可见性

volatile 变量的内存可见性是基于内存屏障（Memory Barrier）实现。内存屏障其实就是一个lock前缀的cpu指令，lock 前缀的指令在多核处理器下，会强制将当前行的数据写回到主内存，这会导致其他cpu缓存的该数据失效，进而需要重新读取。

有序性

为了性能优化，JMM 在不改变正确语义的前提下，会允许编译器和处理器对指令序列进行重排序。JMM 提供了内存屏障阻止这种重排序。
volatile 写操作是在前面和后面分别插入内存屏障，而 volatile 读操作是在后面插入两个内存屏障。

  • 在每个 volatile 写操作的前面插入一个 StoreStore 屏障。
  • 在每个 volatile 写操作的后面插入一个 StoreLoad 屏障。
  • 在每个 volatile 读操作的后面插入一个 LoadLoad 屏障。
  • 在每个 volatile 读操作的后面插入一个 LoadStore 屏障。
屏障 作用
StoreStore 禁止上面的普通写和下面的 volatile 写重排序。
StoreLoad 禁止上面的 volatile 写与下面可能有的 volatile 读/写重排序。
LoadLoad 禁止下面所有的普通读操作和上面的 volatile 读重排序。
LoadStore 禁止下面所有的普通写操作和上面的 volatile 读重排序。

原子性

volatile 不能保证原子性，存在少数情况可以保障（可以保证32位虚拟机系统中 long、double类型单次赋值操作的原子性）。

在 java 中，基本数据类型是天然存在原子性的，如 int i =1；但是在32位虚拟机系统中 long、double的赋值操作，如 long i=3；是不具有原子性的，因为long、double是64位的，在32位虚拟机系统中，多线程并发执行 long i=3；可能会存在一个线程在修改低32位，另一个线程在修改高32位，导致最后赋值操作的结果不是预期的。但是通过 volatile 修饰可以保证其原子性。

synchronized

synchronized 保证了变量的可见性、有序性、原子性 。

1
2
3
4
5
6
7
8
9
10
11
synchronized(this){
	# monitorenter
	# load
	# acquire
	
	do something……
	
	# release
	# monitorexit
	# store
}

synchronized 也是通过内存屏障来实现3个特性。当代码运行到 synchronized 关键字时，
1.会生成一个 monitorenter 指令，表示进入，
2.然后通过 load 指令执行 refresh 操作，即把别的处理器修改过的最新值加载到自己工作内存；
3.通过 acquire 指令禁止上文与屏障代码指令重排，
4.通过 release 指令禁止下文与屏障代码指令重排； .// 有序性
5.然后通过 monitorexit 指令退出屏障，
6.紧接着通过 store 执行 flush 操作 ，即将修改的值刷回到主内存。 .// 可见性
7.其原子性保障是通过 monitorObject 对象，运用 cas 加锁实现。

伪共享

cpu 缓存行

cpu 的处理速度与访问内存、磁盘相比，相差过大，所以有了 cpu 的三级缓存，L1到L3缓存容量依次增大，查找耗时依次增大，cpu 查找顺序依次是L1、L2、L3、主存。cpu 读取数据通常一次读取一个缓存行（Cache Line），缓存行的大小通常是64字节，这意味着即使只操作1字节的数据，cpu 最少也会读取这个数据所在的连续64字节数据。

缓存行状态，MESI 协议

MESI协议描述了多核处理器中一个缓存行的状态。每个缓存行有4个状态，分别是：
M（修改，Modified）： 本地处理器已经修改缓存行，它的内容与主内存中的内容不一样，并且此 cache 只有本地一拷贝(专有)；
E（专有，Exclusive）： 缓存行内容和内存中的一样，而且其它处理器都没有这行数据；
S（共享，Shared）： 缓存行内容和内存中的一样, 有可能其它处理器也存在此缓存行的拷贝；
I（无效，Invalid）： 缓存行失效, 不能使用。

Java中的伪共享

一个缓存行的大小是64字节，如果存放8字节 long 类型，那么一个缓存行可以存储 8个 long类型的变量，如果我们有两个 long 类型变量A、B，它们在一个缓存行，那么当一个线程要修改A时，需要加载该缓存行，另一个线程要修改B时，也需要加载该缓存行，看似它们修改的不是一个变量，但是却是同一个缓存行，只要有一个线程修改，那么该缓存行在其他线程就会失效，需要重新读取。

避免伪共享

  • 填充
    自己把变量填充到64字节
  • @Contended 注解（要设置 -XX:-RestrictContended=false，它默认为 true，意味仅限 JDK 内部的类使用）
    ConcurrentHashMap 源码里面的 size() 方法使用的是分段的思想来构造的，每个段使用的类是 CounterCell，它的类上就有 @sun.misc.Contended 注解。

未完待续……

0%