面试题总结
 · 阅读需 57 分钟
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(多版本并发控制)避免了幻读
 - 可串行化:最高级别,每个事务必须依次执行,完全避免并发问题
- 可能导致死锁
 - 需要表级锁或行级锁,影响系统吞吐量
 
 
