后台面试

No tag

Publish Date: 2020-03-12

Word Count: 5.8k

HashMap机制

哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题

实现原理：
HashMap本质是一个一定长度的数组，数组中存放的是链表。
它是一个Entry类型的数组，Entry的源码：

static class Entry<K,V> implements Map.Entry<K,V> {  
        final K key;  
        V value;  
        final int hash;  
        Entry<K,V> next;  
}

其中存放了Key，Value，hash值，还有指向下一个元素的引用。

当向HashMap中put(key,value)时，会首先通过hash算法计算出存放到数组中的位置，比如位置索引为i，将其放入到Entry[i]中，如果这个位置上面已经有元素了，那么就将新加入的元素放在链表的头上，最先加入的元素在链表尾。

HashMap的get(key)方法是：首先计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。从这里我们可以想象得到，如果每个位置上的链表只有一个元素，那么hashmap的get效率将是最高的。所以我们需要让这个hash算法尽可能的将元素平均的放在数组中每个位置上。

确定哈希桶数组索引位置

  // 方法一，jdk1.8 & jdk1.7都有：
  static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
  // 方法二，jdk1.7有，jdk1.8没有这个方法，但是实现原理一样的：
  static int indexFor(int h, int length) {
       return h & (length-1);  
  }123456789

这里的Hash算法本质上就是三步：
(1) 取key的hashCode值，h = key.hashCode()；
(2) 高位参与运算，h ^ (h >>> 16)；
(3) 取模运算，h & (length-1)。

对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。

这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

扩容机制：

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容。

HashMap的容量由一下几个值决定：

  int threshold;             // 扩容阈值 
  final float loadFactor;    // 负载因子
  transient int modCount;  // 出现线程问题时，负责及时抛异常
  transient int size;     // HashMap中实际存在的Node数量

HashMap的容量size乘以负载因子[默认0.75] = threshold; // threshold即为开始扩容的临界值

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; // HashMap的基本构成Entry数组

当HashMap中的元素个数超过数组threshold时，就会进行数组扩容, 数组默认大小为16，那么当HashMap中元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩大一倍，然后重新计算每个元素在数组中的位置。

HashMap不是无限扩容的，当达到了实现预定的MAXIMUM_CAPACITY，就不再进行扩容。

Hashmap为什么大小是2的幂次？

相对来说素数导致冲突的概率要小于合数，HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时减少冲突

get方法实现

Hashmap get一个元素是，是计算出key的hashcode找到对应的entry，这个时间复杂度为O(1)，然后通过对entry中存放的元素key进行equal比较，找出元素，这个的时间复杂度为O(m)，m为entry的长度。

线程安全

主要是多线程同时put时，如果同时触发了rehash操作，会导致HashMap中的链表中出现循环节点，进而使得后面get的时候，会死循环。

6、TCP拥塞机制

拥塞的标志

1.重传计时器超时
2.接收到三个重复确认

TCP的拥塞控制由4个核心的算法组成：慢启动（slow start）、拥塞避免（Congestion voidance）、快速重传（Fast Retransmit）和快速恢复（Fast Recovery）。

在发送方维持着一个拥塞窗口cwmd（congestion window）的状态量

慢开始

发送的最初执行慢开始，令 cwnd = 1，发送方只能发送 1 个报文段；当收到确认后，将 cwnd 加倍

拥塞避免

设置一个慢开始门限 ssthresh，当 cwnd >= ssthresh 时，进入拥塞避免，每个轮次只将 cwnd 加 1。如果出现了超时，则令 ssthresh = cwnd / 2，然后重新执行慢开始。

快重传

发送方只要一连收到三个重复确认就应当立即重传对方尚未收到的报文段，而不必继续等待设置的重传计时器时间到期。

快恢复

1.当发送方连续收到三个重复确认时，就执行“乘法减小”算法，把ssthresh门限减半
2.考虑到如果网络出现拥塞的话就不会收到好几个重复的确认，所以发送方现在认为网络可能没有出现拥塞。所以此时不执行慢开始算法，而是将cwnd设置为ssthresh的大小，然后执行拥塞避免算法。
增加快重传与快恢复

7、如果没有拥塞机制会怎样

我们知道TCP通过一个定时器（timer）采样了RTT并计算RTO，但是，如果网络上的延时突然增加，那么，TCP对这个事做出的应对只有重传数据，然而重传会导致网络的负担更重，于是会导致更大的延迟以及更多的丢包，这就导致了恶性循环，最终形成“网络风暴”

8、TCP流量控制

原理：让发送方的发送速率不要太快，要让接收方来得及接收。

原则：发送方的发送窗口不能超过接收方给出的接收窗口的数值。

滑动窗口协议

如果发送窗口左部的字节已经发送并且收到了确认，那么就将发送窗口向右滑动一定距离，直到左部第一个字节不是已发送并且已确认的状态

9、TCP怎么保证安全机制

TCP协议保证数据传输可靠性的方式主要有：

校验和
序列号
确认应答
超时重传
连接管理
流量控制
拥塞控制

10、TCP头部字段

1337910993_8515

●顺序号字段：占32比特。用来标识从TCP源端向TCP目标端发送的数据字节流，它表示在这个报文段中的第一个数据字节。

●确认号字段：占32比特。只有ACK标志为1时，确认号字段才有效。它包含目标端所期望收到源端的下一个数据字节。

●标志位字段（U、A、P、R、S、F）：占6比特。各比特的含义如下：

　　◆URG：紧急指针（urgent pointer）有效。

　　◆ACK：确认序号有效。

　　◆PSH：接收方应该尽快将这个报文段交给应用层。

　　◆RST：重建连接。

　　◆SYN：发起一个连接。

　　◆FIN：释放一个连接。　　

●窗口大小字段：占16比特。此字段用来进行流量控制。单位为字节数，这个值是本机期望一次接收的字节数。

11、TCP什么时候发送复位包

一、RST介绍
RST：重置连接、复位连接，用来关闭异常的连接。

发送RST包关闭连接时，不必等缓冲区的包都发出去，直接就丢弃缓冲区中的包，发送RST。
而接收端收到RST包后，也不必发送ACK包来确认

二、什么时候发送RST包

建立连接的SYN到达某端口，但是该端口上没有正在监听的服务。
TCP收到了一个根本不存在的连接上的分节。
请求超时。使用setsockopt的SO_RCVTIMEO选项设置recv的超时时间。接收数据超时时，会发送RST包。

13、TCP心跳包机制

为什么需要心跳机制？

采用TCP连接的C/S模式软件，连接的双方在连接空闲状态时，如果任意一方意外崩溃、宕机、网线断开或路由器故障，另一方无法得知TCP连接已经失效，除非继续在此连接上发送数据导致错误返回。

心跳机制是定时发送一个自定义的结构体(心跳包)，让对方知道自己还活着，以确保连接的有效性的机制。

一方开启KeepAlive功能后，就会自动在规定时间内向对方发送心跳包，而另一方在收到心跳包后就会自动回复，以告诉对方我仍然在线。

心跳检测步骤：
1.客户端每隔一个时间间隔发生一个探测包给服务器
2.客户端发包时启动一个超时定时器
3.服务器端接收到检测包，应该回应一个包
4.如果客户机收到服务器的应答包，则说明服务器正常，删除超时定时器
5.如果客户端的超时定时器超时，依然没有收到应答包，则说明服务器挂了

14、操作系统虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。

深度截图_选择区域_20200308093315

15、虚拟地址和物理地址转换

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

深度截图_plasmashell_20200308103023

深度截图_plasmashell_20200308103943

16、进程和线程区别

根本区别：进程是操作系统资源分配的基本单位，线程是CPU调度和执行的基本单位

拥有资源：系统会为每个进程分配内存资源，线程只能访问隶属进程的资源。

系统开销：每个进程都有独立的代码和数据空间。进程的创建和关闭会有较大的开销，线程是共享代码和数据空间。切换代价小。

通信方式：线程可以通过共享资源通信，进程必须借助PIC

进程的调度算法：

批处理系统
- 先到先服务
- 时间最短
- 剩余时间最短
交互系统
- 时间片轮转
- 优先级调度
- 多级反馈队列

17、为什么需要进程，他存在的意义

并发：
- 间断性
- 失去封闭性：系统资源不专属于一个程序
- 不可再现性：不同程序都有对资源修改的权利，程序的输出结果不一定。
引入进程
- 解决了封闭性问题
  - 进程是系统进行资源分配的独立单位。
  - 进程=数据段+程序段+PCB
- PCB
  - 调度进程时，根据PCB中记录的程序或数据的起始指针，找到进程。
  - 存储进程的状态。
  - PCB中有通讯区域和消息队列指针。

18、进程切换怎么实现的

19、数据库索引结构

B+Tree结构

MySql存储引擎：

InnoDB：聚集索引

1. InnoDB按照B+Tree组建索引必须要有主键，没主键建不了表，
 2. 推荐整型主键是方便比较，提高效率。
 3. 自增主键是：顺序插入B+Tree，不会出现多余的分裂情况。例如节点大小为3，已经有07，09，10，插入08的时候会分裂，耗费资源。

深度截图_选择区域_20200310105220

MyiSam：非聚集索引

20、辅助索引和覆盖索引、聚族索引

聚集索引就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的即为整张表的行记录数据。
如果定义了主键，InnoDB会自动使用主键来创建聚集索引。如果没有定义主键，InnoDB会选择一个唯一的非空索引代替主键。如果没有唯一的非空索引，InnoDB会隐式定义一个主键来作为聚集索引。
辅助索引，也叫非聚集索引。和聚集索引相比，叶子节点中并不包含行记录的全部数据
覆盖索引，即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。

22、意向锁

隔离级别：
- 读未提交（read-uncommitted）：用户A读到用户B修改后但并未提交的数据，（脏读）
- 读已提交（read-committed）：用户A只能读到用户B提交的内容（不可重复读：B提交前后读到的数据不一致）
- 可重复读（repeatable-read）：A，B 开启事务，无论用户B对修改提交与否，如果用户A不提交事务，只会读到修改前的内容，A提交后在次查询会显示修改后的内容，
  只要A没有提交和回滚，A的查询的结果和开事务时的数据是一致的。（幻读：新开事务后读到的数据和上次不一样）
- 穿行化（serializable）:B事务修改数据，会阻塞，等到A事务提交后，B事务会结束修改。
InnoDB的锁机制
- 共享锁
  - S锁，读锁，如果A获取了某一行的读锁，其他会话只能读数据，不能修改该行。（行级锁）
```
select * from account where id=1 lock in share mode;
# 对id=1这一行加共享锁。
```
- 排他锁
  - X锁，写锁，只允许当前事务修改或删除某一行数据。（行级锁）
```
select * from account where id=1 for update;
# 对id=1这一行加排他锁。
```
- 意向锁（表级锁）
  - IS（意向共享锁）
  - IX（意向排他锁）
  - 意向锁存在的意义在于，使得行锁和表锁能够共存，用来说明事务稍后会对表中的数据行加哪种类型的锁(共享锁或独占锁)
  - 当一个事务对表加了意向排他锁时，另外一个事务在加锁前就会通过该表的意向排他锁知道前面已经有事务在对该表进行独占操作，从而等待。
- 自增锁（表级锁）
  - 如果一个事务正在向表中插入值，那么任何其他事务都必须等待，保证第一个事务插入的行是连续的自增值。
- 间隙锁
  - 锁定索引之间的间隙，但是不包含索引本身
- 记录锁
  - 锁定一个记录上的索引，而不是记录本身。如果一个表没有定义索引，那么就会去锁定隐式的“聚集索引”。
- 临键锁
  - Next-Key Locks是行锁与间隙锁的组合。它是 Record Locks 和 Gap Locks 的结合，不仅锁定一个记录上的索引，也锁定索引之间的间隙。它锁定一个前开后闭区间，例如一个索引包含以下值：10, 11, 13, and 20，那么就需要锁定以下区间：
```
(-∞, 10]
(10, 11]
(11, 13]
(13, 20]
(20, +∞)
```
InnoDB行锁，锁什么？
- 行锁就是给索引上锁。无索引时行锁升级为表锁。
MVCC（多版并发控制系统）
- MVCC是 MySQL 的 InnoDB 存储引擎实现隔离级别的一种具体方式，用于实现提交读和可重复读这两种隔离级别。
- 基本思想：
  - 而 MVCC 利用了多版本的思想，写操作更新最新的版本快照，而读操作去读旧版本快照。
  - 在 MVCC 中事务的修改操作（DELETE、INSERT、UPDATE）会为数据行新增一个版本快照。
  - 为了解决脏读和不可重复读问题，MVCC 规定只能读取已经提交的快照
- 版本号，undo日志（回滚指针->链接数据行所有快照），readview（事务ID列表，判断快照是否可用）。
- 快照读，读取的是记录的可见版本 (有可能是历史版本)，不用加锁。
- 当前读，读取的是记录的最新版本，并且，当前读返回的记录，都会加上锁，保证其他事务不会再并发修改这条记录。

23、什么情况会造成数据库的死锁

死锁发生的条件：
1、资源不能共享，需要只能由一个进程或者线程使用
2、请求且保持，已经锁定的资源自给保持着不释放
3、不剥夺，自给申请到的资源不能被别人剥夺
4、循环等待
处理死锁：
- 尽量避免并发地执行涉及到修改数据的语句。
- 要求每个事务一次就将所有要使用的数据全部加锁，否则就不予执行。
- 每个事务的执行时间不可太长，在业务允许的情况下可以考虑将事务分割成为几个小事务来执行
出现死锁的情况
- 事务A：update A，updateB；
- 事务B：updateB，updateA；
- 事务A 给A表加锁，事务B给B表加锁，接下来执行会一直等待下去。（你中有我，我中有你）

24、那种语句会造成数据库死锁
25、主从复制

主从复制主要涉及三个线程：

binlog线程（主服务器）：将日志以二进制日志形式存储在服务器
I/O线程（从服务器）：获取主服务器的二进制日志，存储在本地称为中继日志
SQL线程（从服务器）：读取中继日志，重现日志操作。

26、红黑树的实现

27、一范式、二范式和三范式

1NF:列满足原子性。
2NF：满足一范式，消除了非主属性对码的部分函数依赖。
- 函数依赖：X确定，那么Y也一定确认。
- 完全依赖：x是一个属性，那么Y对于X就是完全函数依赖
- 部分依赖：X是一组属性，Y依赖与X的某个真子集。
- 传递依赖：x->Y->Z
3NF：满足二范式，消除了非主属性对于码的传递函数依赖。

28、所有排序的思路

算法概览

冒泡排序
- 算法描述：
  - 两两比较，根据大小交换顺序。（一轮只能排出一个有序元素）
选择排序
- 算法描述
  - 从第一个位置开始，从未排序的序列中找到最小值排在有序序列的末尾。
插入排序
- 算法描述
  - 初始时，第一个元素有序，第二个元素以后无序。
  - 从无序序列头部开始，从右向左比较，合适位置插入。大的元素向后移一位。
  - 遍历完所有无序序列内容。
希尔排序
- 算法描述
  - 选择自减的增量序列
  - 按照序列元素个数K，对序列进行K趟排序
归并排序
- 算法描述（二路）
  - 将序列分成两个子序列
  - 对两个子序列分别递归调用归并排序
  - 将两个子序列和起来
快速排序
- 算法描述
  - 选出一个基值（povt）/我选第一个元素
  - 比基值小的放到基值左边，大的放在基值右边。/左右指针向中间移动。
  - 再对左右像个子序列重复上述操作/递归调用
堆排序
- 算法描述
  - 将输入序列构成大顶堆
  - 堆顶元素和最后元素交换。砍断对后一个元素。
  - 堆化
    - 自顶向下：每三个节点比较将最大的元素放在父节点上，从上至下，依次比较
    - 自下向上：根据堆的最后一个节点找到其父节点，每三个节点进行比较，大元素放在父节点。依次向上比较。
  - 重复2，3步骤，直至堆都被砍完。
计数排序
- 算法描述
  - 找出序列的最大值，最小值
  - 新建数组C，下标起始和结束就是最小最大值（或建立关系）
  - 遍历序列，数组中记录下标数字出现的次数。
  - 将数组C中的数字，按次数从左到右放到原序列中
桶排序
- 算法描述
  - 人为设置桶大小。
  - 遍历数组，并把数据放入对应的桶中。
  - 对桶内的数据排序（可以别的排序算法）
  - 按桶顺序将数据连起来。
基数排序
- 算法描述
  - 取得数组中的最大数，并取得位数；
  - arr为原始数组，从最低位开始取每个位组成radix数组；
  - 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
- 基数排序： 根据键值的每位数字来分配桶
- 计数排序： 每个桶只存储单一键值
- 桶排序： 每个桶存储一定范围的数值

29、为什么堆排序比快排慢

第一、堆排序访问数据的方式没有快速排序友好。
- 对于快速排序来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的,对cpu缓存不友好。
第二、对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。

30、哪种排序比快排快

桶排序 O（n+k）
- 但是实际应用中快排更普遍。桶排序对数据有一定的要求，能够较均匀的分配在一个桶中。
计数排序 O（n+k）

Maelsee

https://maelsee.github.io/posts/7e9d.html

All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Maelsee !

No tag

Django

Django面试问题Http 请求方法 GET 向特定的路径资源发出请求 POST 向指定路径资源提交数据进行处理请求（一般用于提交表单或者上传文件）数据被包含在请求体中，POST请求可能会导致新的资源的建立和/或已有资源的修改。

2020-03-12 面试

剑指offer算法题

把数组排成最小的数题目输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。示例 1: 输入: [10,2] 输出: "102" 分析题目要求，数组中有ｍ和ｎ，如果m

2020-03-06 算法