你知道的数据结构有哪些
线性结构
● 动态数组：相对于普通数组可以扩容
○ java 中 ArrayList 就属于动态数组
○ 数组的特点是其中元素是连续存储的
● 链表：由多个节点链在一起
○ java 中的 LinkedList 就属于链表
○ 链表的特点是其中元素是不连续存储的，每次需要根据当前节点，才能找到相邻节点
● 栈：符合 First In Last Out（先进后出）规则
○ java 中的 LinkedList 可以充当栈
○ 它的 push 方法向栈顶添加元素
○ 它的 pop 方法从栈顶移除元素
○ 它的 peek 方法从栈顶获取元素（不移除）
● 队列：符合 First In First Out（先进先出）规则
○ java 中 LinkedList 也可以充当队列
○ 它的 offer 方法用来向队列尾部添加元素（入队）
○ 它的 poll 方法用来从队列头部移除元素（出队）
非线性结构
● 优先级队列：在队列基础上增加了优先级，队列会根据优先级调整元素顺序，保证优先级高的元素先出队
○ java 中 PriorityQueue 可以作为优先级队列
○ 它底层用大顶堆或小顶堆来实现
○ 它适用于实现排行榜、任务调度等编码
○ 它特别适合于流式数据的处理，利用它能够大大节省内存
● Hash 表（哈希表，也叫散列表）：由多对 key - value 组成，会根据 key 的 hash 码把它们分散存储在数组当中，其中 key 的 hash 码与数组索引相对应
○ java 中的 HashMap，Hashtable 都属于哈希表
○ 它特别适用于实现数据的快速查找
● 红黑树：可以自平衡的二叉查找树，相对于线性结构来说，拥有更好的性能
○ java 中的 TreeMap 属于红黑树
● 跳表：多级链表结构，也能达到与红黑树同级的性能，且实现更为简单
○ java 中的 ConcurrentSkipListMap 用跳表结构实现
○ redis 中的 SortedSet 也是用跳表实现
● B+ 树：可以自平衡的 N 叉查找树
○ 关系型数据库的索引常用 B+ 树实现
P.S.
● 以上数据结构不必全部掌握，根据自己实际情况，捡熟悉的回答即可
● 以上仅是这些数据结构的简述，关于它们的详细讲解，请参考黑马《数据结构与算法》课程：
○ 上篇 https://www.bilibili.com/video/BV1Lv4y1e7HL
○ 下篇 https://www.bilibili.com/video/BV1rv4y1H7o6
2.2 说说 java 中常见的集合类
重要的集合接口以及实现类参考下图
classDiagram
class Collection {<>}
class List {<>}
class Set {<>}
class Map {
<>
entrySet()
keySet()
values()*
}
Collection <|-- List
Collection <|-- Set
List <|.. ArrayList
List <|.. LinkedList
List <|.. Vector
Set <|.. HashSet
Map <|.. HashMap
Map <|.. TreeMap
Map <|.. Hashtable
Map <|.. ConcurrentHashMap
HashMap <|.. LinkedHashMap
Set <-- Map
Collection <-- Map
接口
● 接口四个：Collection、List、Set、Map，它们的关系：
○ Collection 是父接口，List 和 Set 是它的子接口
● Map 接口与其它接口的关系
○ Map 调用 entrySet()，keySet() 方法时，会创建 Set 的实现
○ Map 调用 values() 方法时，会用到 Collection 的实现
List 实现（常见三个）
● ArrayList 基于数组实现
○ 随机访问（即根据索引访问）性能高
○ 增、删由于要移动数组元素，性能会受影响
○ 【进阶】但如果增、删操作的是数组尾部不牵涉移动元素
● LinkedList 基于链表实现
○ 随机访问性能低，因为需要顺着链表一个个才能访问到某索引位置
○ 增、删性能高
○ 【进阶】说它随机访问性能低是相对的，如果是头尾节点，无论增删改查都快
○ 【进阶】说它增删性能高也是有前提的，并没有包含定位到该节点的时间，把这个算上，增删性能并不高
● Vector 基于数组实现
○ 相对于前两种 List 实现是线程安全的
○ 【进阶】一些说法说 Vector 已经被舍弃，这是不正确的
Set 实现
● HashSet 内部组合了 HashMap，利用 Map key 唯一的特点来实现 Set
○ 集合中元素唯一，注意需要为元素实现 hashCode 和 equals 方法
○ 【进阶】Set 的特性只有元素唯一，有些人说 Set 无序，这得看实现，例如 HashSet 无序，但TreeSet 有序
Map 实现（常见五个）
● HashMap 底层是 Hash 表，即数组 + 链表，链表过长时会优化为红黑树
○ 集合中 Key 要唯一，并且它需要实现 hashCode 和 equals 方法
● LinkedHashMap 基于 HashMap，只是在它基础上增加了一个链表来记录元素的插入顺序
○ 【进阶】这个链表，默认会记录元素插入顺序，这样可以以插入顺序遍历元素
○ 【进阶】这个链表，还可以按元素最近访问来调整顺序，这样可以用来做 LRU Cache 的数据结构
● TreeMap 底层是红黑树
● Hashtable 底层是 Hash 表，相对前面三个实现来说，线程安全
○ 【进阶】它的线程安全实现方式是在 put，get 等方法上都加了 synchronized，锁住整个对象
● ConcurrentHashMap 底层也是 Hash 表，也是线程安全的
○ 【进阶】它的 put 方法执行时仅锁住一个链表，并发度比 Hashtable 高
○ 【进阶】它的 get 方法执行不加锁，是通过 volatile 保证数据的可见性
P.S.
● 未标注的是必须记住的部分
● 标注【进阶】的条目是该集合比较有特色的地方，回答出来就是加分项，不过也根据自己情况来记忆
2.3 HashMap 原理（数据结构）
底层数据结构：数组+链表+红黑树
接下来的回答中要点出数组的作用，为啥会有冲突，如何解决冲突
● 数组：存取元素时，利用 key 的 hashCode 来计算它在数组中的索引，这样在没有冲突的情况下，能让存取时间复杂度达到 O(1)
● 冲突：数组大小毕竟有限，就算元素的 hashCode 唯一，数组大小是 n 的情况下要放入 n+1 个元素，根据鸽巢原理，肯定会发生冲突
● 解决冲突：一种办法就是利用链表，将这些冲突的元素链起来，当然在在此链表中存取元素，时间复杂度会提高为 O(n)
接下来要能说出为什么在链表的基础上还要有红黑树
● 树化目的是避免链表过长引起的整个 HashMap 性能下降，红黑树的时间复杂度是 O(log{n})
有一些细节问题可以继续回答，比如树化的时机【进阶】
● 时机：在数组容量达到 >= 64 且 链表长度 >= 8 时，链表会转换成红黑树
● 如果树中节点做了删除，节点少到已经没必要维护树，那么红黑树也会退化为链表
2.4 HashMap 原理（扩容）
扩容因子：0.75 也就是 3/4
● 初始容量 16，当放入第 13 个元素时（超过 3/4）时会进行扩容
● 每次扩容，容量翻倍
● 扩容后，会重新计算 key 对应的桶下标（即数组索引）这样，一部分 key 会移动到其它桶中
2.5 HashMap 原理（方法执行流程）
以 put 方法为例进行说明
- 产生 hash 码。
a. 先调用 key.hashCode() 方法
b. 为了让哈希分布更均匀，还要对它返回结果进行二次哈希，这个结果称为 hash
c. 二次哈希就是把 hashCode 的高 16 位与低 16 位做了个异或运算 - 搞定数组。
a. 如果数组还不存在，会创建默认容量为 16 的数组，容量称为 n
b. 否则使用已有数组 - 计算桶下标。
a. 利用 (n - 1) & hash 得到 key 对应的桶下标（即数组索引）
b. 也可以用 hash % n 来计算，但效率比前面的方法低，且有负数问题
c. 用 (n - 1) & hash 有前提，就是容量 n 必须是 2 的幂（如 16，32，64 ...） - 计算好桶下标后，分三种情况
a. 如果该桶位置还空着，直接根据键值创建新的 Node 对象放入该位置即可
b. 如果该桶是一条链表，沿着链表找，看看是否有值相同的 key，有走更新，没有走新增
■ 走新增逻辑的话，是把节点链到尾部（尾插法）
■ 新增后还要检查链表是否需要树化，如果是，转成红黑树
■ 新增的最后要检查元素个数 size，如果超过阈值，要走扩容逻辑
c. 如果该桶是一棵红黑树，走红黑树新增和更新逻辑，同样新增的最后要看是否需要扩容
P.S.
● 以上讲解基于 jdk 1.8 及以上版本的 HashMap 实现
● 考虑到 jdk 1.7 已经很少使用了，故不再介绍基于 1.7 的 HashMap，有需求可以看 b 站黑马面试视频
3、网络编程
3.1 说说 BIO、NIO、AIO
问这个问题，通常是考察你对 Web 应用高并发的理解
预备知识
● 开发 Web 应用，肯定分成客户端和服务器。
● 客户端与服务器交互，肯定得做这么几件事：
○ 服务器线程等待有客户端连接上来
○ 客户端真的连上来了，建立连接
○ 客户端没有向服务器发送请求，此时服务器线程需要等待数据准备好
○ 客户端向服务器发送请求，需要将请求数据从网卡复制到系统内存
● 上面 a. c. 这两个阶段，没有客户端连接，没有数据请求，这时是否需要一个线程时刻盯着？
○ 如果需要占用一个线程，那么就称线程被阻塞
○ 如果不需要线程盯着，线程可以腾出手来去干别的活，那么就称线程非阻塞
● d. 阶段的数据复制，不会用到 CPU，也就是不会用到线程，同样也存在线程阻塞还是线程非阻塞两种情况
BIO（阻塞 I/O）
● 是指 b. c. d.这几个阶段，线程都得阻塞，腾不出手干别的，即使此时它无所事事
● 高并发下，阻塞线程多了，处理连接、处理请求的能力就会大受影响
○ 增加线程不可行，毕竟线程是有限资源，这是成本问题
○ 不增加线程也不行，没有新线程，没人去处理新连接，处理新请求
NIO（非阻塞 I/O）
● 是指 b. c. 这两个阶段，线程可以不阻塞，腾出手干别的（怎么干别的，要靠多路复用）
● 非阻塞 I/O 通常结合多路复用技术一起使用，能够在高并发下用少量线程处理大量请求
○ 多路复用是以面向事件的方式处理连接、处理请求，有事件发生才去处理，没有事件则不会占用线程
○ 使用了多路复用技术后，新客户端来了要连接，客户端发来了新请求，都会产生事件，把这些事件交给一个线程去统一处理就行了
○ 线程不会在高并发下存在无事可做的现象，它被充分压榨，利用率高
AIO（异步 I/O）
● NIO 在 d. 这个阶段，线程仍需阻塞，不能被解放出来干其它活
● AIO 则更进一步，只需要提前准备好回调函数，在数据复制时线程被解放，该干嘛干嘛，等数据复制完毕，由系统使用另外线程来调用回调函数做后续处理
● AIO 在 Linux 下本质还是用多路复用技术来实现
小结
● BIO 并发性低，但代码更容易编写
● NIO 并发性高，不过代码编写困难
● AIO 并发性在 Linux 下没有本质提高，用的人少
● 【进阶】Java 21 起，正式支持虚拟线程
○ 配合虚拟线程时，仍然是以 BIO 方式来编写代码，代码编写容易
○ 虚拟线程非常廉价，线程不是不够吗，可劲加就行（不用担心线程闲置问题）
○ Java 21 重新实现了网络 API，虚拟线程底层也会配合多路复用机制，在代码易编写的情况下，兼具高性能
P.S.
● B 是 Blocking 阻塞
● N 是 Non-Blocking 非阻塞
● A 是 Asynchronous 异步
