java面试

1、对key进行hashcode

2、hash表是否为空，如果为空则初始化hash表

3、计算hashcode所在位置有没有数据，如果没有数据则直接放置

4、如果有数据，则判断key是否相等，如果相等则直接替换

5、如果不同则判断是否为红黑树

6、如果是红黑树，则直接插入树

7、如果是链表，则遍历链表，添加到最后

8、判断链表长度是否大于8，如果大于8则转为红黑树

9、如果元素个数大于阈值，则进行扩容

链表

红黑树

1、将容量扩充为2倍

2、将原始hash表的元素重新hash放置在新的hash表中

子主题

原子操作能保证原子性

内存屏障

happens-before语义

原理

问题

独占模式下有线程获取到许可的过程就是state值从0=>1的过程，只有获取到许可的线程进行,重入的操作state值会从1=>2,在共享模式下当调用countDown()方法时，就是一个线程获取到一个许可，state的值-1，只有当许可消耗完，也就是state=0时才会恢复队列中挂起的线程。

CPU密集型

IO密集型

时分秒

ArrayBlockingQueue

SynchronousQueue

LinkedBlockingQueue

PriorityBlockingQuene

直接丢弃

丢弃老的

调用当前线程执行任务

异常（默认）

LinkedBlockingQueue

LinkedBlockingQueue

SynchronousQueue

为任务提供延迟或周期执行

原理

ForkJoinPool.defaultForkJoinWorkerThreadFactory

ABA问题

只能保证一个变量的原子操作

循环开销时间长

Unsafe

加载非classpath下的文件

加载网络传输的class

加载需要加解密的class

实现热部署功能

Survivor

Thread Local Allocation Buffer（TLAB）

放置长生命周期的对象，通常都是从 Survivor 区域拷贝过来的对象。

我们知道普通的对象会被分配在 TLAB 上；如果对象较大，JVM 会试图直接分配在 Eden 其他位置上；如果对象太大，完全无法在新生代找到足够长的连续空闲空间，JVM 就会直接分配到老年代。

不会被回收

内存不够时才会被回收

一定会被回收

虚引用与软引用和弱引用的一个区别在于：虚引用必须和引用队列 （ReferenceQueue）联合使用。当垃圾回收器准备回收一个对象时，如果发现它还有虚引用，就会在回收对象的内存之前，把这个虚引用加入到与之 关联的引用队列中。

加锁(效率低)

Lock Free(复杂)

对象引用的对象也会回收，导致效率低

S0/S1,可配置 -XX:SurvivorRatio

Forwarding指针

BFS和DFS的区别是什么

标记-整理算法

不在堆上的引用

CMS解决办法

把剩余的标记

如果年轻代太大，比较耗时，需要先进行一次yong gc

Point In（专属记录集）

Point Out（通用记录集）

记录集

XMLApplicationContext

ClasspathApplicationContext

ImportSelect

Registar

脏读、幻读、不可重复读

脏读、不可重复读

不可重复读（innodb没有）

无

undo log

事务追求的最终目标，一致性的实现既需要数据库层面的保障，也需要应用层面的保障

多个事务之间的隔离

redo log

聚簇索引

非聚簇索引

B+Tree

最左匹配原则

索引要尽量小，这样可以一次可以加载更多数据

IO瓶颈

CPU瓶颈

概念

结果

场景

分析

概念

结果

场景

分析

概念

结果

场景

分析

概念

结果

场景

分析

端上除了partition key只有一个非partition key作为条件查询

端上除了partition key不止一个非partition key作为条件查询

后台除了partition key还有各种非partition key组合条件查询

注：用NoSQL法解决（ES等）

水平扩容库（升级从库法）

水平扩容表（双写迁移法）

raw

int

embstr

ziplist

hashtable

对象，更省空间

quicklist

消息队列

hashtable

intset

签到、点赞

ziplist

skiplist

排行榜

子主题

布隆过滤器

基数统计

连接

同步

命令传播

Raft算法

没1s记录一次日志

恢复慢

文件大

always

no

everysec

日志重写

日志压缩

文件小

恢复快

丢失数据大，不能做到秒级

每次调用bgsave都需要fork子进程，fork子进程属于重量级操作，频繁执行成本较高；

redis原理

将要过期的key

当内存使用超过配置的时候会返回错误，不会驱逐任何键

缓存null

加锁，只能一个线程访问

随机过期时间，不要同时过期

预热加载

加锁同步

写操作：删缓存、修改数据、删缓存

ack=all

手动ack

开启ProducerId

幂等支持

同步刷盘

异步刷盘

ack

手动回执

限流

扩容

将一些日志消息丢弃

基于Guava实现

基于Lua实现

sentinel

Regisger

Provider

Consumer

Monitor

失败自动切换到其他服务器（默认）

快速失败，立即报错

失败安全，直接忽略

失败后记录下来，定时重试

并行调用多个，一个成功就成功

原理

使用案例

原理

使用案例

原理

使用案例

问题

问题

全局事务协调器

基于数据补偿替换回滚

实现复杂

本地事务发起，发送一个MQ消息，本地事务提交则提交这个MQ消息，消费端可消费

实现简单

最终一致，可能会出现不一致

依赖中间件

Try，Commit，Cancel

优点：

缺点：

基于MySQL的锁

单点问题

基于redis的setnx expire

需要考虑超时情况

释放锁没有通知，需要客户端自旋

setnx与expire非原子操作，可能会出现没有过期的情况

基于ZK的临时节点，事件通知

每次要持久化数据，效率低

设置超时

无法获取就释放

Channel

Buffer

Selector

Reactor模式

RocketMQ

Kafka

next

next

previous

next

O(1)

O(1)

O(n)

public void preOrderTraverse1(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + "->");
            preOrderTraverse1(root.left);
            preOrderTraverse1(root.right);
        }
    }

public void preOrderTraverse2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.empty()) {
            if (node != null) {
                System.out.print(node.val + "->");
                stack.push(node);
                node = node.left;
            } else {
                TreeNode tem = stack.pop();
                node = tem.right;
            }
        }
    }

public void inOrderTraverse(TreeNode root) {
        if (root != null) {
            inOrderTraverse(root.left);
            System.out.print(root.val + "->");
            inOrderTraverse(root.right);
        }
    }

public void inOrderTraverse(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode tem = stack.pop();
                System.out.print(tem.val + "->");
                node = tem.right;
            }
        }
    }

public void postOrderTraverse(TreeNode root) {
        if (root != null) {
            postOrderTraverse(root.left);
            postOrderTraverse(root.right);
            System.out.print(root.val + "->");
        }
    }

public void postOrderTraverse(TreeNode root) {
        TreeNode cur, pre = null;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.empty()) {
            cur = stack.peek();
            if ((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))) {
                System.out.print(cur.val + "->");
                stack.pop();
                pre = cur;
            } else {
                if (cur.right != null)
                    stack.push(cur.right);
                if (cur.left != null)
                    stack.push(cur.left);
            }
        }
    }

实现方式

原理

使用场景

// 冒泡排序，a表示数组，n表示数组大小
public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
 
 for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j+1]) { // 交换
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有数据交换      
      }
    }
    if (!flag) break;  // 没有数据交换，提前退出
  }
}

特点

思想

图解

实现方式

优化方式

特点

思想

图解

思想

图解

特点

MapState

ListState

BroadcastState

Tumbling Windows（不重复）

Sliding Windows（重复的）

Session Windows（会话窗口）

自定义窗口

处理时间 Processing Time

事件时间 Event Time

提取时间 Ingestion Time

实现watermark的机制

为了保证一致性

子主题

按列存储与按行存储相比，前者可以有效减少查询时所需扫描的数据量

按列存储相比按行存储的另一个优势是对数据压缩的友好性

子主题

向量化执行，可以简单地看作一项消除程序中循环的优化。

关系模型相比文档和键值对等其他模型，拥有更好的描述能力，也能够更加清晰地表述实体间的关系。