面经

2022-02-26 约 2228 字预计阅读 5 分钟次阅读

XLXS汽车一面

ArrayLsit循环删除重复元素

方法	结果
for正序	部分元素删不掉
for倒序	正确、单线程多线程ok
foreach	ConcurrentModificationException
ArrayList Remove	ConcurrentModificationException
Iterator Remove	正确、单线程ok；多线程不一定

b树、b+树区别

B树与B+树的区别

B树每个节点都存储数据，所有节点组成这棵树。B+树只有叶子节点存储数据（B+数中有两个头指针：一个指向根节点，另一个指向关键字最小的叶节点），叶子节点包含了这棵树的所有数据，所有的叶子结点使用链表相连，便于区间查找和遍历，所有非叶节点起到索引作用。
B树中叶节点包含的关键字和其他节点包含的关键字是不重复的，B+树的索引项只包含对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
B树中每个节点（非根节点）关键字个数的范围为[m/2(向上取整)-1,m-1](根节点为[1,m-1])，并且具有n个关键字的节点包含（n+1）棵子树。B+树中每个节点（非根节点）关键字个数的范围为[m/2(向上取整),m](根节点为[1,m])，具有n个关键字的节点包含（n）棵子树。
B+树中查找，无论查找是否成功，每次都是一条从根节点到叶节点的路径。

B树的优点

1.B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

B+树的优点

所有的叶子结点使用链表相连，便于区间查找和遍历。B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
b+树的中间节点不保存数据，能容纳更多节点元素。

B树和B+树的共同优点

考虑磁盘IO的影响，它相对于内存来说是很慢的。数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘页（对应索引树的节点）。所以我们要减少IO次数，对于树来说，IO次数就是树的高度，而“矮胖”就是b树的特征之一，m的大小取决于磁盘页的大小。

HashMap数据结构

HashMap： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间

HashMap优化避免链表死循环

1.7之前（包括），put冲突时使用的时头插法，当多线程下，A线程设置了e =node1，next =node2，又根据头插法，线程B设置了e=node2，next=node1，产生了死循环，cpu100。

1.8以后开始使用尾插法，企图避免多线程下死循环，cpu100，然而还是会主要原因有如下

链表转换树或者对树进行操作，即Node节点转换为TreeNode结点异常

mysql innodb间隙锁

当查询某条数据时，会对非主键的数据加间隙锁比如每天访客顺序属性（非主键），1、3，那么无法重新添加2，但是可以添加4。与隔离级别无关

Spring设计模式

简单工厂(非23种设计模式中的一种)

BeanFactory创建Spring Bean
工厂方法

FactoryBean延迟创建Bean
单例模式

提供单例注册器、创建出的Spring Bean
适配器模式

AOP 的增强或通知(Advice)，适配方法前后通知

Spring MVC中，DispatcherServlet适配不同Controller重定向
装饰器模式

DataSource 装饰多个数据源
代理模式

aop面向切面编程运行时增强的动态代理
观察者模式

事件驱动模型中事件、事件监听、时间发布者
策略模式

MethodNameResolver设置类可以处理那些请求，已过时
模版方法模式

jdbcTemplate、hibernateTemplate

Redis缓存穿透和雪崩

缓存雪崩

原因：大量redis key在同一时间失效，导致大量请求访问数据库，数据库服务器宕机，线上服务大面积报错。

解决办法：

（1）redis高可用

（2）加锁排队，限流降级

（3）缓存失效时间均匀分布

缓存穿透

原因：指缓存和数据库中都没有的数据，导致所有的请求都落到数据库上，造成数据库短时间内承受大量请求而崩掉。

解决办法：

（1）接口层增加校验

（2）采用布隆过滤器

Redis扩容

集群

复制配置文件

**src/redis-cli –cluster add-node **增加主节点

**src/redis-cli –cluster add-node -cluster-slave –cluster-master-id **增加从节点

src/redis-cli –cluster reshard 192.168.209.128:6379 分配槽位

内存渐进式扩容

初始hashsize为4，当数组个数与hash表大小一致，将扩容为两倍

每次的增删改查则扩容（rehashindex）+1，收缩类似，分而治之

多线程执行顺序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


private static int a = 0;

@Override
public void run() {
    for (int i = 0;i < 100; i++) {
        a++;
    }
}

public static void main(String[] args) {
    new Thread(new Whyzero()).start();
    new Thread(new Whyzero()).start();
//        try {
//            Thread.sleep(200);
//        } catch (InterruptedException e) {
//            e.printStackTrace();
//        }
    System.out.println(a);
}

一共有三个线程 t1、t2、main由于指令重排，谁先执行不一定，默认是父线程优先，故无论怎么改都是0

当加上sleep，让两个子线程先执行，就能得到正确结果

 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
32
33
34


static volatile long i;
static volatile long n;

public Add100(long i, long n) {
    this.i = i;
    this.n = n;
}

public void run() {
    for (int m = 0; m < n; m++) {
        i++;
    }
}

public static void main(String[] args) {
    for (int j = 8000; j > 100; j--) {
        test1(j);
        boolean flag = i == 2 * j;
        System.out.println("i==" + i + ";j==" + j + "; " + flag);
    }
}

public static void test1(long n) {
    Add100 add = new Add100(0, n);
    Thread t1 = new Thread(add);
    Thread t2 = new Thread(add);
    t1.start();
    t2.start();
    try {
        Thread.sleep(500);
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
}

当循环次数增加时，会发现结果并不是循环次数的两倍，单核一倍到两倍；多核2到两倍

目录

面经