面试题总结
· 57 min read
java 集合
Collection
存放单一元素
List
- 有序可重复
ArrayList
:Object
数组,不同步,线程不安全- 内部基于动态数组实现,比
Array
使用起来更灵活 - 可以添加
null
值,但是不建议,会难以维护判空异常
- 内部基于动态数组实现,比
Vector
:古早的以Object
数组为基础的LinkedList
:双向链表(1.6 之前是循环链表,1.7 取消了循环),不同步,线程不安全- 因为是由链表构成的,所以不支持随机访问,不能实现
RandomAccess
接口
- 因为是由链表构成的,所以不支持随机访问,不能实现
Set
- 无序不可重复
HashSet
:基于HashMap
实现- 检查重复:对象加入
HashSet
时,会计算hashCode
值来判断对象的加入位置,同时也会与其他加入的对象的hashCode
的值比较,如果没有相符的,则会认为没有重复;否则,会调用equals()
方法来检查hashCode
相等的对象是否真的相同
- 检查重复:对象加入
LinkedHashSet
:HashSet
的子类,通过LinkedHashLMap
实现TreeMap
:红黑树实现
Queue
- 按照特定顺序排序,有序可重复
Comparable
:出自java.lang
包,有一个compareTo(Object obj)
方法Comparator
:出自java.util
包,有一个compare(Object obj1, Object obj2)
方法
Map
以键值对形式存储
-
HashMap
:1.8 之前以数组和链表组成,链表是为了解决哈希冲突存在;之后改成了数组/链表+红黑树(当链表长度超过阈值 8 时,先判断数组是否超过 64,超过,将链表转换为红黑树,没超过,先把数组扩容),线程不安全-
因为线程安全问题,效率高于
HashTable
-
可以存储
Null key
和Null value
,但是null
键只有一个,null
值可以有多个 -
默认初始化大小为 16,每次扩容容量变为原来 2 倍,如果给了初始值,则每次扩容容量为 2 的幂次方大小
-
- 第一个线程:在头节点插入前被调度挂起
- 第二个线程:因为使用的是头插法,原来的头节点插入新链表后,第二个节点头插法插入同一个数组下标下的链表,线程结束
- 第一个线程:把新数组下标中存储第二个线程的更新后的那个头节点,此时尾节点的后继指向了头节点
-
1.8 后,多个线程更新同一个桶的数据会产生数据覆盖的风险
-
-
LinkedHashMap
:继承自HashMap
,底层是基于拉链式散列结构即数组和链表或红黑树组成,另外多加了双向链表,可以头插和尾插数据,线程不安全 -
HashTable
:数组+链表,链表主要为了解决哈希冲突,线程安全(因为内部方法都是用synchronized
修饰的)- 不允许存储
Null key
和Null value
- 不允许存储
-
TreeMap
:红黑树,线程不安全- 实现了
NavigableMap
接口:有了对集合内元素搜索的能力 - 实现了
SortedMap
接口:有了对集合中元素根据键排序的能力,默认是按Key
的升序排序
- 实现了
遍历方式
Concurrenthashmap 是怎么实现线程安全的(具体读写)
- 1.7 之前主要依赖于分段锁 -
Segment
- 由多个
Segment
组成(默认为 16),每个Segment
维护一个HashEntery
数组(数组+链表,类似与 1.7 之前的HashMap
) - 每个
Segment
继承ReetrantLock
,用于实现分段锁,每个锁只锁容器其中一部分数据,多线程访问不会存在锁竞争,提高并发访问率- 因为继承了
ReetrantLock
,所以Segment
是一种可重入锁,扮演锁的角色
- 因为继承了
- 读操作
- 如
get(key)
不会加锁,直接通过volatile
变量保证可见性
- 如
- 写操作
put
、remove
需要锁住单个Segment
,并不会影响其他Segment
- 计算
key
的hash
值,找到Segment
,然后使用Segment
的ReentrantLock.lock()
进行加锁操作 - 插入或删除数据后释放锁
- 由多个
- 1.8 后彻底移除了
Segment
,改用数组+链表+红黑树的数据结构,并使用CAS + Synchronized
实现线程安全- 由
Node<K, V>[] table
作为主数据存储 - 当表长度超过一定阈值(8)时,转换为红黑树
- 锁粒度更细,
synchronized
只锁定当前链表或红黑二叉树的首节点,只要不产生hash
冲突就不会产生并发 - 读操作
get(key)
操作不会加锁:- 计算
key
的hash
值,找到bucket
(数组槽) - 直接读取
table[index]
,如果是链表或红黑树,则遍历查找 - 由于
Node
的value
使用volatile
修饰,所以可以保证可见性,无需加锁
- 计算
- 写操作:
put(key, value)
:- 计算
key
的hash
值,找到数组的index
位置 CAS
方法创建新Node
:如果该bucket
为空,则用CAS
插入新节点,避免加锁Synchronized
锁定链表或红黑树- 如果
CAS
失败,说明该bucket
已有数据,则用synchronized
直接锁定该桶的头节点,进行插入 - 如果是链表,遍历后插入
- 如果是红黑树,按照红黑树规则插入
- 如果
- 计算
- 由
红黑树的优势
红黑树是一种自平衡二叉搜索树( BFS
)
- 优势
- 保持平衡,最坏情况下时间复杂度
O(logn)
- 普通的二叉搜索树(
BFS
)在极端情况下会退化成链表(即高度接近n
),导致O(n)
的查询复杂度 - 红黑树通过旋转和变色操作保持平衡,保证最坏情况下的增删改查操作都维持在
O(logn)
,不会出现严重的退化
- 普通的二叉搜索树(
- 插入、删除效率高
- 插入、删除操作的调整成本较低:自平衡调整(变色 + 最多 2 次旋转)开销较小
- 适用于高并发
- 在
ConcurrentHashMap
中,当桶中的链表长度超过 8 时,转换成红黑树,提高查询性能 - 插入、删除的调整操作相对较少,在并发环境下更稳定,不会频繁进行全书重平衡
- 在
- 空间占用较低
- 红黑树不需要存储额外的平衡因子
- 只需要额外存储 1 位颜色信息(红/黑)
- 保持平衡,最坏情况下时间复杂度
jvm 虚拟机
数据库的隔离级别
定义了多个事务并发执行时的数据可见性,主要用于控制脏读、不可重复读、幻读等问题
- 读未提交:最低的隔离级别,事务可以读取其他未提交事务的数据,并发性高,但数据一致性最差
- 脏读:事务 A 读取了事务 B 未提交的数据,如果 B 回滚, A 读到的数据就是无效的
- 不可重复读:事务 A 多次读取同一行数据,期间事务 B 修改并提交,导致 A 读取的值不一致
- 幻读:事务 A 读取了某个范围的数据,事务 B 插入了新数据,导致 A 重新读取时看到了幻影数据
- 读已提交:只能读取已经提交的数据,避免了脏读,比读未提交安全,仍支持较高的并发性
- 不可重复读、幻读
- 可重复读:事务执行期间,读取的所有数据保持一致,防止不可重复读。
- 幻读
Mysql InnoDB
通过MVCC
(多版本并发控制)避免了幻读
- 可串行化:最高级别,每个事务必须依次执行,完全避免并发问题
- 可能导致死锁
- 需要表级锁或行级锁,影响系统吞吐量