Shopee Java一面 整体感觉不难 许愿二面

面试总结：总体不难，算法题脑抽了只过了一半，面试官点出了问题说时间到了，反问一点点，感觉五五开，许愿一个二面

1.Java中的锁机制，什么是可重入锁

Java中的机制主要包括

• synchronized关键字

• Lock接口及其实现类(如ReentrantLock)

• 原子类(如AtomicInteger)

• volatile关键字，仅保证可见性和有序性

可重入锁

可重入锁是指同一个线程在外层方法获取锁的时候,再进入该线程的内层方法会自动获取锁,不会因为之前已经获取过还没释放而阻塞。Java中ReentrantLock和synchronized都是可重入锁。

可重入锁的实现原理:

• 记录锁的持有线程
• 维护一个计数器
• 当计数器为0时,表示锁没有被任何线程持有
• 当持有锁的线程再次请求锁时,计数器+1
• 当线程退出同步代码块时,计数器-1
• 计数器为0时释放锁

可重入锁的优点:

• 避免死锁
• 提高了锁的灵活性

2.AQS (AbstractQueuedSynchronizer)

AQS是Java并发包中的核心基础组件,用于构建锁或者其他同步组件。

AQS使用一个int成员变量表示同步状态,通过内置的FIFO队列来完成资源获取线程的排队工作。

AQS的核心思想:

• 如果被请求的共享资源空闲,则将当前请求资源的线程设置为有效的工作线程,并且将共享资源设置为锁定状态。
• 如果被请求的共享资源被占用,那么就需要一套线程阻塞等待以及被唤醒时锁分配的机制。

AQS的主要方法:

• acquire(int): 独占式获取同步状态
• release(int): 独占式释放同步状态
• acquireShared(int): 共享式获取同步状态
• releaseShared(int): 共享式释放同步状态

AQS的实现:

• 使用一个volatile的int类型的成员变量来表示同步状态
• 使用一个FIFO队列来完成资源获取的排队工作
• 使用CAS来原子性地修改同步状态值

AQS的应用:

• ReentrantLock
• Semaphore
• CountDownLatch
• ReentrantReadWriteLock
• ThreadPoolExecutor

3.Redis相关数据结构,为什么每种数据类型一般都有两种数据结构?

Redis的主要数据结构

• String: 简单动态字符串(SDS)
• List: 双向链表和压缩列表(ziplist)
• Hash: 哈希表和压缩列表
• Set: 哈希表和整数集合(intset)
• Sorted Set: 跳表(skiplist)和压缩列表

每种数据类型一般都有两种数据结构的原因

• 空间和时间的权衡
• 数据量小的时候使用更加紧凑的数据结构,节省内存
• 数据量大的时候转换为普通数据结构,提高操作效率

以Hash为例:

• 当field-value长度较短且个数较少时,使用压缩列表
• 当数据量增大时,转换为哈希表

这种设计能够在内存使用和性能之间取得很好的平衡。

4.JVM相关内存结构,GC

JVM内存结构

1. 堆(Heap)
   • 年轻代(Young Generation)
     • Eden空间
     • Survivor空间(From和To)
   • 老年代(Old Generation)
2. 方法区(Method Area)
   • 永久代(JDK 8之前)/元空间(JDK 8及以后)
3. 程序计数器(Program Counter Register)
4. 虚拟机栈(VM Stack)
5. 本地方法栈(Native Method Stack)

GC(垃圾回收)

垃圾回收算法:

• 标记-清除算法
• 复制算法
• 标记-整理算法
• 分代收集算法

垃圾收集器:

• Serial收集器
• ParNew收集器
• Parallel Scavenge收集器
• Serial Old收集器
• Parallel Old收集器
• CMS收集器
• G1收集器

GC触发时机:

• Minor GC：清理新生代。
• Major GC：清理老年代。
• Full GC：清理整个堆，包括新生代和老年代。

5.HashMap底层原理

HashMap的底层数据结构是数组+链表+红黑树(JDK 1.8及以后)。

主要属性:

• Node<K,V>[] table: 存储数据的数组
• int size: 实际存储的键值对数量
• int threshold: 扩容阈值
• float loadFactor: 负载因子

put操作流程:

1. 对key的hashCode()进行hash操作
2. 计算index = (n - 1) & hash
3. 如果没碰撞,直接放到bucket里
4. 如果碰撞,以链表的形式存在buckets后
5. 如果链表长度超过8,转换为红黑树
6. 如果size超过threshold,进行扩容

get操作流程:

1. 对key的hashCode()进行hash操作
2. 计算index = (n - 1) & hash
3. 遍历该位置上的链表或红黑树

扩容机制:

• 当size超过threshold时进行扩容
• 扩容时,容量变为原来的2倍
• 重新计算每个元素在数组中的位置(再散列)

6.MySQL索引类型,索引失效,覆盖索引,hash索引

MySQL索引类型

• B+树索引(默认)
• Hash索引
• Full-text全文索引

索引失效的情况

• 使用!=或<>操作符
• 使用函数或表达式
• 类型隐式转换
• 使用OR连接条件
• like以%开头
• 不满足最左前缀原则

覆盖索引

查询的数据列恰好是索引的一部分,可以直接从索引中获取数据,不需要回表查询。

Hash索引

• 基于哈希表实现,只有精确匹配才有效
• 不支持范围查询
• 不支持排序
• 不支持部分索引列匹配查找

Hash索引 vs B+树索引:

• Hash索引只支持等值查询,B+树索引支持范围查询
• Hash索引不支持排序,B+树索引天然支持排序
• Hash索引不支持最左前缀匹配,B+树索引支持

7.Spring IOC AOP原理,循环依赖解决

IOC(控制反转)

• 核心是BeanFactory和ApplicationContext
• 通过反射机制实例化bean并建立bean之间的依赖关系
• 管理bean的生命周期

AOP(面向切面编程)

• 核心是ProxyFactory
• 两种代理方式:JDK动态代理和CGLIB
• 通过织入切面来实现功能的统一维护

循环依赖解决

Spring通过三级缓存解决循环依赖

1. 一级缓存，singletonObjects: 完全初始化好的bean
2. 二级缓存，earlySingletonObjects: 实例化但未初始化的bean
3. 三级缓存，singletonFactories: 存放BeanFactory的实例

解决流程:

1. 创建bean实例
2. 将创建的bean实例放入三级缓存
3. 填充属性
4. 如果发现循环依赖,尝试从三级缓存中获取
5. 没有循环依赖,将bean放入一级缓存

构造函数的循环依赖无法解决,因为实例化和初始化是一体的。

8.MyBatis相关,#和$区别

MyBatis是一个优秀的持久层框架,它支持定制化SQL、存储过程以及高级映射。

#{}和${}的区别:

• #{}是预编译处理,会将参数替换为?
• ${}是字符串替换,直接将参数值拼接到SQL中

使用场景:

• #{}用于SQL语句中的值
• ${}用于动态表名、列名等

安全性:

• #{}可以防止SQL注入
• ${}不能防止SQL注入

9.线程池相关,流程,拒绝策略,如何设计线程池最大线程数和核心线程数

线程池执行流程

1. 如果运行的线程少于corePoolSize,则创建新线程来处理请求
2. 如果运行的线程等于或多于corePoolSize,则将请求加入队列
3. 如果无法将请求加入队列,则创建新的线程来处理请求
4. 如果创建新线程使当前运行的线程超出maximumPoolSize,任务将被拒绝

拒绝策略

1. AbortPolicy: 丢弃任务并抛出RejectedExecutionException异常(默认)
2. DiscardPolicy: 丢弃任务,但是不抛出异常
3. DiscardOldestPolicy: 丢弃队列最前面的任务,然后重新尝试执行任务
4. CallerRunsPolicy: 由调用线程处理该任务

如何设计线程池最大线程数和核心线程数

• CPU密集型任务: 线程数 = CPU核心数 + 1
• IO密集型任务: 线程数 = CPU核心数 * (1 + 平均等待时间/平均工作时间)

一般而言:

• 核心线程数 = CPU核心数
• 最大线程数 = CPU核心数 * 2

实际应用中,可以通过压测来确定最优的线程池参数。

10.HashMap和ConcurrentHashMap

HashMap:

• 非线程安全
• 允许null键和null值
• 初始容量16,负载因子0.75
• JDK 1.8后,链表长度超过8会转换为红黑树

ConcurrentHashMap:

• 线程安全
• 不允许null键和null值
• JDK 1.7使用分段锁(Segment)
• JDK 1.8使用CAS+Synchronized

ConcurrentHashMap的实现(JDK 1.8):

• 使用volatile数组保存Node
• 使用CAS操作保证数组的原子性
• 使用Synchronized锁定链表或红黑树的首节点

put操作:

• 如果bucket为空,使用CAS操作放入
• 如果bucket非空,使用Synchronized锁定首节点
• 执行链表或红黑树的插入操作

get操作:

• 不需要加锁,利用volatile的可见性保证

11.红黑树,二叉查找树,红黑树高度差

二叉查找树:

• 左子树所有节点的值均小于根节点的值
• 右子树所有节点的值均大于根节点的值
• 左右子树也分别为二叉查找树
• 时间复杂度: 平均O(logn),最坏O(n)

红黑树:

• 每个节点要么是红色,要么是黑色
• 根节点是黑色
• 每个叶子节点(NIL)是黑色
• 如果一个节点是红色的,则它的子节点必须是黑色的
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

红黑树的高度:

• 最短路径: 全黑节点
• 最长路径: 红黑相间
• 最长路径的长度不会超过最短路径的2倍

红黑树 vs 平衡二叉树:

• 红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作
• 红黑树的统计性能要好于平衡二叉树

12.MySQL索引

MySQL索引类型

1. 普通索引
2. 唯一索引
3. 主键索引
4. 联合/组合索引
5. 全文索引

B+树索引的特点:

• 所有数据都存储在叶子节点
• 叶子节点形成一个单向链表
• 非叶子节点只存储键值信息

索引的优点:

• 加快数据检索速度
• 唯一索引可以保证数据的唯一性
• 加快表与表之间的连接

索引的缺点:

• 占用额外的存储空间
• 降低更新表的速度

13.如何判断链表有环,如何判断树是二叉查找树

判断链表是否有环

快慢指针法

• 定义两个指针,快指针每次移动两步,慢指针每次移动一步
• 如果存在环,两个指针最终会相遇
• 时间复杂度O(n),空间复杂度O(1)

哈希表法

• 遍历链表,将每个节点存入哈希表
• 如果当前节点已在哈希表中,说明存在环
• 时间复杂度O(n),空间复杂度O(n)

判断树是否为二叉搜索树:

中序遍历法

• 对二叉树进行中序遍历,结果应该是升序的

递归法

• 递归判断，利用二叉搜索树的性质，对于每个节点，它的左子节点值必须小于当前节点值，右子节点的值必须大于当前节点值，并且所有节点需要满足这个条件。

14.Redis分布式锁

Redis分布式锁的实现原理

1. 加锁: 使用SETNX命令设置一个键值对,如果键不存在则设置成功并获得锁
2. 解锁: 删除该键值对
3. 超时: 设置键的过期时间,防止死锁

实现细节

1. 使用Lua脚本保证加锁操作的原子性
2. 使用唯一标识符(如UUID)作为值,防止误删其他客户端的锁
3. 考虑Redis主从复制的延迟问题,使用Redlock算法

15.限流算法

• 计数器算法：基于时间窗口的请求数统计。
• 滑动窗口：将计数器细分成多个更小的时间窗口。
• 令牌桶算法：维持一个令牌桶，系统请求需拿到令牌。
• 漏桶算法：确保请求处理的稳定速率，通过漏水的速率控制请求速率。