面经个人总结

摘要:

暂无摘要

序章

  • 你有哪些特长
  • 对于项目:
    1. 这是一个怎样的项目
    2. 用到了什么技术,为什么用这项技术(以及每项技术很细的点以及扩展)
    3. 过程中遇到了什么问题,怎么解决的
  • 自我介绍
  • 可以提问的问题:部门的业务,实习生的培养机制

算法

  • 快速排序:当基准数选择最左边的数字时,那么就应该先从右边开始搜索;当基准数选择最右边的数字时,那么就应该先从左边开始搜索。不论是从小到大排序还是从大到小排序!否则会得到错误的结果。最好情况是基准数选得好,每次都能等分数列时,复杂度为O(nlogn)。最差情况是已经正序或者逆序,复杂度为O(n^2)。平均为O(nlogn)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    //从小到大(如果是从大到小,只需要将代码中两个不等号改一下)
    void quick_sort(int left, int right, vector<int> & arr){
    if(left >= right) {
    return;
    }
    int i = left, j = right, base = arr[left], temp;
    while(i < j) {
    while(arr[j] >= base && i < j) { //如果是从大到小需要将>=改成<=
    j--;
    }
    while(arr[i] <= base && i < j) { //如果是从大到小需要将<=改成>=
    i++;
    }
    if(i < j) {
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    }
    }
    arr[left] = arr[i];
    arr[i] = base;
    quick_sort(left, i - 1, arr);
    quick_sort(i + 1, right, arr);
    }

    第六行有一点需要注意:i的初始值不能设置为left+1,而是应该和left相同。以4567为例就可以知道哪里会出问题。

  • 冒泡排序(是a[j]和a[j+1]比较不是a[i]和a[j]比较啊)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for (i = 0; i< N - 1; i++) { //控制n-1趟冒泡
    for (j = 0; j < N - 1 - i; j++)
    {
    if (a[j] > a[j + 1]) { //如果是降序,将>改成<即可
    int tmp;
    tmp = a[j];
    a[j] = a[j + 1];
    a[j + 1] = tmp;
    }
    }
    }
  • 二分查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    bool BinarySearch(int target, vector<int> vec) {
    int left = 0, right = vec.size() - 1;
    while (left < right) {
    mid = left + (right - left) / 2;
    if (mid == target) {
    return true;
    } else if (mid < target) {
    left = mid + 1;
    } else {
    right = mid - 1;
    }
    }
    return false;
    }

    写完才发现,这个挺简单的没必要写在这=_=

  • 归并排序

    1
     

数据结构

  • hashmap原理:

    首先分配一大片内存,形成许多桶。是利用hash函数,对key进行映射到不同区域(桶)进行保存。其插入过程是:

    1. 得到key 
    2. 通过hash函数得到hash值 
    3. 得到桶号(一般都为hash值对桶数求模) 
    4. 存放key和value在桶内。 

    其取值过程是:

    1. 得到key 
    2. 通过hash函数得到hash值 
    3. 得到桶号(一般都为hash值对桶数求模) 
    4. 比较桶的内部元素是否与key相等,若都不相等,则没有找到。 
    5. 取出相等的记录的value。
  • 前序遍历,中序遍历,后序遍历

    前序遍历(根左右),中序遍历(左根右),后序遍历(左右根)

    中序遍历非递归算法:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    //中序遍历
    void InOrderWithoutRecursion2(BTNode* root)
    {
    //空树
    if (root == NULL)
    return;
    //树非空
    BTNode* p = root;
    stack<btnode*> s;
    while (!s.empty() || p)
    {
    if (p)
    {
    s.push(p);
    p = p->lchild;
    }
    else
    {
    p = s.top();
    s.pop();
    cout << setw(4) << p->data;
    p = p->rchild;
    }
    }
    }
  • 二叉树,平衡二叉树

    平衡二叉树:节点的平衡因子是节点的左右子树的深度之差,平衡二叉树是任意节点的平衡因子的绝对值小于等于1的二叉树。

    平衡化旋转:插入一个新节点后,需要从插入的新节点处沿通向根的方向回溯,如果在某一节点发现不平衡,就从发生不平衡的节点起,沿刚刚回溯的路径取直接下两层的节点,进行旋转。

    • b树,b+树:减少查询磁盘IO,速度快。数据库的底层索引是用b+树实现的

      b树:各节点中最多的数据存储量为阶。每个节点可以存多个数据

      b+树:非叶子节点只存放索引,所有的数据都在叶子节点。

      b+树优点:

    1. 每个非叶子节点只充当索引,单一节点存储的元素更多,相同的内存可以存放更多索引数据
  1. 所有的查询都要查找到叶子节点,查询性能是稳定的,而B树,每个节点都可以查找到数据,所以不稳定。
    1. 所有的叶子节点形成了一个有序链表,更加便于查找。
  • 为什么要用B+树,为什么不用红黑树和B树)

    B+树是一种特殊的平衡多路树,是B树的优化改进版本,它把所有的数据都存放在叶节点上,中间节点保存的是索引。这样一来相对于B树来说,减少了数据对中间节点的空间占用,使得中间节点可以存放更多的指针,使得树变得更矮,深度更小,从而减少查询的磁盘IO次数,提高查询效率。另一个是由于叶节点之间有指针连接,所以可以进行范围查询,方便区间访问。

    红黑树是二叉的,它的深度相对B+树来说更大,更大的深度意味着查找次数更多,更频繁的磁盘IO,所以红黑树更适合在内存中进行查找。

  • map与unordered_map

    map通过红黑树实现,自动有序。unordered_map通过hash实现,无序但是查找的时间复杂度为O(1)

    map费空间,unordered_map构建时比较慢

操作系统

  • 进程是一个程序在给定的活动空间和初始环境下,在一个处理机上的执行过程。

  • 进程的三个基本状态:运行状态,等待状态(进程正在等待某一事件的发生,即使给他CPU控制权也无法执行),就绪状态(万事俱备,只欠CPU)

    线程的状态变迁图是一样的

  • 线程是比进程更小的活动单位,他是进程中的一个执行路径。

  • 进程同步反应的是合作关系,一般有严格的执行顺序。进程互斥反应竞争关系

  • PV操作:P操作,若相减结果为负值,则进程被阻,并插入该进程到等待队列。V操作,相加结果大于零,进程继续,否则唤醒等待队列中的一个进程

  • 进程与线程的关系

    1. 线程是进程中的一条执行路径
    2. 单个进程可以创建多个同时存在的线程
    3. 每个线程都有自己私用的堆栈和处理执行环境
    4. 同一进程中的多个线程共享分配给该进程的内存
  • fork()返回-1表示创建失败,返回0为从子进程返回,返回值>0为从父进程返回,返回值为子进程号

  • 进程调度算法:

    1. 先来先服务
    2. 短作业优先
    3. 最短剩余时间优先
    4. 时间片轮转
    5. 优先级调度
  • 中断

    中断是指CPU对系统发生的某个事件做出的一种反应,CPU暂停正在执行的程序,保存现场后自动去执行相应的处理程序,处理完该事件后再返回中断处继续执行原来的程序。中断一般三类,一种是由CPU外部引起的,如I/O中断、时钟中断,一种是来自CPU内部事件或程序执行中引起的中断,例如程序非法操作,地址越界、浮点溢出),最后一种是在程序中使用了系统调用引起的。而中断处理一般分为中断响应和中断处理两个步骤,中断响应由硬件实施,中断处理主要由软件实施。

  • 栈帧

    栈帧表示程序的函数调用记录,而栈帧又是记录在栈上面,很明显栈上保持了N个栈帧的实体,那就可以说栈帧将栈分割成了N个记录块,但是这些记录块大小不是固定的,因为栈帧不仅保存诸如:函数入参、出参、返回地址和上一个栈帧的栈底指针等信息,还保存了函数内部的自动变量(甚至可以是动态分配内存,alloca函数就可以实现,但在某些系统中不行),因此,不是所有的栈帧的大小都相同。下面通过一个简单的实例,来分析栈帧的记录活动

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void func(int m, int n) {
    int a, b;
    a = m;
    b = n;
    }
    main() {
    ...
    func(m, n);
    L: 下一条语句
    . ..
    }

    这里的main函数只是简单调用了一个函数func,那么在main调用func函数前,栈的情况是下面这个样子的:

    此时栈中只有一个main函数的栈帧,从低地址esp(栈顶指针)到高地址ebp(栈帧栈底指针)的这块区域,就是当前main函数的栈帧。当main中调用func时,写成汇编大致是:

    push m
    
    push n; 两个参数压入栈
    
    call func; 调用func,将返回地址(实际上是当前PC值的下一个值)填入栈,并跳转到func。

    当成功跳转到func函数中时,func函数的栈帧就已经形成了,但是形成新的栈帧之前,必须要重新记录当前栈帧的栈底指针ebp,下面的保存和切换ebp的几个动作是由系统自动完成的。

    1. push ebp; 函数调用之所以能够返回,单靠保持返回地址是不够的,这一步压栈动作很重要,因为我们要标记函数调用者栈帧的帧 底,这样才能找出保存了的返回地址,栈顶是不用保存的,因为上一个栈帧的顶部讲会是func的栈帧底部。(两栈帧相邻的)

    2. mov ebp, esp; 上一栈帧的顶部,就是这个栈帧的底部 ;

      暂时先看现在的栈的情况

      接下来就是func里面的临时变量局部变量入栈。

  • 虚拟内存

    虚拟内存的基本思想是:在程序装入时,可以将程序的一部分装入内存,而将其余部分留在外存,就可以启动程序执行。在程序执行过程中,当所访问的信息不在内存时,由操作系统将所需要的部分调入内存,然后继续执行程序。

    理论依据是程序的局部性

  • 页式系统:

    虚页:程序的地址空间被分成大小相等的片,称为虚页。

    实页:内存被分为大小相等的块,称为实页。

    页表:记录虚页号与实页号之间的映射关系

    页式地址变换步骤:

    1. 首先CPU给出逻辑地址

    2. 逻辑地址的高几位对应虚页号,剩余的第几位为页内偏移地址

    3. 去页表缓存中看看是否有虚页号对应的块号(实页号),如果有,执行5;如果没有,执行4。

    4. 去页表中查找虚页号对应的块号(实页号)

    5. 将块号和页内偏移地址组合形成物理地址

      页面淘汰算法:OPT LRU FIFO 时钟

  • 段页式系统:

    分段是程序中自然划分的一组逻辑意义完整的信息集合,段长可变,依据逻辑划分。

    段页式系统是在一个分段内划分页面。

  • 大端模式和小端模式

    大端:是指数据的高字节保存在内存的低地址中,而数据的低字节保存在内存的高地址中

    小端:是指数据的高字节保存在内存的高地址中,而数据的低字节保存在内存的低地址中

  • 编译过程

  • 动态链接与静态链接

    静态链接:静态链接的时候,载入代码就会把程序会用到的动态代码或动态代码的地址确定下来,静态库的链接可以使用静态链接,动态链接库也可以使用这种方法链接导入库。

    动态链接:使用这种方式的程序并不在一开始就完成动态链接,而是直到真正调用动态库代码时,载入程序才计算(被调用的那部分)动态代码的逻辑地址,然后等到某个时候,程序又需要调用另外某块动态代码时,载入程序又去计算这部分代码的逻辑地址,所以,这种方式使程序初始化时间较短,但运行期间的性能比不上静态链接的程序

    简单的说,静态库和应用程序编译在一起,在任何情况下都能运行,而动态库是动态链接,顾名思义就是在应用程序启动的时候才会链接,所以,当用户的系统上没有该动态库时,应用程序就会运行失败。再看它们的特点:

    动态库:

    1.共享:多个应用程序可以使用同一个动态库,启动多个应用程序的时候,只需要将动态库加载到内存一次即可

    2.开发模块好:要求设计者对功能划分的比较好。

    3.采用动态链接的程序比静态链接的初始化速度更快,但是执行期间的性能更差

    静态库:代码的装载速度快,执行速度也比较快,因为编译时它只会把你需要的那部分链接进去,应用程序相对比较大。但是如果多个应用程序使用的话,会被装载多次,浪费内存

  • 进程通信

    1. 消息缓存通信(管道):在内存中开设缓冲区,发送进程将消息送入缓冲区,接收进程接受传递来的缓冲区

      无名管道:半双工,只能在有亲缘关系的进程间使用

      命名管道,半双工,可以在没有亲缘关系的进程间使用

    2. 消息队列:消息的链表

    3. 共享内存

    4. 信号量

    5. 套接字:一般用于不同主机之间进程的通信

  • C++线程通信:信号量,全局变量

计算机网络

  • OSI七层模型

    物理层: 通过媒介传输比特,确定机械及电气规范,传输单位为bit,主要包括的协议为:IEE802.3 CLOCK RJ45

    数据链路层: 将比特组装成帧和点到点的传递,传输单位为帧,主要包括的协议为MAC VLAN PPP

    网络层:负责数据包从源到宿的传递和网际互连,传输单位为包,主要包括的协议为IP ARP ICMP OSPF BGP

    传输层:提供端到端的可靠报文传递和错误恢复,传输单位为报文,主要包括的协议为TCP UDP

    会话层:建立、管理和终止会话,传输单位为SPDU,主要包括的协议为RPC NFS

    表示层: 对数据进行翻译、加密和压缩,传输单位为PPDU,主要包括的协议为JPEG ASII

    应用层: 允许访问OSI环境的手段,传输单位为APDU,主要包括的协议为FTP HTTP DNS

  • 五层模型(自顶向下):

    应用层:HTTP 支持网络应用

    运输层:TCP UDP 进程之间

    网络层:IP 主机之间

    链路层

    物理层:在线路上传输比特流

    应用层的数据是最原始的,之后每向下一层,就会加一个头部,例如在运输层会给HTTP报文增加TCP报文头,在网络层又会被加上IP首部。所以HTTP传送的数据是包含在TCP数据部分的。不要把HTTP和IP搞混了。

  • HTTP请求报文

    由三部分组成:请求行 请求头 请求体

    请求行:

    ①是请求方法,GET和POST是最常见的HTTP方法,除此以外还包括DELETE、HEAD、OPTIONS、PUT、TRACE。

    ②为请求对应的URL地址,它和报文头的Host属性组成完整的请求URL。

    ③是协议名称及版本号。

    请求头:

    Accept告诉服务端,客户端可以接受什么类型的响应

    cookie:前面有介绍cookie的基本原理,客户端的cookie号就是通过http请求头发给服务器的

  • HTTP响应报文

    三部分组成:响应行 响应头 响应体

    响应报文可能会有Set-Cookie 字段,服务端可以设置客户端的Cookie,其原理就是通过这个响应报文头属性实现的。

  • TCP报文头:固定长度20字节+可变长度

    序列号:表示本报文段所发送数据的第一个字节的编号

    确认号:表示接收方期望收到发送方下一个报文段的第一个字节数据的编号

    数据偏移:由于TCP首部包含一个长度可变的选项部分,需要指定这个TCP报文段到底有多长

    ACK:表示前面确认号字段是否有效。只有当ACK=1时,前面的确认号字段才有效。TCP规定,连接建立后,ACK必须为1,带ACK标志的TCP报文段称为确认报文段

    SYN:在建立连接时使用,用来同步序号。当SYN=1,ACK=0时,表示这是一个请求建立连接的报文段;当SYN=1,ACK=1时,表示对方同意建立连接。SYN=1,说明这是一个请求建立连接或同意建立连接的报文。只有在前两次握手中SYN才置为1,带SYN标志的TCP报文段称为同步报文段

    FIN:表示通知对方本端要关闭连接了,标记数据是否发送完毕。

    最下面的长条是一个IP数据报,tcp报文是包含在IP数据报中的,并且是IP数据报的数据部分,tcp报文段只指定端口,具体与哪个机器通信会由IP首部中的ip地址指定。

    IP首部示意图:

    首部的前一部分是固定长度,和TCP报文同样是20字节,是所有IP数据报必须具有的。在首部的固定部分的后面是一些可选字段,其长度是可变的。

  • TCP的三次握手,为什么要三次握手

  • TCP去掉第三次握手会怎么样?

    如果仅两次连接可能出现一种情况:客户端发送完连接报文(第一次握手)后由于网络不好,延时很久后报文到达服务端,服务端接收到报文后向客户端发起连接(第二次握手)。此时客户端会认定此报文为失效报文,但在两次握手情况下服务端会认为已经建立起了连接,服务端会一直等待客户端发送数据,但因为客户端会认为服务端第二次握手的回复是对失效请求的回复,不会去处理。这就造成了服务端一直等待客户端数据的情况,浪费资源。

    另外一个角度:由于网络环境不好,客户端发送的连接请求过了很久才抵达服务端,这个连接请求此时实际上已经失效了。如果只有两次握手,那么服务端回复了这个失效的连接请求后,就会认为连接已经成功建立,并会一直等待客户端发来数据,这就导致服务端资源浪费。宏观一点讲,在网络中存在很多的失效的连接请求,服务端收到的请求中夹杂着失效的和有效的,服务端需要判断收到的请求到底有没有效,方法就是第三次握手,相当于问问客户端,“”这真的是你刚刚发送的有效请求吗?”

  • TCP的四次挥手(实际上就是终止TCP连接的过程)

    图中当server端收到client的断开请求时,可能涉及到传输的数据没有传完,因此server端不会立即同意断开请求,可以继续给client端发送数据。此阶段数据传输是单向的(半双工,半关闭)

    回复的报文段中FIN字段没有置为1

    TIME-WAIT作用:

    1. 当server端同意断开请求连接时,client的网络状态并未立即切换,因为先发的报文并不一定比server同意断开请求先到,需要等待2MSL(报文最长存活时间)时间,确认server端的数据全部接收后,才会改变网络状态。一个MSL大概几十秒。
    2. 为了保证客户端发送的最后一个ACK报文段能够到达服务器。因为这个ACK有可能丢失,从而导致处在LAST-ACK状态的服务器收不到对FIN-ACK的确认报文。服务器会超时重传这个FIN-ACK,接着客户端再重传一次确认,重新启动时间等待计时器。最后客户端和服务器都能正常的关闭。假设客户端不等待2MSL,而是在发送完ACK之后直接释放关闭,一但这个ACK丢失的话,服务器就无法正常的进入关闭连接状态
  • http状态码

    200请求成功 301资源被永久转移到其他URL 404请求的资源未找到 400客户端请求的语法错误,服务器无法理解 401要求用户进行身份认证 403服务器理解客户端请求但是拒绝此请求 505服务器不支持请求的HTTP版本

  • 网络层传输数据的基本单元我们称为数据报,运输层传输数据的基本单元我们称作报文段

  • 为什么tcp为什么要建立连接

    保证数据的可靠传输

  • TCP与UDP的区别:前者建立连接,后者不。前者可靠,后者尽力而为。前者面向字节流,后者面向报文。TCP比UDP传输的数据量更大。UDP比TCP更快。

  • cookie与session:

    cookie以文本形式存储在浏览器,而session存储在服务端。由于cookie存储在本地,可以被随意修改,而session在服务端,不能被轻易修改,所以session更安全。我们向某个网站发送HTTP请求时,对方服务端会开一个session,然后回复的HTTP相应报文中会包含一个经过了加密的cookie字符串,其中包含有用户的一些信息,同时包含sessionID。下次我们再访问这个网站时,我们发出的HTTP请求报文的头部会加上这个cookie字符串,服务端可以从中解析出sessionID等信息,根据sessionID可以从存储在服务端的session中解析出更多的用户信息。

  • DNS

    DNS缓存 -> 本地hosts文件 -> 向DNS服务器请求一个DNS查询(DNS查询一般使用UDP,因为快)

    发送DNS查询报文时,主机首先向本地的DNS服务器发送一个DNS查询报文,之后本地DNS服务器将这个查询报文转发到根DNS服务器,并得到下一级DNS服务器的IP,接着本地DNS服务器再向下一级DNS服务器发送查询请求,就这样一级一级向下查询,主体都是本地DNS服务器,最后查到之后,本地DNS服务器再将IP地址发送给主机

  • 浏览器中输入URL到页面返回的全过程

    大致分为8步

    1.根据域名,进行DNS域名解析;

    2.拿到解析的IP地址,建立TCP连接;

    3.向IP地址,发送HTTP请求;

    4.服务器处理请求;

    5.返回响应结果;

    6.关闭TCP连接;

    7.浏览器解析HTML;

    8.浏览器布局渲染;

  • HTTP1.0与HTTP1.1的区别:HTTP 1.0规定浏览器与服务器只保持短暂的连接,一个TCP连接对应一个HTTP请求,浏览器的每次请求都需要与服务器建立一个TCP连接,服务器完成请求处理后立即断开TCP连接,这会导致性能缺陷。例如一个包含有许多图像的网页文件中并没有包含真正的图像数据内容,而只是指明了这些图像的URL地址,当WEB浏览器访问这个网页文件时,需要多次建立TCP连接,非常耗时。HTTP 1.1支持持久连接,一个TCP连接可以对应多个HTTP请求

  • HTTP1.1与HTTP2.0的区别:

    HTTP1.1:若干个请求排队串行化单线程处理,后面的请求等待前面请求的返回才能获得执行机会,一旦有某请求超时等,后续请求只能被阻塞,毫无办法,也就是人们常说的线头阻塞;

    HTTP2.0:多个请求可同时在一个连接上并行执行。某个请求任务耗时严重,不会影响到其它连接的正常执行;

    多说一句:如果需要请求的页面上有很多图片,在HTTP1.1时代,虽然有piprlining技术,但是不好用所以一般被关闭,通常通过建立多个tcp连接来加速(例如chrome限定对于同一个页面最多开6个TCP),而在HTTP2.0时代,可以在一个TCP连接上同时发送多个HTTP请求

  • HTTPS

    http://www.360doc.com/content/20/0319/11/835902_900290660.shtml

    HTTPS在传输数据时用的是对称加密,只有在验证证书时用的是非对称加密。数据传输过程采用对称加密原因有二:首先是因为非对称加密效率太低,另外非对称加密是单向的,不适用于网络传输场景。

    为什么需要CA认证机构颁发证书?如果没有证书,可能会带来”中间人问题“,过程为,本地请求被中间人服务器劫持,中间人服务器向客户端发送自己未被验证过的证书,客户端会与中间人完成之后的HTTPS流程,此时中间人就已经有了客户端发出的随机数。接着中间人以客户端的请求向正规网站发出请求,理所当然被正常响应。中间人将拿到的数据进行加密,返回给客户端。虽然客户端也拿到了自己想要的数据,但是过程中所有的传输内容都被中间人窃取。

  • TCP拥塞控制(Reno)

    1. 当拥塞窗口小于门限值时,发送方处于慢启动阶段,窗口以指数速度增大
    2. 当拥塞窗口大于门限值时,发送方处于拥塞避免阶段,窗口线性增大
    3. 当收到三个重复的ACK时,门限值设为拥塞窗口的一半,而拥塞窗口设为门限值+3MSS(报文段数据部分的最大长度)
    4. 当超时事件发生时,门限值设为拥塞窗口的一半,而拥塞窗口设为一个MSS
  • TCP重传机制

    快速重传(三个冗余ACK)与超时重传

  • 流量控制:接收方在反馈时,将缓冲区剩余空间大小填充在报文段首部的窗口字段中,通知发送方

  • HTTP报文头有多少个字节

  • TCP可靠性的保证:序号 ACK 超时重传 流量控制 拥塞控制 三握四挥

  • 网络层的几个协议

    • ICMP:ICMP主要用来发送错误报文,在某个位置,IP路由器不能找到一条通往HTTP请求中所指定的主机的路径,该路由器就会向你的主机生成并发送一个ICMP报文以指示这个错误
    • OSPF:使用OSPF时,一台路由器构建了一个关于整个自治系统的完整拓扑图,于是每台路由器在本地执行Dijkstra算法找到通向自治区域内每一个子网的最短路径。OSPF主要用于自治区域内的路由。
    • BGP:主要用于自治区域之间的选路。自治区域内的路由器通过iBGP连接,相邻两个自治区域的网关路由器通过eBGP连接。BGP可以用来通报不同的自治区域之间的某一子网的可达性信息。

数据库

  • 开始一个事务就是写一个sql语句:start transaction,这样一个事务就开始了,之后可以随意添加增删查改的语句,最后commit,事务结束。其实一个事务就是由start transaction和commit(或rollback)包裹的一系列sql语句

  • mysql事务隔离级别

    数据库事务有不同的隔离级别,不同的隔离级别对锁的使用是不同的,锁的应用最终导致不同事务的隔离级别

    读未提交(Read Uncommitted):允许脏读取,但不允许更新丢失。如果一个事务已经开始写数据,则另外一个事务则不允许同时进行写操作,但允许其他事务读此行数据。该隔离级别可以通过“排他写锁”实现,即一个事务在写操作时,其他事务不允许写,只允许读。在读未提交级别下,写事务在写完成后、commit之前就会将锁释放,然后其他读事务就可以马上开始读,但是此时前面的写事务可能会回滚,那么读事务就会读到脏数据。也即,读到了未提交的数据

    读已提交(Read Committed):允许不可重复读取,但不允许脏读取。读取数据的事务允许其他事务继续访问该行数据,但是未提交的写事务将会禁止其他事务访问该行。可以通过“瞬间共享读锁”和“排他写锁”实现。此级别和读未提交大体相同,不同的是,写事务要在提交之后才能释放锁,这就解决了读未提交级别中的读脏问题。读到的都是提交过的数据,也即读已提交。这个级别会出现不可重复读的问题,我们先开一个读事务,并进行一次读取,此时读事务还为提交,又开了一个写事务,对数据进行修改,由于此时写事务还未提交,也即还为释放锁,此时如果读事务再次读取数据,和前一次读到的内容是一样的。这个时候写事务提交,读事务再次读取,发现数据不同了,然后读事务提交。从上述过程可以发现,读事务的第三次读取到的数据与前两次不同,这就是出现了不可重复读问题。

    可重复读取(Repeatable Read)

    禁止不可重复读取和脏读取,但是有时可能出现幻读数据。所谓幻读,就是当某个事务读取某个范围内的记录时,另外一个事务又在该范围内插入了新的记录,之前的事务再次读取该范围的记录时,会产生幻行。读取数据的事务将会禁止写事务(但允许读事务),写事务则禁止任何其他事务。可以通过“共享读锁”和“排他写锁”实现。

    序列化(Serializable)

    提供严格的事务隔离。它要求事务串行执行,事务只能一个接着一个地执行,不能并发执行。仅仅通过“行级锁”是无法实现事务序列化的,必须通过其他机制保证新插入的数据不会被刚执行查询操作的事务访问到。

  • MVCC(多版本并行控制):MVCC只在读已提交和可重复读取两个级别下使用。上一点的读已提交中有一行加粗,为什么此时写事务已经对数据上锁了,读事务仍然可以读取数据呢,这就是因为MVCC中有一个版本链,存储着过去的数据,写事务正在执行时,读事务可以从版本链中读到数据。可重复读取级别下的MVCC对版本链的管理策略会有些不同,保证了不会发生不可重复读

  • 事务:是指作为单个逻辑工作单元执行的一系列操作,要么完全地执行,要么完全地不执行。事务具有4个基本特征,分别是:原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)、持久性(Duration),简称ACID。

    1)原子性(Atomicity)

    原子性是指事务包含的所有操作要么全部成功,要么全部失败回滚,因此事务的操作如果成功就必须要完全应用到数据库,如果操作失败则不能对数据库有任何影响。

    2)一致性(Consistency)

    一致性是指事务必须使数据库从一个一致性状态变换到另一个一致性状态,也就是说一个事务执行之前和执行之后都必须处于一致性状态。

    拿转账来说,假设用户A和用户B两者的钱加起来一共是5000,那么不管A和B之间如何转账,转几次账,事务结束后两个用户的钱相加起来应该还得是5000,这就是事务的一致性。

    3)隔离性(Isolation)

    隔离性是当多个用户并发访问数据库时,比如操作同一张表时,数据库为每一个用户开启的事务,不能被其他事务的操作所干扰,多个并发事务之间要相互隔离。

    4)持久性(Durability)

    持久性是指一个事务一旦被提交了,那么对数据库中的数据的改变就是永久性的,即便是在数据库系统遇到故障的情况下也不会丢失提交事务的操作。

  • 对ACID的理解:原子性的实现基于日志的REDO/UNDO机制。隔离性的实现主要就是乐观锁与悲观锁。对于一致性,在ACID中,一致性是最基本的属性,可以认为其他三个属性都是为了保证一致性而存在的。原子性并不能保证一致性,比如两个进程都向某个账户转100元,第一个进程将金额修改为100,第二个进程也将金额修改为100,最后结果是100,显然是不对的,所以就需要引入隔离性。

  • 悲观锁

    总是假设最坏的情况,每次去拿数据的时候都认为别人会修改,所以每次在拿数据的时候都会上锁,这样别人想拿这个数据就会阻塞直到它拿到锁(共享资源每次只给一个线程使用,其它线程阻塞,用完后再把资源转让给其它线程)。传统的关系型数据库里边就用到了很多这种锁机制,比如行锁,表锁等,读锁,写锁等,都是在做操作之前先上锁。Java中synchronizedReentrantLock等独占锁就是悲观锁思想的实现。

    乐观锁

    总是假设最好的情况,每次去拿数据的时候都认为别人不会修改,所以不会上锁,但是在更新的时候会判断一下在此期间别人有没有去更新这个数据,可以使用版本号机制CAS算法实现。乐观锁适用于多读的应用类型(写比较少),这样可以提高吞吐量,像数据库提供的类似于write_condition机制,其实都是提供的乐观锁。在Java中java.util.concurrent.atomic包下面的原子变量类就是使用了乐观锁的一种实现方式CAS实现的。

    版本号机制:一般是在数据表中加上一个数据版本号version字段,表示数据被修改的次数,当数据被修改时,version值会加一。当线程A要更新数据值时,在读取数据的同时也会读取version值,在提交更新时,若刚才读取到的version值为当前数据库中的version值相等时才更新,否则重试更新操作,直到更新成功。

    举一个简单的例子:
    假设数据库中帐户信息表中有一个 version 字段,当前值为 1 ;而当前帐户余额字段( balance )为 $100 。

    1. 操作员 A 此时将其读出( version=1 ),并从其帐户余额中扣除 $50( $100-$50 )。
    2. 在操作员 A 操作的过程中,操作员B 也读入此用户信息( version=1 ),并从其帐户余额中扣除 $20 ( $100-$20 )。
    3. 操作员 A 完成了修改工作,将数据版本号加一( version=2 ),连同帐户扣除后余额( balance=$50 ),提交至数据库更新,此时由于提交数据版本大于数据库记录当前版本,数据被更新,数据库记录 version 更新为 2 。
    4. 操作员 B 完成了操作,也将版本号加一( version=2 )试图向数据库提交数据( balance=$80 ),但此时比对数据库记录版本时发现,操作员 B 提交的数据版本号为 2 ,数据库记录当前版本也为 2 ,不满足 “ 提交版本必须大于记录当前版本才能执行更新 “ 的乐观锁策略,因此,操作员 B 的提交被驳回

    CAS算法

    compare and swap(比较与交换),是一种有名的无锁算法。无锁编程,即不使用锁的情况下实现多线程之间的变量同步,也就是在没有线程被阻塞的情况下实现变量的同步,所以也叫非阻塞同步(Non-blocking Synchronization)。CAS算法涉及到三个操作数

    • 需要读写的内存值 V

    • 进行比较的值 A

    • 拟写入的新值 B

      当且仅当 V 的值等于 A时,CAS通过原子方式用新值B来更新V的值,否则不会执行任何操作(比较和替换是一个原子操作)。一般情况下是一个自旋操作,即不断的重试

  • 并发操作可能带来的数据不一致性:

    1. 丢失更新:两个以上事务从DB中读入同一数据并修改, 其中一事务(后提交的事务)的提交结果破坏 了另一事务(先提交的事务)的提交结果,导 致先前提交事务对DB的修改被丢失
    2. 读脏:事务1修改某一数据,并将其写回磁盘。事务2读取同一数据后,事务1由于某种原因被撤消. 这时事务1已修改过的数据被恢复原值。事务2读到的不稳定的瞬间数据就与数据库中的数 据不一致,是不正确的数据,又称为“脏”数据
    3. 不接重复读:事务1读取数据后,事务2执行更新操作,使事务1无 法再现前一次读取结果
  • 封锁:X锁(写锁)和S锁(读锁)

  • 三级封锁协议:事务T在修改数据R之前必须先对其加X锁,直 到事务结束才释放;事务T在读取数据R前必须先加S 锁,直到事务结束才释放

  • 三级封锁协议太严格,就又有了两段锁协议的内容

    1. 在对任何数据进行读、写操作之前,事务首先要 获得对该数据的封锁;

    2. 在释放一个封锁之后,事务不再获得任何其他封 锁。

  • 数据库索引,哪些地方需要索引,是否越多越好

    索引是一种数据结构,存储的是表上某一列的值以及这个值所在的那一行的地址。使用索引的全部意义就是通过缩小一张表中需要查询的记录/行的数目来加快搜索的速度。索引并非越多越好,无用的索引反而会拉低性能。

    1
    2
    CREATE INDEX name_index
    ON Employee (Employee_Name)
  • mysql的索引主要是B+树索引。为什么不用B树呢?B树的两个主要特点,一个是树内存储数据,另一个是叶节点之间没有指针相连;而B+树的两个主要特点,一个是数据全都存储在叶子节点,另外叶子节点全都用链表连在一起。数据库索引采用B+ tree的主要原因是B Tree在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题,B+ tree应运而生。B+ tree只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,如果使用B Tree,则需要做局部的中序遍历,可能要跨层访问,效率太慢。

  • 常见的MySQL主要有两种结构:Hash索引和B+ Tree索引,我们使用的是InnoDB引擎,默认的是B+树。B+ Tree索引和Hash索引区别 哈希索引适合等值查询,但是不无法进行范围查询 哈希索引没办法利用索引完成排序,如果有大量重复键值得情况下,哈希索引的效率会很低,因为存在哈希碰撞问题。而B+ Tree是一种多路平衡查询树,所以他的节点是天然有序的(左子节点小于父节点、父节点小于右子节点),所以对于范围查询的时候不需要做全表扫描。

  • 聚簇索引和非聚簇索引:聚簇索引就是按照每张表的主键构造一颗B+树(即使没有创建主键,系统也会隐式创建一个主键),同时叶子节点中存放的就是整张表的行记录数据,这个特性决定了索引组织表中数据也是索引的一部分,每张表只能拥有一个聚簇索引。聚簇索引的查询速度更快,因为索引树的叶子节点直接就是我们要查询的整行数据了。而非聚簇索引的叶子节点是主键的值,还需要根据主键值回表查询。

  • 聚簇索引并不是一种单独的索引类型,而是一种数据存储方式。在InnoDB中,聚簇索引和非聚簇索引都是通过B+树来实现的,B+树索引按照存储方式的不同分为聚簇索引和非聚簇索引。

    ①聚集索引(聚簇索引):以 InnoDB 作为存储引擎的表,表中的数据都会有一个主键,即使你不创建主键,系统也会帮你创建一个隐式的主键。

    这是因为 InnoDB 是把数据存放在 B+ 树中的,而 B+ 树的键值就是主键,在 B+ 树的叶子节点中,存储了表中所有的数据。

    这种以主键作为 B+ 树索引的键值而构建的 B+ 树索引,我们称之为聚集索引。(换句话说,此时B+树的中间节点中存储是索引值都是主键的列值)

    ②非聚集索引(非聚簇索引):以主键以外的列值作为键值构建的 B+ 树索引,我们称之为非聚集索引换句话说,此时B+树的中间节点中存储是索引值不是主键的列值

    非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据,而是存储该列对应的主键,想要查找数据我们还需要根据主键再去聚集索引中进行查找,这个再根据聚集索引查找数据的过程,我们称为回表换句话说,聚簇索引的B+树的叶子节点存储的是数据,而非聚簇索引的B+树的叶子节点存储的是数据所在行的主键的值。即非聚集索引查找数据分为两步,首先根据非聚簇索引找到数据所在行的主键,然后根据这个主键去聚簇索引中找到我们要的数据。

    假设现在有个表,包含两个列:id和lucknum。主键是id。以下面这句sql为例

    1
    select * from user where id>=18 and id <40

    现在id是主键,此时就可以直接去聚簇索引中查找数据。再看下面这行sql

    1
    select * from user where luckNum=33

    由于luckNum不是主键,所以需要先在非聚簇索引中找到luckNum为33的那一行的主键值,然后再根据这个主键值取聚簇索引中找到luckNum = 33的整行数据。

  • 索引在mysql中也叫做键

C++

  • 面向对象三大特点:封装 继承 多态

    封装即将客观事物封装成抽象的类,并且把私密数据进行隐藏,并提供一些公有接口

  • 重载与重写

    重载是指函数名字相同,参数列表不同。重写是指对父类的虚函数进行重新定义,函数名和参数列表都必须相同。所以说多态是通过重写来实现的。

  • 多态:发生多态的条件是,父类指针或引用指向子类对象,虚函数重写

  • 静态联编与动态联编:将源代码中的函数调用解释为执行特定的函数代码块称为函数名联编。在编译过程中进行联编称为静态联编,在程序运行时进行联编称为动态联编。如果使用虚函数则为动态联编。同样是基类指针或者引用指向子类对象,如果调用的函数没有声明为虚函数,则是静态联编。

  • 虚函数

    经常在基类中将派生类会重新定义的方法声明为虚方法。

    如果方法是通过引用或者指针调用的按下面的规则确定使用的是哪一个方法:如果方法没有使用关键字virtual,程序将根据引用类型或者指针类型来选择方法,如果使用了virtual,程序将根据指针或者引用指向的对象的类型来选择方法。

  • 虚函数的工作原理:给每个对象增加一个隐藏成员,隐藏成员中保存了一个指向虚函数表的指针,虚函数表是一个数组,数组中记录的是这个对象的虚函数们的地址。无论类中有多少个虚函数,其对象中都只有一个这个隐藏成员,区别只是这个成员指向的表的大小不同。调用虚函数时,程序将查看存储在对象中的虚函数表地址,然后得到相应虚函数的地址。类声明中定义的第n个虚函数,将位于虚函数表(数组)的第n个元素。

  • 虚析构函数:析构函数应该是虚函数,除非类不用作基类。虚析构函数是为了解决父类指针指向子类对象时,释放子类对象的资源时,释放不完全,造成的内存泄漏问题。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Father{
    public:
    Father(){}
    virtual ~Father(){
    std::cout << "~father" << std::endl;
    }
    }

    class Son{
    public:
    Son(){}
    virtual ~Son(){
    std::cout << "~Son" << std::endl;
    }
    }

    int main(){
    Father *demo = new Son();
    delete demo;
    }

    如果加上virtual,则delete demo的时候会先调用~Son()再调用~Father()。如果没有virtual,由于demo是Father指针,所以只调用~Father()。

  • new与malloc的区别

    1. 申请的内存所在的位置

      new操作符从自由存储区(free store)上为对象动态分配内存空间,而malloc函数从上动态分配内存。自由存储区是C++基于new操作符的一个抽象概念,凡是通过new操作符进行内存申请,该内存即为自由存储区。而堆是操作系统中的术语,是操作系统所维护的一块特殊内存,用于程序的内存动态分配,C语言使用malloc从堆上分配内存,使用free释放已分配的对应内存。

    2. 返回类型安全性

      new操作符内存分配成功时,返回的是对象类型的指针,类型严格与对象匹配,无须进行类型转换,故new是符合类型安全性的操作符。而malloc内存分配成功则是返回void * ,需要通过强制类型转换将void*指针转换成我们需要的类型。

    3. 使用new操作符申请内存分配时无须指定内存块的大小,编译器会根据类型信息自行计算,而malloc则需要显式地指出所需内存的尺寸。

    4. new/delete会调用对象的构造函数/析构函数以完成对象的构造/析构。而malloc则不会

    5. 对数组的处理

      C++提供了new[]与delete[]来专门处理数组类型,对数组的支持体现在它会分别调用构造函数函数初始化每一个数组元素,释放对象时为每个对象调用析构函数。至于malloc,它并不知道你在这块内存上要放的数组还是啥别的东西,反正它就给你一块原始的内存,在给你个内存的地址就完事。

    6. operator new /operator delete的实现可以基于malloc,而malloc的实现不可以去调用new。

  • const与mutable

    先来回顾下const的基础知识,const int * a是指针不能改变指向的那个内存位置的值,int * const a是指针不能指向其他位置。记忆方法就是,const离谁近(int & *)谁就不能变。

    const还可以用来修饰成员函数。类的成员函数后面加 const,表明这个函数不会对这个类对象的数据成员(准确地说是非静态数据成员)作任何改变。声明和定义时,都要在参数的圆括号后面加上const。与之对应的是mutable,被mutable修饰的成员变量,即使在const成员函数中,其值依然可以被改变。

  • C++内存模型

    C++内存分为5个区域:

    • 堆 heap :
      由new分配的内存块,其释放编译器不去管,由我们程序自己控制(一个new对应一个delete)。如果程序员没有释放掉,在程序结束时OS会自动回收。涉及的问题:“缓冲区溢出”、“内存泄露”
    • 栈 stack :
      是那些编译器在需要时分配,在不需要时自动清除的存储区。存放局部变量、函数参数。
      存放在栈中的数据只在当前函数及下一层函数中有效,一旦函数返回了,这些数据也就自动释放了。
    • 全局/静态存储区 (.bss段和.data段) :
      全局和静态变量被分配到同一块内存中。
    • 常量存储区 (.rodata段) :
      存放常量,不允许修改(通过非正当手段也可以修改)
    • 代码区 (.text段) :
      存放代码(如函数),不允许修改(类似常量存储区),但可以执行(不同于常量存储区)
  • C++11智能指针介绍

    使用头文件

    智能指针主要用于管理在堆上分配的内存,它将普通的指针封装为一个对象。当对象的生存周期结束后,会在析构函数中释放掉申请的内存,从而防止内存泄漏。

    • 为什么要使用智能指针

      智能指针的作用是管理一个指针,因为存在以下这种情况:申请的空间在函数结束时忘记释放,造成内存泄漏。使用智能指针可以很大程度上的避免这个问题,因为智能指针就是一个类,当超出了类的作用域是,类会自动调用析构函数,析构函数会自动释放资源。所以智能指针的作用原理就是在函数结束时自动释放内存空间,不需要手动释放内存空间。

    • unique_ptr

      (替换auto_ptr)unique_ptr实现独占式拥有或严格拥有概念,保证同一时间内只有一个智能指针可以指向该对象。它对于避免资源泄露(例如“以new创建对象后因为发生异常而忘记调用delete”)特别有用。

    • shared_ptr

      shared_ptr实现共享式拥有概念。多个智能指针可以指向相同对象,该对象和其相关资源会在“最后一个引用被销毁”时候释放。从名字share就可以看出了资源可以被多个指针共享,它使用计数机制来表明资源被几个指针共享。可以通过成员函数use_count()来查看资源的所有者个数。shared_ptr 是为了解决 auto_ptr 在对象所有权上的局限性(auto_ptr 是独占的), 在使用引用计数的机制上提供了可以共享所有权的智能指针。

    • 如何选择智能指针:如果需要多个指针指向同一个对象,就是用shared_ptr,否则使用unique_ptr

    • 使用方法

      1
      unique_ptr<Report> ps (new Report("using unique ptr"));

      Report是一个类,之后使用ps的方法和普通的指针一样。

    • 使用make_shared函数可以返回指定类型的shared_ptr

      1
      2
      3
      std::shared_ptr<int> foo = std::make_shared<int> (10);
      // same as:
      std::shared_ptr<int> foo2 (new int(10));
  • 多态原理

  • STL

    • 优先队列

      定义优先队列 priority_queue<int, vector, greater > q;第一个为元素的类型,第二个为所使用的容器(vector或deque),第三个为一个比较的规则,决定是最大优先队列还是最小优先队列,默认的less为最大优先队列。第三个参数如果省略,默认为大顶堆,即降序排列,加上之后变成小顶堆。方法与栈差不多,有top()ppop()push()等等。

    • vector与list

      vector

       向量 相当于一个数组
       在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时,首先分配一个非常大的内存空间预备进行存储,即capacituy()函数返回的大小, 当超过此分配的空间时再整体重新放分配一块内存存储,这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。
      优点:(1) 不指定一块内存大小的数组的连续存储,即可以像数组一样操作,但可以对此数组
                  进行动态操作。通常体现在push_back() pop_back()
                  (2) 随机访问方便,即支持[ ]操作符和vector.at()
                  (3) 节省空间。
      缺点:(1) 在内部进行插入删除操作效率低。
                  (2) 只能在vector的最后进行push和pop,不能在vector的头进行 push和pop。 
                   (3)  当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释
                        放 

      list

       双向链表
       每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
      优点: (1) 不使用连续内存完成动态操作。
                   (2) 在内部方便的进行插入和删除操作
                  (3) 可在两端进行push、pop
      缺点:(1)  不能进行内部的随机访问,即不支持[ ]操作符和vector.at() 
                  (2) 相对于verctor占用内存多 
  • 拷贝构造函数与赋值运算符重载

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    #include<iostream>
    #include<string>
    using namespace std;

    class MyStr
    {
    private:
    char *name;
    int id;
    public:
    MyStr():id(0),name(NULL) {}
    MyStr(int _id, char *_name) //constructor
    {
    cout << "constructor" << endl;
    id = _id;
    name = new char[strlen(_name) + 1];
    strcpy_s(name, strlen(_name) + 1, _name);
    }
    MyStr(const MyStr& str)
    {
    cout << "copy constructor" << endl;
    id = str.id;
    name = new char[strlen(str.name) + 1];
    strcpy_s(name, strlen(str.name) + 1, str.name);
    }
    MyStr& operator =(const MyStr& str)//赋值运算符
    {
    cout << "operator =" << endl;
    if (this != &str)
    {
    if (name != NULL)
    delete[] name;
    this->id = str.id;
    int len = strlen(str.name);
    name = new char[len + 1];
    strcpy_s(name, strlen(str.name) + 1, str.name);
    }
    return *this;
    }
    ~MyStr()
    {
    delete[] name;
    }
    };

    int main()
    {
    MyStr str1(1, "hhxx");
    cout << "====================" << endl;
    MyStr str2;
    str2 = str1;
    cout << "====================" << endl;
    MyStr str3 = str2;
    return 0;
    }

Java

  • hashmap和hashtable的区别

  • String StringBuilder StringBuffer区别,线程安全问题

    String是字符串常量,每次更改都是创建一个新的然后把旧的回收,所以最慢。另外两个都是字符串变量。buffe和Stringr线程安全,Builder线程不安全

  • 反射

    反射之中包含了一个「反」字,所以想要解释反射就必须先从「正」开始解释。

    一般情况下,我们使用某个类时必定知道它是什么类,是用来做什么的。于是我们直接对这个类进行实例化,之后使用这个类对象进行操作。

    1
    2
    Apple apple = new Apple(); //直接初始化,「正射」
    apple.setPrice(4);

    上面这样子进行类对象的初始化,我们可以理解为「正」。

    而反射则是一开始并不知道我要初始化的类对象是什么,自然也无法使用 new 关键字来创建对象了

    这时候,我们使用 JDK 提供的反射 API 进行反射调用:

    1
    2
    3
    4
    5
    Class clz = Class.forName("com.chenshuyi.reflect.Apple");
    Method method = clz.getMethod("setPrice", int.class);
    Constructor constructor = clz.getConstructor();
    Object object = constructor.newInstance();
    method.invoke(object, 4);

    上面两段代码的执行结果,其实是完全一样的。但是其思路完全不一样,第一段代码在未运行时就已经确定了要运行的类(Apple),而第二段代码则是在运行时通过字符串值才得知要运行的类(com.chenshuyi.reflect.Apple)。

    所以说什么是反射?

    反射就是在运行时才知道要操作的类是什么,并且可以在运行时获取类的完整构造,并调用对应的方法。

    完整示例代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    public class Apple {

    private int price;

    public int getPrice() {
    return price;
    }

    public void setPrice(int price) {
    this.price = price;
    }

    public static void main(String[] args) throws Exception{
    //正常的调用
    Apple apple = new Apple();
    apple.setPrice(5);
    System.out.println("Apple Price:" + apple.getPrice());
    //使用反射调用
    Class clz = Class.forName("com.chenshuyi.api.Apple");
    Method setPriceMethod = clz.getMethod("setPrice", int.class);
    Constructor appleConstructor = clz.getConstructor();
    Object appleObj = appleConstructor.newInstance();
    setPriceMethod.invoke(appleObj, 14);
    Method getPriceMethod = clz.getMethod("getPrice");
    System.out.println("Apple Price:" + getPriceMethod.invoke(appleObj));
    }
    }
  • bean

  • Sprinng MVC :在SpringMVC的应用中,当一个请求到达服务器时,首先会被DispatchServlet获取,当然在此之前会被一些安全控制相关的拦截器处理,到了DispatchServlet之后,DispatchServlet会根据HandlerMapping的机制(比如常用的@RequestMapping),将请求分配给处理该请求的ControllerController会调用一个或多个Service完成具体的业务逻辑处理,而Service则会调用一个或多个Repository(即我们常说的Dao层)与数据库交互。然后Controller完成业务逻辑处理之后,将数据返回客户端,或者调用视图解析器将视图返回客户端。

  • hashMap

    与 JDK 1.7 相比,1.8 在底层结构方面做了一些改变,当每个桶中元素大于 8 的时候,会转变为红黑树,目的就是优化查询效率

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    public V put(K key, V value) {
    // HashMap允许存放null键和null值。
    // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。
    if (key == null)
    return putForNullKey(value);
    // 根据key的keyCode重新计算hash值。
    int hash = hash(key.hashCode());
    // 搜索指定hash值在对应table中的索引。
    int i = indexFor(hash, table.length);
    // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    // 如果发现已有该键值,则存储新的值,并返回原始值
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
    }
    }
    // 如果i索引处的Entry为null,表明此处还没有Entry。
    modCount++;
    // 将key、value添加到i索引处。
    addEntry(hash, key, value, i);
    return null;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public V get(Object key) {
    if (key == null)
    return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
    e != null;
    e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    return e.value;
    }
    return null;
    }

双缓存算法

对于clean容器n,当他失效时,理想状态是,同一条带中比n小的容器都在cache中,我们只需要从磁盘读取比n大的那些容器。实际情况下,同一条带中比n小的容器可能会被挤出去,那么恢复n时就要重新读取比n小的那些容器。另外,当恢复n时,那些比n大的容器被存入缓存,这些比n大的容器在将来一定会被命中,但是可能在命中到来之前就被挤出去了,之后就需要再次从磁盘读。
为了避免上面的两种情况,增加clean cache,用来保护clean容器。dirty cache满了的时候,不能将clean cache中的容器替换出去。
对opt算法也进行了改进。假如接下来需要恢复容器n,将缓存中的容器按照下面的优先级排序:
1. (优先级最高)恢复n所需的容器
2. 在window中出现的容器(即不久将来会被用到),出现的越早优先级越高
3. 没有在window中出现的容器,但是在window中有和该容器在同一条带的容器(关联容器),在window中关联容器出现的越早,优先级越高
4. (优先级最低)在window中没有出现过,且window中也没有关联容器
排序后,首先考虑将优先级最低的容器替换掉

web服务器

  1. 功能

a) 可配置监听地址、监听端口和主目录 b) 能够在监听端口上进行监听
c) 支持服务的启动
d) 支持服务的关闭

e) 能够响应客户端的请求,并定位相应的 html 文件
f) 能够构造并发送可被客户端解析的响应报文
g) 以多线程或异步方式响应每个客户端请求,支持多个客户端的并发请求
h) 在服务器端的屏幕上输出每个请求的来源(IP 地址、端口号和 HTTP 请求命令行) i) 支持一定的异常处理能力
j) 支持多种类型文件的输出
k) 对于无法成功定位文件的请求,能够根据错 误原因,作相应错误提示
l) 在服务器端的屏幕上能够输出对每一个请求 处理的结果
m) 具备图形 GUI 界面

  1. 流程

    winsock初始化 -> 创建服务器套接字 -> 配置端口号 -> 配置本地资源路径 -> 解析用户输入的ip地址 -> 将服务器套接字与端口号绑定 -> 开始监听listen -> 每出现一个请求,就开一个新的线程,使用accept函数建立连接

rdt协议

GBN演示图

SR协议发送方有一个窗口,只要这个窗口中存在还没有发送过的分组,就发送,并且每个分组设置一个计时器。如果某个分组超时了,就重传。如果收到了ack,就对相应的分组进行标记,如果收到的ack是base序号,就把base序号推进到下一个还没有被ack的序号。接收方如果按序收到了分组,就提交,如果失序,就缓存。收到的如果是n,就ack n。

a-b剪枝算法

整个α-β剪枝的核心思想就是,当你知道你有一个选择A时,此时你知道了B选择不如A选择好,那么你就不需要知道B选择有多坏。

a-b 剪枝算法是一种基于剪枝的深度优先搜索算法,是对 Minmax 算法的优 化,同时 a-b 剪枝算法也是根据极大-极小规则进行的,基本思想是:根据倒推值 的计算方法,或中取大,与中取小,在扩展和计算过程中,剪掉不必要的分枝, 从而提高效率。

对于MIN层我们取所有情况的最小值和上一层的a比较,如果最小值小于a就意味着不会使得a更大,就剪掉

α值:有或后继的节点,取当前子节点中的最大倒推值为其下界,称为α值。节点倒推值>=α;

β值:有与后继的节点,取当前子节点中的最小倒推值为其上界,称为β值。节点倒推值<=β

a 剪枝是指,在对博弈树采取深度优先的搜索策略时,从左路分枝的叶节点 倒推得到某一层的 MAX 节点的值,可表示到目前为止得以落实的最大效用 值,记为 a。这个值可以作为 MAX 方效用值的下界。然后再搜索该 MAX 节 点的其他子节点,如果发现子节点的上界比自己的下界还要小,那么就直接 放弃还没有搜索的分枝,即进行剪枝。
b 剪枝是指,在对博弈树采取深度优先的搜索策略时,从左路分枝的叶节点 倒推得到某一层的 MIN 节点的值,可表示到目前为止得以落实的最小效用 值,记为 b。这个值可以作为 MIN 方效用值的上界。然后再搜索该 MIN 节 点的其他子节点,如果发现子节点的下界比自己的上界还要大,那么就直接 放弃还没有搜索的分枝,即进行剪枝。

系统调用

我们都知道,很多我们习以为常的C语言标准函数,在linux平台的实现都是通过系统调用完成的,例如我们在用户程序中使用open()或者write()函数时,函数执行过程中会通过中断进入到系统内核中检查系统调用号,这个号码代表进程请求哪种服务。然后,它查看系统调用表(sys_call_table)找到所调用的内核函数入口地址。接着,就调用内核函数来实现open()或者write()等函数的功能。我们要做的,就是在内核中增加一个内核函数,相应地也在系统调用表中增加一个表项,使得我们增加的功能永远的留存在系统中

然后找到/usr/src/linux-4.18.3/arch/x86/entry/syscalls/syscall_64.tbl,在编号为334的一行后面新加一行,编号为335,第二列为common,第三列为新增系统调用的名字,我命名为mycall,第四列为__x64_sys_mycall。

之后找到/usr/src/linux-4.18.3/include/linux/syscalls.h,从文件名字就能看出来,这里面的都是函数的声明,我们在文件的最后,#endif之前,添加我们自定义的函数的声明.

之后,找到/usr/src/linux-4.18.3/kernel/sys.c,我们将新增加的函数的定义添加在文件的末尾,#endif之前

首先需要注意的是,在内核中,我们只能使用内核函数,比如open()、write()函数都不能用了,需要用ksys_open()和ksys_write()

make编译内核,make modules_install安装模块,make install安装内核

编译器

抽象语法树采用孩子兄弟表示法来表示,每个节点为一个ASTTree结构体,结构体中有ScopeItem指针,用于指向符号表节点。每一个ScopeItem结构体中记录符号的详细信息,并且还有一个ScopeItem*的指针用于记录数组的内情向量。数组长度用vector记录,维度用dim记录。

朴素贝叶斯声音性别识别

  • 简化的贝叶斯公式为

  • 朴素贝叶斯基于的假设为

  • 概率的计算方法为

设备驱动

  • linux把所有的设备都当做文件来处理。我们的linux操作系统跟外部设备(如磁盘、光盘等)的通信都是通过设备文件进行的,linux为不同种类的设备文件提供了相同的接口,比如read(),write(),open(),close()。所以在系统与设备通信之前,系统首先要建立一个设备文件
  • 编写驱动程序 my_device.c,我们需要为驱动编写 my_open、my_release、 my_read、my_write 函数
  • 编写my_open函数时:从设备使用的角度出发,当需要打开、开始使用某个设备时,使用 try_module_get 去增加管理此设备的 owner 模块的使用计数,这样,在设备在使 用时,管理此设备的模块就不能被卸载
  • 编写try_release函数时:执行module_put函数
  • 编写my_read函数时:使用copy_to_user函数。Copy_to_user 函数的作用是将内核区的内容复制到用户空间,他的参数分别 为指向内核区的指针、指向用户缓冲区的指针和读取内容的长度,执行此操作后, 相应的内容就从内核区复制到用户空间,也就相当于完成了读操作。
  • 编写my_write函数。Copy_from_user 函数的作用是将用户空间的内容复制到内核,他的参数分别 为指向用户缓冲区的指针、指向内核区的指针和读取内容的长度,执行此操作后, 相应的内容就从用户复制到内核,也就相当于完成了写操作。
  • 注册设备时要用到 register_chrdev 这个函数,函数的第一个参数为为新设备 分配的主设备号,我们这里设置为 0,意味着允许系统自动为设备设置主设备号; 函数的第二个参数是设备名,第三个参数是 file_operations 结构体的指针,这个 结构体中有 my_open、my_release、my_read、my_write 这四个函数,意味着新的 设备具有这四个功能。
  • 执行make,执行insmod my_drive.ko指令,用于安装模块。进入/proc/device查看主设备号。之后使用mknod命令创建设备文件。

实习

目标:对锋刃的消费延迟,设置监控来发现,然后触发对应处理操作,尽可能实现自动化处理,不能自动化的,触达 到对应的负责人,以达到早发现,早处理。

锋刃作业并行度计算方式:

  1. 锋刃作业上游每秒的流量 / 锋刃作业的处理能力qps(留有40%buffer) = 最少需要的并行度;
  2. 最佳并行度 = 大于等于最少需要的并行度 AND 能被锋刃上游CDMQ的分区数整除的最小值 AND 小于等于锋刃上游CDMQ的分区数

翻转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>

using namespace std;

struct ListNode {
int val;
struct ListNode * next;
};

struct ListNode *reverseList(struct ListNode* head) {
if (head == nullptr) {
return nullptr;
}
struct ListNode *p0 = nullptr;
struct ListNode *p1 = head;
struct ListNode *p2 = head->next;
while (p1 != nullptr) {
p1->next = p0;

p0 = p1;
p1 = p2;
if (p2 != nullptr) {
p2 = p2->next;
}
}
return p0;
}

int main(){
int num[5] = {1, 2, 3, 4, 5};
ListNode *node = new ListNode, *head = node;
node->val = 1;
node->next = nullptr;
for(int i = 1; i < 5; i++) {
node->next = new ListNode;
node = node->next;
node->val = num[i];
node->next = nullptr;
}
cout << "原本的链表为" << endl;
node = head;
while(node) {
cout << node->val << " ";
node = node->next;
}
cout << endl << "翻转后的链表为" << endl;
node = reverseList(head);
while(node) {
cout << node->val << " ";
node = node->next;
}

}

赋值运算符重载与拷贝构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class String {
private:
char * str;
public:
String ():str(new char[1]) { str[0] = 0;}
const char * c_str() { return str; };
String & operator = (const char * s);
String::~String( ) { delete [] str; }
String( String & s){
str = new char[strlen(s.str)+1];
strcpy(str,s.str);
}
};
String & String::operator = (const char * s) {
//重载“=”以使得 obj = “hello”能够成立
if( this == & s)
return * this;
delete [] str;
str = new char[strlen(s)+1];
strcpy( str, s);
return * this;
}