面经 - Python | 计网 | 数据库 | 数据结构_计网remove

语言类

python
2022春招，Python面试必知必会，245道面试真题

高级语言和低级语言

python就是高级语言，C语言是低级语言
高级语言：执行效率低，实现效率高，目标代码大，可维护性好，代码移植型好。可坑不需要关注与底层的具体实现，很多功能都已经封装好了，只需要专注于业务逻辑地实现
低级语言：执行效率高，实现效率低，目标代码小，可维护性差，代码移植型差

基础

三大框架

1. Django
   功能非常全，主要快速开发。如果需要高并发，要进行二次封装，虽然使用方便，但是效率比较低。如果要求高，需要比如重写socket，底层用c重写之类的，ORM也比较慢
2. Flask
   轻量级，主要用于接口的编写，就相当于是一个内核，其他功能都需要使用扩展模块实现，前后端分离，效率高。
   可以使用扩展添加ORM、身份校验、文件上传等功能。
   采用Werkzurg WSGI进行路由，jinja2管理模板，默认没有配置数据库，可以选择mysql或者nosql，效率比django高，是最灵活的框架。
3. Tornado
   是非阻塞式的服务器，速度相当快。源于其非阻塞式的方式和epoll的运用。每秒可以处理数以千计的链接请求，是实时web最理想的框架

单例模式

无论如何实例化，都只有一个对象存在

class A(object):
    __instance=None
    __x=1
    def __new__(cls,*args,**kwargs):
        if cls.__instance is None:
            cls.__instance=object.__new__(cls)
            return cls.__instance
        else:
            return cls.__instance
    def add(self):
        self.__x+=1
        print(self.__x)
a=A()
a.add()
b=A()
b.add()
#结果
2
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

装饰器

实际上就是使用闭包实现的，看一个简单小代码。
分析一下，首先wrapper就是一个装饰器函数，然后inner是一个闭包函数，装饰器实际起作用的也就是这么个闭包函数，外部函数有一个参数，实际上就是我们这里的目标函数x()，闭包函数需要返回该目标函数，还要带上小括号，如果有参数，需要通过闭包函数的参数传入，谭厚在括号里写上传给目标函数
需要先在目标函数前@一下，然后调用目标函数x()的时候，需要把闭包函数中的参数都加上。也可以用*args可变参数。
在执行的之后，会先执行闭包函数外部函数的代码，从上到下。然后会开始执行闭包函数，随后闭包函数返回目标函数，传参以后，开始执行目标函数。

def wrapper(function):
    print('this is outter')
    def inner_wrapper(x,y,k):
        print('this is inner dunction')
        print('{}+{}={}'.format(x,y,x+y))
        return function(k)
    print('ssss')
    return inner_wrapper

@wrapper
def x(k):
    print('this is x()',k)

x(1,3,1)
#执行
this is outter
ssss
this is inner dunction
1+3=4
this is x() 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

其实装饰器分为三类：

• 函数装饰器
• 带参数函数装饰器
• 类装饰器

函数装饰器
就是普通的闭包函数

def use_logging(func):
    def wrapper(*args, **kwargs):
        logging.warn("%s is running" % func.__name__)
        return func(*args, **kwargs)
    return wrapper

def bar():
    print('i am bar')
bar = use_logging(bar)
bar()
输出：WARNING:root:bar is runningi am bar

1
2
3
4
5
6
7
8
9
10
11
12

带参数函数装饰器
两层闭包函数，最外层可以在@里带上参数传入，第二层的参数是装饰器自动传入的函数参数，第三层就是装饰器执行的闭包

def use_logging(level):
    def decorator(func):
        def wrapper(*args, **kwargs):
            if level == "warn":
                logging.warn("%s is running" % func.__name__)
            return func(*args)
        return wrapper
    return decorator

@use_logging(level="warn")
def foo(name='foo'):
    print("i am %s" % name)

foo()
输出：
WARNING:root:foo is running
i am foo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

类装饰器
使用比较灵活，还可以依赖内部的__call()__方法，装饰器附加以后，就会调用这个方法

class Foo(object):
    def __init__(self, func):
        self._func = func
    def __call__(self):
        print ('class decorator runing')
        self._func()
        print ('class decorator ending')

@Foo
def bar():
    print ('bar')

bar()
输出：class decorator runing
bar
class decorator ending
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

常见数据类型

Python 有哪些数据结构

序列（列表、元组）、映射（字典）、集合
栈stack、队列queue、双向队列deque、链表linkedlist

• 元组：不能修改，用小括号定义，如果只有一个元素，需要加一个逗号

字符串

使用format格式化字符串

• 宽度：设置长度，如果填充的小于这个长度，默认补全空格
• 对齐：<>^，分别表示左对齐、右对齐和居中。默认居左
• 填充：除了目标字符串外填充什么，默认空格
• 逗号：可以显示数字的千分位
• 精度：.4f .4分别为浮点数的小数有效部分、字符串有效长度
• 类型：二进制b、八进制o、十进制d、对应的unicode字符u、小写十六进制x、大写十六进制X

大概顺序是:{填充}{对齐}{长度}{类型}{如果有数字的千分位}
示例

'{:*^30,}'.format(12345)
'************12,345************'

>>> '{:*^30b}'.format(12345)
'********11000000111001********'
1
2
3
4
5

集合

• S.remove(e)：移除元素e，如果不存在报错
• s.discard(e)：移除元素e。如果不存在无所谓
• s.update(b)：合并集合
• s.difference(b)：s和b的差集
• s.difference_update(b)：s和b的差集赋值给s
• s.intersection(b)：s和b的并集
• s.intersection_update(b)：s和b的并集赋值给s
• s.union(b)：s和b的合集

栈

队列

先进先出FIFO

import queue
a=eueue.Queue()
#入队
a.put(xxx)
出队
a.get()
1
2
3
4
5
6

双端队列

from collections import deque
a=deque([1,2])
#右边插入数据
a.append('x')
#向左添加
a.appendleft(yyy)
1
2
3
4
5
6

pop同理

列表

去重
list(set(target))
根据索引去除
使用pop()。不指定元素默认弹出列表尾部元素
指定下标以后弹出指定下标的元素。
列表的+=操作实质上是调用了extends，而不是不可变对象那种先相加然后创建新对象释放原对象（相加赋值）
删除元素：

• remove
• del l[index]
• pop()

字典

字典的键只能是不可变对象。
使用update()合并两个字典
删除元素：

• 字典移除也可以使用pop()，可以指定默认值，如果键不存在则使用默认值，否则报错。
• del d[key]也可以删除指定键的项
• popitem()：随机删除一项

defaultdict
普通字典在访问不存在的key时会报错，defaultdict不会报错，会返回一个默认值，可以在初始化的时候设置默认值的类型。
如果是int，不指定默认值访问不存在的key的时候，返回0

from collections import defaultdict
d=defaultdict(int)
d=defaultdict(str)
d=defaultdict(list)
1
2
3
4

OrderedDict
有序字典，插入的数据按照key排序存放

列表推导式

其实除了列表推导式，还有字典推导式和集合推导式。
集合推导式可以自动去重

#列表推导式
>>> [x for x in 'sssdddaaa']
['s', 's', 's', 'd', 'd', 'd', 'a', 'a', 'a']
#字典推导式
>>> s=[(1,'1'),(2,'2'),(3,'3')]
>>> {key:value for key,value in s}
{1: '1', 2: '2', 3: '3'}
#集合推导式
>>> {x for x in 'asdfghhgfdsa'}
{'g', 'd', 'a', 'h', 'f', 's'}
1
2
3
4
5
6
7
8
9
10

计算100以内的素数，前面的循环室遍历所有数，后面是看对每一个因子取余，如果是合数说明肯定会有一个可以除尽，也就是余数为0，即如果后面的列表没有0，说明是素数

[x for x in range(2,100) if 0 not in  [x%i for i in range(2,int(math.sqrt(x))+1)]]
1

可变对象和不可变对象

可变对象（对象内容是可变的）：列表、字典和集合。也就这三个可变了
不可变对象（对象内容是不可变的）：整型、元组和字符串
不可变对象
python中变量存放的是对象引用，相当于所有变量都是引用，对于不可变对象来说，虽然对象的值不会变化，但是引用是会变的。
比如对于不可变对象整数10，如果有三个对象值均为10，那么这三个对象的id一致，10这个引用则为3。
如下代码，一个整数先赋值，然后进行加操作，此时加操作以后，i已经是另一个对象了，因为整型是不可变的，指向75的引用，原先73的引用计数为0，应该被垃圾回收

i=73
i+=2
1
2

再比如有如下两个操作，那么其实内存中只存在一个值为1的对象，x和y都是对这个的引用，x和y的id都是一样的。

x=1
y=1
1
2

此时如果x=2，x的引用就会发生变化，内存中就会产生一个值为2的对象，引用发生了改变，此时x和y的id不一致了。
内存中值相同的对象只能存在一个，如果需要声明一个这个值的变量，就会给这个对象引用＋1
可变对象
对象的内容是可以被修改的，对象内容发生改变时，变量的引用不会变。
修改对象的值，因为引用的地址一致，所以其他引用对象的值也会改变。
如下可以看到，对于可变类型，即便值一样，内存地址也不一样，内存中可以存在多个值相同的对象，地址值不同.

>>> a=[1,2,3]
>>> id(a)
2017258406664
>>> a=[1,2,3]
>>> id(a)
2017258389896
>>> a+=[5,6]
>>> id(a)
2017258389896
1
2
3
4
5
6
7
8
9

值的变化不会引起创建新对象，地址不会发生改变，只会改变地址中的内容或者地址扩增（执行列表相加）
但是如果给a重新赋值的话那么就会重新创建一个对象。
这里有几个小特例
如果是赋值，就都是引用，如果是声明新变量，如下所示有一些特例

• 对于一些较小频繁用到的int，内存池中已经默认分配有对象，直接使用即可，范围是[-5, 256]，在使用的时候直接从池子取出来即可，因此每次的new一个i这个范围的int变量的id都一样，如果大于256或者小于-5，则创建的变量id则不一样
• 对于float类型没有，每次都需要重新创建一个对象
• 对于tuple类型，和float一样，值一样的id不同，也是重新创建一个对象。
• str类型的话，如果是单词类型，值一样id一样，因为会为频繁使用的单词类型字符串创建一个字典缓存，key是值，value是地址，如果存在就直接取地址返回，否则创建一个新的对象，保存在字典里；如果不是单词类型的字符串，id就不同

参数传递

python都是引用传递，对于不可变对象没什么问题，只会给对象引用+1，对于可变对象来说，传递就是真实的内存地址。
只允许引用传递其实是为了方便内存管理，因为是基于引用计数器的，比如赋值传参等操作都会给引用+1，有一个变量不再使用的时候，会-1，如果一个对象的引用计数为0，就会被回收释放。
但是解决不了循环引用的问题，使用了其他的GC方法（标记清除和分代回收机制）。

**深拷贝和浅拷贝

对于不可变对象，没有什么区别，主要用于可变对象
深复制：将待复制对象完全复制一份，改变原有的待复制对象不会对新的这个对象产生影响
浅复制，只能复制最外层的对象，复杂嵌套对象属于第二层+，不是最外层：

• 当浅复制的值是不可变对象时，会执行赋值操作，也就是id与原来的对象一致
• 当时复杂对象的时候，改变复杂对象中的值会使得新对象的值也随之改变

函数闭包

在一个内部函数中，对一个外部函数作用域的变量进行引用，而且外部函数返回值一般为内部函数，这个内部函数就是闭包。
闭包的一个作用是可以保存当前的一些运行环境，每次运行是能记住引用的外部作用域的变量的值。
如下，还有，python是可以返回函数的。也就是说result实质上是increment()函数，而不是start()结果。
因此可以通过添加小括号调用result指的函数得到内部函数的结果。

def start(x):
	def increment(y):
		return x+y
	return increment
result=start(1)
print(result)
print(result(8))
#输出
<function start.<locals>.increment at 0x0000011B6F321598>
9
1
2
3
4
5
6
7
8
9
10

虽然可以访问为外部函数的变量，但是无法修改其值，否则会报错找不到变量
看如下示例，for里面是没有域的概念，先用for将三个内部函数添加到列表里，然后再用一个for分别执行列表里的每一个内部函数，本来以为是0，2，4，结果是4，4，4。为什么呢
因为在追加内部函数的时候，没有保存i的值，而是在第二个for，也就是执行内部函数的时候，才去取i的值，而此时i已经是2了，所以就都是4

f=[]
for i in range(3):
	def add(x):
		return x*i
	f.append(add)
for temp in f:
	print(temp(2))
1
2
3
4
5
6
7

解决方案就是再加一层，把add变成闭包，利用外层函数保存每次i的值

f=[]
for i in range(3):
	def outter(i):
		def add(x):
			return x*i
		return add
	f.append(outter(i))
for temp in f:
	print(temp(2))
1
2
3
4
5
6
7
8
9

最后有一个nonlocal关键词，表明这个变量是一个外部函数的变量，这样的话每次调用内部函数的时候，其实x都是最开始的5.

def start():
	x=5
	def inner():
		nonlocal x
		x+=1
		return x
	return inner
s=start()
print(s())
print(s())
print(s())
print(s())
1
2
3
4
5
6
7
8
9
10
11
12

可以查看这个函数的闭包信息，start()closure返回一个元组包含引用的外部变量
如果内部函数没有引用外部变量，不是闭包，则返回None
如果没有外部函数没有返回内部函数，不是闭包，会报错

def start():
	x=5
	def inner():
		return x*2
	return inner
s=start()
print(s())
for i in start().__closure__:
	print(i,i.cell_contents)
#输出
10
<cell at 0x000002637BD27BB8: int object at 0x00000000771E6160> 5
1
2
3
4
5
6
7
8
9
10
11
12

实际应用大概有日志吧

内存管理

引用计数

Pytnon内部使用引用计数、保持和追踪内存中的对象，所有对象都有引用计数
计数增加的情况：

• 赋值
• 创建对象
• 传参
• 将其添加到容器里（列表字典等）

计数减少：

• del
• remove()移除

优点：

• 高效
• 运行没有停顿，只要变量引用引用为0，立刻回收
• 便于实现

缺点：

• 维护引用计数的资源过大
• 无法解决循环引用

垃圾回收

垃圾回收机制基于引用计数，当一个对象的引用计数为0的时候，认为这个对象像是可以被回收的，会立刻回收。
基于引用计数的机制的缺陷呢，可以使用标记清除和分代回收机制完善。
但是对于重写了__del__()方法的，好像不能自动回收，得手动del。
标记清除
分为两个节点，第一阶段是将系统中的活跃对象进行标记、第二阶段是回收不活跃的对象。
第一阶段呢，将内存中的对象根据引用关系，可以构造成一个有向图，对象是有向图的节点，引用关系是边。然后从根对象（root object，全局变量、调用栈、寄存器）开始遍历，可达的节点都标记为活跃对象。
然后对不活跃的对象进行回收。
但是标记清理不能一次性对所有对象进行扫描处理。
通过gc.get_threshold可以获取到一个阈值(700,10,10)，第一个就是标记清除的阈值。
缺点是即便有一小部分未标记，也要扫描所有对象然后标记清除
分代回收
存活的对象越久，越容易被引用，更不应该被清除，为了克服标记清除的这个缺陷，使用分代回收
一共分为0代、1代和2代。所有对象在第一次创建或者声明的时候都是第0代，执行一次标记清除留下来的对象代数+1。
在系统中有个参数设置，当先对第0代的对象进行扫描清除，一定次数以后，对0和1代进行扫描清除，再经过一定次数以后，对0、1和2代进行清除。这两次一般默认为好像都是10次。
或者当年轻一代满了，调用垃圾回收，讲仍然存活的放在中年代里，也就是第1代，以此类推

内存池

为了方便管理内存，python对于小于256字节的内存使用pymalloc申请，超过的使用malloc
然后对于整数，-5~256有预先分配好缓存，可以直接使用，如果两个变量都赋值5，那个id地址一样。但是假设一个整型数字内存被释放，这块内存在以后仍然只能申请整型，不能用于浮点数等
对于单个字符，也是同上
对于字符串，单个单词的话，创建好一个对象以后，会在内存中记录下来，可能比如哈希表，在第二次使用的时候，可以直接引用。

并发

GIL

python的线程底层封装了Linux的POSIX Thread。
全局解释器锁相当于互斥锁，当这个线程在运行的时候，CPython解释器会锁住当前线程，阻止别的线程运行，当多个线程交替运行的时候，就造成一种并行的假象。
使用GIL主要和CPython有关，这里面使用了引用计数的机制，当有两个线程同时对一个变量进行引用的时候，可能会造成引用计数的竞争条件导致最终计数只会增加一，当某一个线程退出的时候，计数减1，可能会满足释放对象的条件，这时候第二个线程如果访问这个对象的时候，可能就会因为找不到然后报错了。
条件竞争漏洞（Race condition）官方概念是“发生在多个线程同时访问同一个共享代码、变量、文件等没有进行锁操作或者同步操作的场景中。”
总结一下使用GIL的两个主要原因：

• 避免内存管理这种模块机制出现条件竞争的问题
• CPython底层使用了大量的C语言库，而这些库并不是线程安全的（因为线程安全会降低性能以及提高代码复杂度）

同时还有这么一个概念check_interval，会一定时间间隔去检查GIL的使用情况，如果达到间隔会强制当前线程释放GIL锁，避免一个线程长时间执行。
但是即便有着GIL，也还不是线程安全的，比如有一个全局变量n，多线程里面每次n=+1，输出n。这就不是线程安全
n+1的字节码其实如下，由四个语句组成，这四个是可以被打断的，而不是一个整体原语之类的，因此不安全。

>>> import dis
>>> dis.dis(foo)
LOAD_GLOBAL              0 (n)
LOAD_CONST               1 (1)
INPLACE_ADD
STORE_GLOBAL             0 (n)
1
2
3
4
5
6

还是需要自己用锁实现线程安全

    n = 0
    lock = threading.Lock()
     
    def foo():
        global n
        with lock:
            n += 1
1
2
3
4
5
6
7

对于单核来说其实这样的多线程没有优势，，多核CPU的时候，还是只有一个线程运行，而且每个线程在多个CPU交替运行，会造成CPU切换资源的浪费运行变慢。（在多线程会对GIL进行抢占，如果没有得到GIL的线程就会让CPU等待，不能合理利用多核心）

多进程

因为GIL的存在，使得多线程是假的，无法发挥多核心CPU的优点。
multiprocessing模块支持多进程的使用，差不多完整复制了threading提供的接口并且把线程改为进程。每个进程有自己的GIL，不会出现竞争。
比如Apache服务器就是父进程监听，当有新的HTTP请求到来的时候，fork出一个子进程处理请求。
创建一个进程
Process([group [, target [, name [, args [, kwargs]]]]])
一些常用的函数：

• start()：启动进程，并调用该子进程中的p.run()
• run()：进程启动时运行的方法，正是它去调用target指定的函数，我们自定义类的类中一定要实现该方法
• terminate()：强制终止进程p，不会进行任何清理操作，如果p创建了子进程，该子进程就成了僵尸进程，使用该方法需要特别小心这种情况。如果p还保存了一个锁那么也将不会被释放，进而导致死锁
• is_alive()：返回进程是否在运行。如果p仍然运行，返回True
• join([timeout])：进程同步，主进程等待子进程完成后再执行后面的代码。线程等待p终止（强调：是主线程处于等的状态，而p是处于运行的状态）。timeout是可选的超时时间（超过这个时间，父线程不再等待子线程，继续往下执行），需要强调的是，p.join只能join住start开启的进程，而不能join住run开启的进程。

协程

python多任务—协程（一）
介绍就不说了

yield和send

这里分为send和next两种。

send
python2里面可以用yield和send生产者消费者实现
通过send()方法可以把参数传递给yeild，可以强行修改yield的值，同时send是会有返回值的，返回值就是yield后面的值。如下代码，好像也可以用next
这里第一次需要传入None，因为第一次没有一个yield可以赋值。
然后这里send(n)就是可以传入一个参数n，然后消费者里面的n的值就不是后面r的值了，而是传入的n，这个r的值就是send的返回值

#-*- coding:utf8 -*-
def consumer():
    r = ''
    while True:
        n = yield r
        if not n:
            return
        print('[CONSUMER]Consuming %s...' % n)
        r = '200 OK'

def producer(c):
    # 启动生成器
    c.send(None)
    n = 0
    while n < 5:
        n = n + 1
        print('[PRODUCER]Producing %s...' % n)
        r = c.send(n)
        print('[PRODUCER]Consumer return: %s' % r)
    c.close()

if __name__ == '__main__':
    c = consumer()
    producer(c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

next
也是使用yeild生成器来实现切换，可以从一个函数切换到另一个函数，如下，先构造两个生成器，然后分别调用next()方法就可以唤醒相应的生成器，执行yeild的操作，然后保存上下文，等待下次唤醒，实现相应的切换。

import time

def task_1():
    while True:
        print("--This is task 1!--before")
        yield
        print("--This is task 1!--after")
        time.sleep(0.5)

def task_2():
    while True:
        print("--This is task 2!--before")
        yield
        print("--This is task 2!--after")
        time.sleep(0.5)
        
if __name__ == "__main__":
    t1 = task_1()  # 生成器对象
    t2 = task_2()
    # print(t1, t2)
    while True:
        next(t1)  # 1、唤醒生成器t1，执行到yield后，保存上下文，挂起任务；下次再次唤醒之后，从yield继续往下执行
        print("\nThe main thread!\n")  # 2、继续往下执行
        next(t2)  # 3、唤醒生成器t2，....
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

结果如下，运行到yield关键字的时候就会暂停，等待下一次唤醒

asyncio和yield from

这是python3.4出来的功能，内置了异步IO的支持。
调用get_event_loop()然后生成三个函数。
这里每个test就是一个协程函数，yield from可以方便调用另一个生成器，因为后者sleep也是一个协程，所以线程会中断执行下一个循环，当sleep返回以后，r就能得到返回值了（这里是None），比如这里可以进行一些IO操作，在这期间主线程不会等待，会继续运行其他协程。

#-*- coding:utf8 -*-
import asyncio

@asyncio.coroutine
def test(i):
    print('test_1', i)
    r = yield from asyncio.sleep(1)
    print('test_2', i)

if __name__ == '__main__':
    loop = asyncio.get_event_loop()
    tasks = [test(i) for i in range(3)]
    loop.run_until_complete(asyncio.wait(tasks))
    loop.close()
1
2
3
4
5
6
7
8
9
10
11
12
13
14

更新一下

#-*- coding:utf8 -*-
import asyncio

async def test(i):
    print('test_1', i)
    await asyncio.sleep(1)
    print('test_2', i)

if __name__ == '__main__':
    loop = asyncio.get_event_loop()
    tasks = [test(i) for i in range(3)]
    loop.run_until_complete(asyncio.wait(tasks))
    loop.close()
1
2
3
4
5
6
7
8
9
10
11
12
13

Gevent

这其实分为两个，一个是基础的greenlet，另一个是比较高级的Gevent
greenlet
这个创建协程以后可以调用switch()方法手动切换线程。
如下greenlet(func)创建两个协程，参数就是需要执行的函数名，然后手动切换的话就直接调用switch即可。

from greenlet import greenlet
import time

def task_1():
    while True:
        print("--This is task 1!--")
        g2.switch()  # 切换到g2中运行
        time.sleep(0.5)

def task_2():
    while True:
        print("--This is task 2!--")
        g1.switch()  # 切换到g1中运行
        time.sleep(0.5)
        
if __name__ == "__main__":
    g1 = greenlet(task_1)  # 定义greenlet对象
    g2 = greenlet(task_2)
    
    g1.switch()  # 切换到g1中运行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Gevent
是基于Greenlet实现的网络库，通过greenlet实现协程，当协程遇到IO操作或者网络访问等，会自动切换到另一个协程，等到IO结束以后，会再切换回来。是自动做的，保证一直有协程运行，而不是一直死等着IO操作。
相比于greenlet这个的优点就是可以根据执行的操作自动切换

async关键字

这个好像不太涉及切换的问题，就相当于进程或者线程，创建以后就异步执行，然后直到结束
使用这个关键字可以定义一个协程函数，调用run_until_complete把协程对象添加到事件循环里，然后异步执行，直到这个函数执行完成。

import asyncio
 
async def work(x):  # 通过async关键字定义一个协程
    for _ in range(3):
        print('Work {} is running ..'.format(x))

coroutine_1 = work(1)  # 协程是一个对象，不能直接运行

# 方式一：
loop = asyncio.get_event_loop()  # 创建一个事件循环
result = loop.run_until_complete(coroutine_1)  # 将协程对象加入到事件循环中，并执行
print(result)  # 协程对象并没有返回结果，打印None
# 方式二：
# asyncio.run(coroutine_1)  #创建一个新的事件循环，并以coroutine_1为程序的主入口，执行完毕后关闭事件循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

面向对象

面向对象是相当于面向过程而言的，面向过程语言是一种基于功能分析的，以算法为中心的程序设计方法，而面向对象是一种基于结构分析的，以数据为中心的程序设计思想。在面向对象语言中有一个很重要的东西，叫做类。面向对象有三大特性：封装、继承、多态。

面向对象的三大特征

• 封装：将实现某些功能的方法等封装在一个类中，用户在使用时直接调用这个类就行了，而不需要关注如何具体实现这个类的功能
• 继承：一个类可以通过继承的方式去使用父类所有的方法和变量等，可以多重继承
• 多态：重载和重写

重载和重写

重载主要解决的是同名函数的不同参数类型和个数的问题
都是多态的实现，重写是子类对父类的已有的方法重新写一遍，需要保证方法名、参数以及返回类型和父类保持一致；重载是同名的方法拥有不同的参数列表，如参数的个数或者类型不同，甚至顺序不同，返回值的类型没有要求，可以不同可以相同，不能从返回值相同判断重载。

__init__()、__new__()、__call__()、__str__()、__repr__()

• __init__(self)：在实例化对象的时候会调用
• __str__(self)：适合人阅读的，return的值可以使用print()打印
• __repr__(self)：解释器可以阅读的格式，可以直接在终端执行对象名就可以看到这个函数返回值
• __call__(self)：在把对象当成函数使用的时候回调用这个函数，同时不影响类正常的生命周期。如a=A() a(1,2)，其中a(1,2)就会调用call方法
• __new__(self)：第一个参数是当前类，返回值是一个类的实例，在init之前调用，返回的实例作为init的第一个参数

调用父类方法

直接命名一个和父类函数名一样的函数，就可以重写，然后默认调用子类这个。
在其中可以使用super().xxx()调用父类方法。

class Animal:
    def heshui(self):
        print('动物正在喝水')

class Cat(Animal):
    def heshui(self):
        super().heshui()
cat = Cat()
cat.heshui()

>>>动物正在喝水
1
2
3
4
5
6
7
8
9
10
11

强制调用父类的私有方法，比如__heshui(self)，直接调用会发现报错，因为这其实是私有的，主要是将其名字改为了_Animal__heshui(self)，可以如下调用
super()._Animal__heshui()
然后如果子类定义了__init__(self)方法，是不能直接调用父类的变量等属性，因为相当于重写了父类的构造函数，需要显式调用一下父类的构造函数才行，如下
super().__init__()

类可以定义哪几种方法

• 常规方式：就是需要第一个参数self
• @classmethod修饰方式：添加注解以后可以使用{类名}.{方法名}()调用使用，第一个参数是类本身
• @staticmethod修饰方式：添加注解以后可以使用{类名}.{方法名}()调用使用，不需要有类的参数

静态方法和类方法应用场景

计算机网络

HTTP的特点

• 允许连接任意类型的数据，使用Content-Type标记
• 是无状态的，每次链接都会被认定为是一个新的连接，不会记录之前访问的状态信息等
• h支持客户端服务器端模式

http的缓存机制

客户端第一次请求数据后，将返回的数据保存到缓存数据库中。
分为强制缓存和对比缓存。
强制缓存在使用的时候如果没过期，可以直接拿来用。如果过期了会像服务器申请新资源。
对比缓存不管中没中缓存，都需要使用从数据库获取到的缓存数据标识发给服务器进行验证，然后返回数据使用。
强制缓存
浏览器请求服务器资源的时候，服务器会将缓存的一些信息规则一块返回，比如Expires/Cache-control，前者是HTTP/1.0的，后者是1.1的，前者设定一定时间后会过期，但是依赖于服务器的时间，是服务器端返回的过期时间，如果客户端时间和服务器端差得多，那就出事了
cache-control呢，有好几个参数，可以选择缓存还是不缓存，缓存的时间等。

对比缓存
有两个标识，（Last-Modified / If-Modified-Since） （Etag / If-None-Match）
一个是最后修改时间（Last-Modified / If-Modified-Since）
需要进行比较判断才能使用缓存，在使用的时候，浏览器先从缓存数据库获取到缓存标识，然后发送给服务器，服务器判断是否过期，如果没有，返回304头部，没有实体部分，速度很快，客户端直接从数据库读取缓存。
第一次请求资源服务器会返回该资源的最后修改时间放在last-Modified字段上，再次请求后，会把这个值放在If-Modified-Since字段里，服务器会比较这个最后修改时间，如果资源修改时间小于等于这个（也就是说没过期），就是304；如果大于（过期了）就是返回200的状态码和资源实体部分。

还有一个是标识（Etag / If-None-Match），这个优先级更高
服务器响应会告诉客户端该资源在服务器的唯一标识，再次请求后，会将该标识和被请求资源的标识进行对比，不一致返回200+实体部分，否则304

几个常用的状态码的意思

状态码：

• 200：正常响应
• 204：正常响应，但是没有实体返回
• 301：永久重定向，比如资源被分配了其他的URL，需要更换然后访问
• 302：临时重定向，
• 304：访问的资源没有被修改，所以服务器不会返回数据，通常是已经缓存了报304
• 400：报文中存在错误
• 401：未经许可，比如没有经过认证
• 403：服务器拒绝访问，可能也是认证失败的问题
• 404：页面不存在，可能是URL错误
• 500：服务器内部错误，比如服务端代码报错等

HTTP1.0和1.1和2.0的区别

HTTP1.0：

• 默认短连接，每次请求都是一个新的无状态请求
• 默认一台主机有一个IP，不传递主机名

HTTP1.1：

• 默认长连接，允许在一个TCP连接中处理多个请求
• 增加range字段，支持断点续传
• 多增加了几个状态码，如状态码100：对于大文件服务器端如果不想请求可以返回100，指示请求是否会被正常响应
• 由于虚拟主机的发展，一台物理机可以存在多个虚拟机，需要使用HOST信息具体指定

HTTP2.0：

• 1.1是基于文本格式传输数据，2.0是采用了二进制格式传输，更加高效
• 复用，就是一个链接中可以传输多个请求或者响应
• 允许服务器主动推送给客户端消息

多路复用是通过帧实现的，2.0中将数据包体积再次减小至多个帧，模拟流的形式。
其中Type共有十种类型标识每个帧，通过ID标识这个帧所属的流，实现全双工非阻塞通信。

帧类型大概如下几种：

HHTP协议头部的字段

有通用首部字段、请求首部字段、响应首部字段、实体首部字段
通用头部

• cache-control：控制缓存类型
• Date：创建报文的时间
  请求头部
• Accept：接受的内容类型
• Accept-Charset：接受的字符编码
• Accept-Encoding：接受的编码格式
• Accept-Languge：接受的语言
• Cache-Control：缓存机制
• Content-Length：请求体长度
• Content-MD5：对请求体内容MD5编码
• Content-Type：请求体MIME类型
• Content-If-Modified-Since：更新时间，如果更新时间到服务器接受请求的时间资源没有发生变化，
• User-Agent：用户代理字符串
• If-None-Match：客户端ETAG，服务器端会对比ETag，如果没有变化返回304
• X-Csrf-Token：csrf防止跨站请求伪造
• X-Request-ID：标识客户端和服务器端的HTTP请求

响应头部

• Cache-Control：缓存机制是否可以缓存，单位是秒
• Content-Encoding：响应体的编码格式
• Content-Length：响应体长度
• Content-Language：响应体语言
• Content-MD5：对响应体内容进行二进制MD5 base64编码
• Etag：特定资源的版本号，比如摘要
• Last-Modified：资源最后修改的时间
• Content-Type：响应体MIME类型

在HTTP请求从浏览器发出到服务器接收之前，会有哪些流程步骤？

对于静态资源，会通过一个地理CDN技术，选择一个距离用户最近的一个服务器去获取相应资源下载。
然后可能会通过反向代理服务或者负载均衡服务。
反向代理：实质上对用户来说就是目标服务器，反向代理使得用户不会感知到内网的存在，比如正常应该是经过网关，然后再去跳转到相应的内网服务器，多个步骤，有这个以后就会看起来只有一步，降低网络和服务器的一个负载使用。代理服务器还可以配置比如防火墙之类的功能进行一个安全防护
负载均衡：在上一步之后，会根据请求流量的特征以及当前系统中每个服务器的负载情况等数据，将请求分发到合适的服务器进行处理然后返回结果。

HTTP的缺点

HTTP主要有三个缺点：

1. 是明文传输的，数据容易被窃取到
2. 没有对双方身份进行一个确认
3. 没有对数据完整性进行验证，可能会被篡改

基于以上几个问题，可以通过增加一些功能，比如加密传输和身份认证等，这就是HTTPS

数字证书是什么

服务器端向CA申请证书，避免中间人攻击，证书包括：证书内、做证书签名算法以及签名
签名：
CA使用证书签名对证书呢容进行哈希运算
然后使用私钥对哈希加密得到签名

验证：
浏览器得到证书，获取到证书内容、证书签名算法以及数字签名
使用公钥解密签名
使用算法对证书内容进行哈希运算
对比上面两个的值，如果一致说明可信

HTTP和HTTPS区别

HTTP：

• 超文本传输协议，明文传输
• 80端口

HTTPS：

• 使用SSL协议加密传输和身份认证
• 使用到CA证书，一般收费
• 443端口

HTTPS原理

HTTPS是在应用层和传输层中间的，在HTTP和TCP中间加了一层SSL（安全套接字）和TLS（传输层安全）协议，通过身份认证和加密传输保障数据传输的安全性

1. 先进行TCP三次握手
2. 客户端发送Client Hello，告诉服务器端一些信息，如需要访问的域名、支持的加密（哈希）算法，一个随机数等
3. 服务器端返回Server Hello，选择一个加密算法；随后并且发送随机数和自己的证书，证书中则包括了密钥的公钥、访问的网址、证书颁发机构以及过期时间等；其中私钥保存在服务器
4. 客户端对证书进行校验（TLS实现）。如是否过期、颁发机构、是否是自己访问的网址以及是否合法证书而不是假的。如果通过的话，对随机数，使用公钥进行加密（RSA加密），或者DH也行好像，发送给服务器端
5. 服务器端使用私钥就可以解密得到随机数，用于后续的加密通信

SSL和TLS其实是一个东西对称加密的东西，其实是一个东西，在最之前是SSL（安全套接字协议），经过几个版本的发布，SSL3.0升级以后命名为TLS1.0，是基于SSL之上的。
核心是非对称加密，使用公钥和私钥进行加密。

• 非对称加密：公钥私钥不同，生成依靠单向门限函数，是单向的。但是i依赖于较为复杂的数学运算，加解密时间较长。
• 对称加密： 密钥的生成代价较小，加解密开销少。

实际中，对称加密安全性完全依赖于密钥的保密性，如果通信的时候密钥被截获了，安全性就不能够被保证了，因此可以使用非对称加密先对密钥进行一个加密传输，然后双方使用私钥进行解密得到密钥，就可以用于对称加密了。
但是有这么个问题：如果使用SSL/TLS需要知道对方的公钥，公钥需要在网络上直接进行通信传输，那么如果被截获了，就可以出现中间人攻击
A和B通信，B给A发自己的公钥，但是被C截获了，C把自己的公钥发给了A，A以为这是B的，就正常用；然后给B发送数据包，被C截获，使用C的私钥解密就可以获得数据包；这其中AB都以为是和对方直接通信，然而全部被C知道了
因此就需要有一个可信的第三方来保证，CA

• CA有服务器端的公钥，给服务器端发布证书，证书上包含：加密签名（CA私钥对消息摘要进行加密）、证书内容和哈希算法
• 客户端核验服务器端的证书身份，找到CA，得到CA的公钥，对签名进行解密，得到一个摘要值；客户端对证书内容进行摘要，在得到一个哈希值，进行对比如果一致则校验成功

HTTPS CA

如何验证我访问的服务器就是正确的服务器呢。
证书是由CA生成颁发的，加密需要使用到CA的私钥。
验证，证书里面有CA的信息

• 客户端使用CA的公钥解密数字签名
• 利用证书里面的算法对证书内容进行哈希运算
• 对比上面两个结果，如果一致，就说明是正确的
• 然后从证书内容里面取出服务器的公钥，进行加密传输

如果证书被冒用了，虽然校验可以通过，但是发送的消息是经过加密的，假网站没有私钥不能解密，保证安全。

HTTPS中间人攻击

• 没有CA的前提下，服务器端会直接发送自己的公钥给客户端
• 被攻击者截获，然后攻击者给客户端发送一个假密钥
• 客户端用假密钥加密子集选择的一个随机数（密钥）发送给服务器端
• 再次被攻击者截获，解密得到真正的随机数（密钥），发送一个假的密钥哈希给服务器端
• 服务器端使用这个进行加密传输
• 这样攻击者就有了服务器端和客户端加密的这个假的密钥，进行相应的解密就可以得到请求内容

解决方法就是嵌入CA证书

DNS解析过程

1. 浏览器搜索自己的DNS缓存
2. 如果没有，搜索操作系统的缓存以及hosts文件
3. 如果没有，发送请求给本地域名服务器查找，如果找不到，依次询问根域名服务器、顶级一名服务器等，最终返回对应的IP给本地域名服务器
4. 本地域名服务器缓存以后，返回给操作系统
5. 操作系统缓存起来，返回给浏览器

cookie和session

cookie：

• 保存在客户端
• 可以设为长时间保存，如记录登录信息
• 保存在浏览器本地，相对不安全
• 存储大小大概为4k

session：

• 保存在服务器端
• 一般过期时间较短，或者浏览器关闭后就失效
• 相对较为安全
• 理论上没有上限，但是有可能会影响性能，所以不要存储太多

幂等

幂等函数或者幂等方法，指的是不管运行一次还是运行多次，结果都是一致的，不会改变系统状态，也不会对系统造成影响。

传输层的协议常用的有哪些

• TCP：传输控制协议
• UDP：用户数据报协议

TCP和UDP的区别

TCP

1. 提供了面向连接的可靠传输协议（接受到的数据是完整的、有序的、无差错的）
2. 拥有拥塞控制、差错控制和流量控制等机制
3. 是面向字节流的
4. 是一对一的协议
5. 是可靠交付的
6. 是全双工的，收发双方都有缓存区临时保存收发的数据

UDP：

1. 尽最大努力交付，不保证可以准确无误的传输
2. 面向无连接的，不需要提前建立连接，减少开销，使用方便快捷
3. 是面向报文的，接受应用层的报文添加首部以后就发送，太长会分片
4. 没有拥塞控制等机制保证传输
5. 支持一对一、一对多、多对多
6. UDP报文首部很小，8字节，TCP是20，降低开销

TCP和UDP的使用场景

TCP：数据完整性要求较高的，比如FTP文件传输，邮件发送接收等
UDP：响应要求高的，比如实时通信、网络视频等

TCP和HTTP的区别

TCP是传输层的协议，解决的是数据如何在网络中传输。TCP三次握手建立连接以后，连接会一直存在，直至通信结束以后才会断开连接。
而HTTP是应用层协议，解决如何包装数据，采用请求-响应，是基于TCP的，HTTP/1.0中每一次给服务器端发送请求都会建立一个新的TCP连接，HTTP1.1中服务器端可以在一个链接中处理多个请求，提高了利用率降低开销，是一种短连接。
如果想维持连接关系，需要定时去发送数据包证明自己在线
如果高并发的时候，服务器端会存在大量的TIMEWAIT状态的连接，会导致端口等资源不足从而无法正常响应连接。
可以通过keep-alive参数设置连接持续的秒数，会一直持续这么久

TCP怎么做到可靠传输

• 校验和：对数据包二进制求和然后取反，如果校验和出错，将认定这个报文是错误的，丢弃
• 确认号和序号：通过序号判定数据包的顺序。也就是seq和ack。服务器端返回的数据包ack表示期望收到客户端传来的下一个数据包的seq
• 超时重传：发送一个数据包后，启动一个定时器，如果一定时间没有收到确认数据包将重传。（没有收到ack的原因，发送的数据包丢失了，重传以后会返回ack，返回的ack确认包丢失了，重传以后通过序号判断重复了，直接丢弃，然后返回ack）
• 流量控制：收发双方都有一定的缓冲空间，TCP接收端只允许发送端发送接收缓冲区能够容纳的数据包，如果接收端无法处理多余的数据包会发送消息给发送端，让其减缓发送速率。（流量控制协议采用的是可变大小的滑动窗口协议）。是为了保证接收方正常接收数据
• 拥塞控制：网络拥塞时会减少发送速率。降低网络的拥塞程度。（四个算法：慢开始、拥塞避免、快重传、快恢复）

TCP数据包的序号和确认号

序号其实是上一个数据包最后的一个字节数。
发送方发送一个序号为500的大小为10字节的数据包，接收方收到以后，会返回一个确认包，这个确认包的确认好ack=510，表明接收到了，而且期望下一个数据包的序号是510.

滑动窗口除了用在可靠传输的保证,还问了有什么作用(流量控制）

流量控制。窗口是缓存的一部分，暂时存放字节流，收发双方各有一个窗口，通过TCP报文的窗口字段告诉对方自己的值，便于对方设置自己的窗口大小。

为什么不能用两次握手进行连接？

1. 做好双方发送数据的准备工作，协商好初始序号，确认双方的收发能力。
2. 避免已失效的连接请求报文到达服务器端造成错误
   . - 比如第一个SYN消息延迟了，然后重发，第二次建立链接成功，通信完后断开（或者不断开？）。但是此时第一次SYN到了，服务器返回ACK，但是此时客户端并没有进行连接，就会出问题
   . - 服务器端返回的ACK丢失，但是此时服务器端认为链接已经建立 ，就等待接收数据，但是客户端没有收到ACK，在等待ACK，死锁

一些补充：
如果第二次报文丢失，客户端会一直等待链接，但是服务器会认为连接建立，开始传输数据，但是此时客户端仍在等待链接，因此会丢弃传来的数据，然后服务器端会超时重传，造成死锁。

其实这是由TCP的自身特点可靠传输决定的。客户端和服务端要进行可靠传输，那么就需要确认双方的接收和发送能力,不然容易出现丢包的现象

• 第一次握手: 可以确认客服端的发送能力
• 第二次握手: 可以确认服务端的接收能力 和 发送能力
• 第三次握手: 可以确认客户端的接收能力。

TCP三次握手丢包怎么解决

如果第一个SYN包丢了，服务器端不知道客户端发来的请求，不会返回ack，客户端会进行超时重传，一共有三次，分别是5.8s、24s和48s，一共76s左右，大多数系统设定最长等待时间为75s
如果是服务器端返回的SYN+ACK丢了，客户端就不知道服务器端收没收到数据，仍然会进行超时重传。此时服务器端进入了同步已接收状态，收不到客户端返回的普通ack，也会进行重传SYN+ACK，超时时间分别是3s、6s和12s，linux默认五次好像，如果还没有回应，关闭连接。客户端也会重传SYN，服务器端收到以后立刻返回SYN+ACK
如果是最后客户端返回的普通ack丢失了，服务器端会因为不知道客户端收没收到SYN+ACK而重传，但是此时客户端已经进入连接已建立状态，会立刻发送数据包，而服务器端仍处于同步已接收状态，有两种说法：

1. 服务器端收到数据包后立刻相应RTS，然后关闭连接
2. 服务器端通过数据报文的确认序号判断是否连接成功，从而直接建立连接

为什么连接的时候是三次握手，关闭的时候却是四次握手

三次握手的时候收到SYN请求以后，可以直接返回SYN+ACK报文，同步和确认。而关闭的时候，客户端发来的连接释放报文时，客户端没有数据发送了，但是服务端可能还有数据需要传输，无法立即关闭，因此需要先返回一个确认报文ACK，告诉客户端收到了FIN报文，但是服务器可能还需要发送数据，随后等服务器端处理完后，继续返回FIN报文告诉客户端可以关闭了

为什么TIME_WAIT状态需要经过2MSL(最大报文段生存时间)才能返回到CLOSE状态

四个报文发送完成后理论上是可以关闭了，但是实际网络状况并不理想，可能会导致客户端无法成功发送ACK给服务器端，此时服务器端会继续发送FIN报文，TIME-WAIT就是避免ACK丢失无法到达服务器端，为了重发，等待重新发送ACK的，2MSL就是一个发送和一个回复所需的最大时间

1. 防止上一次连接中的包，迷路后重新出现，影响新连接（经过2MSL，上一次连接中所有的重复包都会消失）
2. 可靠的关闭TCP连接。如果最后一个fin的ack丢失，客户端已经关闭，服务器端没收到，又重传fin，会受到RST而不是ACK

四次挥手中如果客户端发给服务器的最后一个报文丢失了会怎么样

服务器端会在超时后，继续返回FIN数据包告知客户端，客户端此时处于等待关闭状态，等待两个报文最长寿命时间，客户端要保证极端情况下也能接受到服务器的超时重发FIN报文。但是如果真的没有回应，服务器端会始终处于最终确认状态，而客户端已经关闭。
此时如果有新连接，会返回RST报文给客户端，因为出错连接过程就会被终止。
还有可能会导致，最后的ack延迟，连接已经关闭了而且有了新的链接进来，这时候丢失的ack收到了，会对新连接造成错误。
两个时间是允许丢失一次，因为网络中连续丢失两个的可能性太低了，所以避免不必要的开销，就两个MSL

TCP如何解决乱序和丢包的问题

TCP报文段的序号seq解决乱序问题，ACK确认包解决丢失的问题。
丢包的问题类似于TCP可靠连接？

SYN泛洪攻击

ddos。
客户端发送连接请求报文给服务器端，服务器端返回SYN+ACK报文，此时客户端不会返回确认报文，因此服务器端会持续返回ACK报文，造成资源的消耗。
当短期内存在大量的这种半连接时，就可能会导致服务器端资源枯竭从而崩溃。
而好像三次握手失败以后，不会重发ACK，会发送RTS数据报，直接进入CLOSED状态，避免SYN泛洪
服务器端没有收到对于SYN+ACK的确认后，会尝试重传，超时3s、6s以及12s重传，如果还没有回应会直接关闭连接，这个次数可以在tcp_synack_retries修改

解决措施：

• 降低syn timeout，服务器端及时释放半连接
• 过滤ip，短时间内如果大量有某个ip的syn请求，视为遭到了攻击，通过防火墙等措施避免
• 不断检测无效连接，及时释放。但是可能会导致正常连接被关闭。
• SYN Cache技术（延迟分配TCB）。收到SYN报文后，不急着分配TCB，先返回一个ACK报文，将该半连接信息保存到哈希表中，随后再次收到ACK以后，再分配TCB资源
• SYN Cookie技术（延迟分配TCB）：使用特殊算法计算出一个序号，包含了对方IP、端口等固定信息，以及对方不知道的己方的一些固定信息，收到对方确认报文后，重新计算 序号，如果匹配，则创建TCB

TCP拥塞控制

详见计网知识点文章吧

如果已经建立了连接，但是客户端突然出现故障了怎么办

TCP存在有保活定时器。keepalive时服务器每收到客户端传来的信息都会重置定时器，当一定时间没有收到客户端消息时，一般是两个小时，服务器端会发送探测报文，之后每隔75s发送一次，连续十次没有回应后，任务客户端出现故障，连接关闭

ARP是地址解析协议，简单语言解释一下工作原理。

（1）首先，每个主机都会在自己的ARP缓冲区中建立一个ARP列表，以表示IP地址和MAC地址之间的对应关系。
（2）当源主机要发送数据时，首先检查ARP列表中是否有对应IP地址的目的主机的MAC地址，如果有，则直接发送数据，如果没有，就向本网段的所有主机发送ARP数据包，该数据包包括的内容有：源主机IP地址，源主机MAC地址，目的主机的IP地址。
（3）当本网络的所有主机收到该ARP数据包时，首先检查数据包中的IP地址是否是自己的IP地址，如果不是，则忽略该数据包，如果是，则首先从数据包中取出源主机的IP和MAC地址写入到ARP列表中，如果已经存在，则覆盖，然后将自己的MAC地址写入ARP响应包中，告诉源主机自己是它想要找的MAC地址。
（4）源主机收到ARP响应包后。将目的主机的IP和MAC地址写入ARP列表，并利用此信息发送数据。如果源主机一直没有收到ARP响应数据包，表示ARP查询失败。

TTL是什么？作用是什么？哪些工具会用到它（ping traceroute ifconfig netstat）？

TTL是指生存时间，简单来说，它表示了数据包在网络中的时间，经过一个路由器后TTL就减一，这样TTL最终会减为0，当TTL为0时，则将数据包丢弃。
这样也就是因为两个路由器之间可能形成环，如果没有TTL的限制，则数据包将会在这个环上一直死转，由于有了TTL，最终TTL为0后，则将数据包丢弃。ping发送数据包里面有TTL，但是并非是必须的，即是没有TTL也是能正常工作的，traceroute正是因为有了TTL才能正常工作，ifconfig是用来配置网卡信息的，不需要TTL，netstat是用来显示路由表的，也是不需要TTL的。

数据结构

排序

稳定排序：

• 冒泡排序
• 插入排序
• 归并排序

不稳定排序：

• 快速排序
• 选择排序
• 希尔排序
• 堆排序

应用场景

空间大资源充足的时候，如果要求时间效率，可以使用归并排序
快速排序的时间是最省的，但是最坏情况下不如堆排序和归并排序
小数据的话快速排序不如插入排序
当数据基本有序或者数据较少的时候，插入排序不错，冒泡排序也不错。对于基本有序的数据，插入排序的时间是快速排序的一半
堆排序适合海量数据，比如一百万个数里面找到前1000大个数字，使用小顶堆

插入排序

时间复杂度：

• 最好：O(n)
• 最坏：O(n²)

冒泡排序

时间复杂度：

• 最好：O(n)
• 最坏：O(n²)
• 平均：O(n²)

归并排序

分治思想，先分，对半分，直到分为两两一组，然后开始治，每两个合并，四个合并，八个合并等等
时间复杂度：
一趟是O(n)，要进行log₂n趟，因此是：O(nlog₂n)

选择排序

O(n²)

快速排序

快速排序就是如下

解释下快排的过程

先选择一个基数，然后先从右往左找到第一个比基数小的数，从左往右找到一个比基数大的数，交换两者，然后继续找，直到左右相遇，这个相遇的地方和基数交换，此时一轮排序完成。
然后以现在的基数位置分割左右两部分，递归分别排序

快排的空间复杂度

平均复杂度O(nlogn)，最坏情况O(n²)

堆排序

利用堆这种数据结构进行排序，属于选择排序的一种，最好最坏的时间复杂度都是O(nlogn)，是不稳定排序。
是一个完全二叉树

• 大顶堆：每个节点值大于等于左右孩子节点
• 小顶堆：每个节点值小于等于左右孩子节点

大顶堆

两步

1. 构造初始堆，按照大顶堆的思想变成大顶堆
2. 然后将堆顶的元素与末尾元素交换，使得末尾元素最大，然后调整一下结构，使其符合定义，比如需要满足堆顶大于子节点
3. 然后继续将堆顶元素和末尾元素交换，以此类推

树

前缀和、差分数组

前缀和
前缀和就比如说是这种题型，计算一个序列的和，如第i-j项的和。
d[i]表示前i项，即[0,i-1]的和，求[i,j]的和只需要d[j+1]-d[i]就可以得到了
创建一个n+1的数组，然后i=i-1就行

preSum = new int[nums.length + 1];
        // 计算 nums 的累加和
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
1
2
3
4
5

差分数组
当频繁对数组的数据需要进行修改的时候，就不好用前缀和了，需要使用差分数组
差分数组里，d[i]=num[i]-num[i-1]，表示当前数和前一个数的差值

int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i - 1];
}
1
2
3
4
5
6

第一个数树原始数组的数，可以根据差值反推出原数组。diff[i]表示当前res[i]和前一个数res[i-1]的差值

int res=new int[diff.length];
res[0]=diff[0];
for (int i=1;i<diff.length;i++){
    res[i]=res[i-1]+diss[i];
}
1
2
3
4
5

这样的话，如果想给[i,j]加上3，只需要d[i]+=3，d[j+1]-=3

哈希

哈希是一种键值的数据结构。
生成哈希的方法有

• 数字分析法：均匀取几位
• 平方取中法：平方扩大范围，再取几个数
• 分段叠加法：分成几段，然后舍去或者选择几段进行叠加，移位法和折叠法。
• 除留余数法：用表长除关键字

哈希冲突

如果有多个关键词的哈希值重复了，就叫哈希冲突。
冲突的解决主要有两种：开放地址法和链地址法

• 开放地址法：如果冲突了，就通过序列重新计算哈希
• • 线性探查：分别+1，2，3…检查是否冲突
• • 二次探查：+1方，-1方，2方，-2方等等，然后计算哈希
• • 伪随机：加一个随机数
• 链地址法：通过链表进行连接，如果发生冲突了，就添加在对应位置的链表尾部
• 构造多个哈希函数，彼此不冲突
• 在设置一个溢出表，冲突的都放进去

一致性哈希

一致性哈希算法原理
普通分布式集群的话不能较好地处理请求与服务器之间的映射关系，某个请求由固定服务器处理，无法负载均衡。可能会存在有的太忙有的太闲，如果有宕机了，可能还会导致无法处理请求。
在分布式中用的比较多，解决了简单哈希算法在分布式哈希表( Distributed Hash Table，DHT) 中存在的动态伸缩等问题。利用哈希算法对请求和服务器进行动态映射，可以应对节点宕机的情况，会通过算法将请求重新分配到可用机器上。
这里以一个分布式memcached服务器集群为例。

1. 首先先初始化一个0~2³²-1的圆环，按照顺时针组织空间
2. 计算出所有服务器的哈希值，保存在圆环的对应位置上
3. 对需要存储的数据或者请求进行哈希运算，得到一个哈希值，映射在圆上
4. 在圆环上进行顺序查找，碰到的第一个服务器负责存取数据或者处理请求

如果此时添加一个节点，受影响的只有从这个节点逆时针方向到第一个节点中间的哈希值数据请求

算法

一百个数放在一起，每次抽取基数位，最后剩下几

找规律其实，可以用10或者20模拟，然后会发现最后剩下的数是包含因数2最多的数

一百个灯，第一次编号为1的倍数的拨动开关，第二次编号为2的倍数的拨动开关，第三次编号为3的倍数的拨动开关…第100次编号为100的倍数的波动开关，最后亮着的是谁

感觉还是个找规律的题，每次

最短路径

Floyd算法和迪杰斯特拉算法
Floyd：
解决给定的加权图中顶点间的最短路径的一种算法。
给定一个二维数组map[][]保存从节点 i 到节点 j 的最短路径。
从 i 到 j 有中间可以经过数个额外节点
对于每个节点k，如果map[i][j]>map[i][k]+map[k][j]，那么map[i][j]=map[i][k]+map[k][j]。意思就是说如果i和j经过k节点的路径最短，那么更新这个最短路径，以此类推
时间复杂度：O(n³)，空间复杂度：O(n²)

迪杰斯特拉：
用于计算一个节点到其他节点的最短距离，采用了广度优先遍历的思想，在使用前需要指定一个起始点。

大数据

1亿QQ号，1G内存，在最快的时间内判断一个QQ号是否存在

用位图？
一个int4个字节，32位。先QQ/32找到在数组的某个数，然后对32取余，找到某个比特位，

有100G数据，内存4G，如何排序？（或者内存很小只有1.5MB）

可以采用桶排序。
分别把数据放在文件中，然后依次读取文件。

找出1G的文件中高频词

有一个 1GB 大小的文件，文件里每一行是一个词，每个词的大小不超过 16B，内存大小限制是 1MB，要求返回频数最高的 100 个词(Top 100)

内存有限无法全部读取到内存中，分治，把文件分割成若干个1M的小文件。
遍历大文件执行hash(x)%5000，分成5000个文件，如果均匀的话应该每个文件200kB，否则就继续细分。对每个小文件，使用哈希表统计词频，

网站日志中记录了用户的IP，找出访问次数最多的IP

一个IP地址32位，大概4G，不能全部加载到内存里，分治
取哈希，hash(x)%1024，存储到1024个文件里，每个文件大概4M个IP地址
然后用哈希表求每个文件里的IP次数，再取每个文件里的第一高频，就只需要比较1024个数。

其余

25匹马选最快的3匹，每组只能跑5匹，需要跑多少次

同样的题目：这里有64匹马，八个跑道，几次找到最快的四匹马。
设ABCDE
先来五次：每组分别跑一次，得到每组的组内顺序，去掉每组的最后两名，留下A1,A2,A3…E1,E2,E3
再来第六次：取每组第一名跑一次，A1,B1,C1,D1,E1，假设结果就是这个顺序，则可以去掉D和E组的所有，以及C3,C2,B3。留下A1,A2,A3,B1,B2,C1
第七次：此时已知A1最快了，只需要比较剩下五匹，找出最快的两个，就分别是2，3名了

代码算法

dfs

python版本和java版本

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> result=new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        boolean[] dp=new boolean[num.length];
        dfs(num,0,dp,new ArrayList<Integer>());
        return result;
    }
    void dfs(int[] num,int index,boolean[] dp,ArrayList<Integer> res){
        if (num.length==index){
            result.add(new ArrayList(res));
            return;
        }
        for (int i=0;i<num.length;i++){
            if (!dp[i]){
                dp[i]=true;
                res.add(num[i]);
                dfs(num,index+1,dp,res);
                res.remove(res.size()-1);
                dp[i]=false;
            }
        }
    }
}
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

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        # write code here
        self.result=[]
        dp=[False] * len(num)
        self.dfs(num,0,dp,len(num),[])
        return self.result
    def dfs(self,num,index,dp,length,res):
        if index==length:
            temp=copy.copy(res)
            self.result.append(temp)
            return 
        for i in range(length):
            if not dp[i]:
                dp[i]=True
                res.append(num[i])
                self.dfs(num,index+1,dp,length,res)
                res.pop()
                dp[i]=False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

快速排序

def quickSort(List,left,right):
    if left<right:
        left_index=left
        right_index=right
        mid=List[left_index]
        while (left_index<right_index):
            while (left_index<right_index and List[right_index]>=mid):
                right_index-=1
            if left_index<right_index:
                List[left_index]=List[right_index]
            while (left_index<right_index and List[left_index]<=mid):
                left_index+=1
            if left_index<right_index:
                List[right_index]=List[left_index]
        List[left_index]=mid
        quickSort(List,left,left_index-1)
        quickSort(List,left_index+1,right)
List=[5,4,3,2,1]
quickSort(List,0,len(List)-1)
print(List)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

归并排序

def mergeSort(List,left,right):
    if left==right:
        return
    mid=int((left+right)/2)
    mergeSort(List,left,mid)
    mergeSort(List,mid+1,right)
    merge(List,left,mid,right)
def merge(List,left,mid,right):
    temp=[]
    i=0
    left_index=left
    right_index=mid+1
    while left_index<=mid and right_index<=right:
        if List[left_index]<=List[right_index]:
            temp.append(List[left_index])
            left_index+=1
        else:
            temp.append(List[right_index])
            right_index+=1
    while left_index<=mid:
        temp.append(List[left_index])
        left_index+=1
    while right_index<=right:
        temp.append(List[right_index])
        right_index+=1
    i=0
    while left<=right:
        List[left]=temp[i]
        left+=1
        i+=1

List=[5,4,3,2,1]
mergeSort(List,0,len(List)-1)
print(List)
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

回文子串

动态规划和中心扩散，中心扩散就是从0开始遍历，然后以此向左向右找和中心值一样的，然后判断左是否等于右，如果是，则是回文记录，如果不是，则不是

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        dp=[[False]*n]*n
        for i in range(n):
            dp[i][i]=True
        start=0
        max_len=0
        for length in range(2,n+1):
            for left in range(n):
                right=left+length-1
                if right>=n:
                    break
                if s[right]!=s[left]:
                    dp[left][right]=False
                else:
                    if right-left<=2:
                        dp[left][right]=True
                    else:
                        dp[left][right]=dp[left+1][right-1]
                if dp[left][right] and length>max_len:
                    max_len=length
                    start=left
        return s[start:start+max_len]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

数据库

主要来源
《面试必备知识》——数据库129问

架构

主要有以下几个部分

• 连接器：身份认证和权限，连接用的
• 查询缓存：查询数据的时候会先查询缓存（8.0以后移除了）。以k-v的形式缓存在内存中，但是其实不建议用缓存，如果经常跟更新的话，每更新一次就要把缓存清空
• 分析器：缓存没有命中的话就会分析SQL语句，检查语法是否正确。分为词法分析（提取关键词、表名和字段等）和语法分析（校验SQL合法性）。
• 优化器：按照MySQL觉得的进行优化
• 执行器：进行语句的执行

执行过程
对于插入语句

• 先检查是否具有权限，如果有权限，会先查询缓存，如果这个语句作为key在缓存中，直接使用缓存，没有就下一步
• 通过分析其进行词法分析提取出关键元素，进行判断语法是否有问题
• 优化器确定优化方案
• 权限校验，如果有权限就会调用数据库引擎接口返回结果

更新语句

• 查询数据，如果有缓存也会用缓存
• 拿到数据以后修改字段，调用引擎API写入数据，InnoDB将数据保存在内存中，记录redo log，redo log进入prepare状态，高速执行器执行完成可以提交了
• 执行器收到以后记录binlog，提交redo log

关系型数据库和非关系型数据库

关系型

使用数学的关机模型来描述实体间的关系。
优点：

• 便于理解，非常贴合现实世界
• 使用方便，sql语句就可以
• 维护较好，支持事务，ACID属性保证完整性

缺点：

• 海量数据读写性能较差
• 不好扩展，无法通过增加节点数等提高并发性能吞吐量

非关系型数据库

主要指非关系型的、分布式的而且一般不需要满足ACID原则的，如mongoDB、redis等。
主要分为键值存储数据库（redis）、列存储数据库（应对分布式海量数据，仍然有key指向多个列）、文档型数据库（半结构化的数据如json之类的）、图形数据库
缺点是约束较少，只能存储一些简单数据。

三大范式

其实也就是数据库设计建表的原则
第一范式：要求每一列数据都是原子不可分的
比如如果一个字段叫家庭信息，存储了几口人和住在哪，这就可以把他分开为两个字段，违背了第一范式
第二范式：属性值必须完全依赖于主键
确保每一列都和主键相关，而不能和主键部分相关（对于联合主键，要和所有主键相关）
比如对于一个订单表，有订单号和产品号个主键，同时有产品数量、名称、订单价格和订单时间。数量和名称就是依赖于两个主键的，但是订单时间和金额这个字段只和订单号有关，而和产品号这个主键没关系，所以不符合这个原则。
需要将时间和金额拆分成另一个表
第三范式：所有的非主属性不依赖于其他的非主属性
每一列数据都需要和主键直接相关，而不能间接相关
比如学生表里，学号是主键，还有老师性别和年龄字段，这个就和学号不直接相关，违背了。

索引

数据库维护着某些满足特定算法查找的数据结构，能够以某些方式指向数据，利用这个数据结构进行高级查找，就是索引。
数据库联合索引

索引分类

• B树：平衡多叉线索树，是m叉，比线索二叉树快很多
• B+树：合上一个的区别在于B+树只在叶子节点存储数据，而B树则是每个节点即存放索引又存放数据。
• 哈希：要精确匹配所有的列才能查询，引擎通过索引创建一个哈希，键是哈希值，值是指想数据行的指针。MEMORY就采用这种，非常快速高效，处理冲突使用链地址法。

建立索引的原则

使用索引可以提高数据库的检索速度。
如何建立索引
适合：

• 选择性高、重复率低的数据
• 频繁出现在where 中的字段
• 多表联合查询作为关键对象的列

不适合：

• 频繁需要修改更新的字段
• 一张表不要太多索引

索引类型

主要类型有如下几种：

• 普通索引：就是普通索引
• 唯一索引：索引列必须唯一，但是可以空
• 全文索引：用来查找文本中的关键词，而不是直接匹配索引的值。比如说like关键词
• 组合索引：多个字段用于索引，只有使用创建索引的第一个字段，才会被使用索引，遵循最左前缀集合
• 主键索引：每个表只有一个主键，索引必须唯一，主键不得为空

索引的优缺点

优点：

• 索引列可以保证唯一，生成唯一的id
• 可以有效缩短数据查询时间
• 可以加快表之间的连接
• 如果字段用于排序，可以加速相应过程

缺点：

• 建立维护索引需要时间成本，随着数据量的增大成本增加
• 需要空间成本，每一条索引都要占据一定的物理存储空间，数据量越大，占据的物理空间越多
• 会降低表的增删改查的速度，因为每次修改都需要动态维护索引信息

最左前缀原则

在联合索引中，如果SQL语句用到了联合索引的最左边，那么就可以用联合索引进行匹配。
比如某表有索引(a,b,c)，基本只有匹配上才能匹配索引。

但是碰到><between like会停止匹配。
比如对于select * from t where a=1 and b>1 and c =1; 这样a,b可以用到（a,b,c），c索引用不到，因为b>1这里停止了不匹配
但是如下可以匹配到，因为优化器会进行优化，改变一下顺序，就可以匹配a,b,c了

select * from t where a=1 and c=1 and b=1;
//优化为
select * from t where a=1 and b=1 and c=1;
1
2
3

不走索引的情况

对于like，百分号%在左不走索引，在右走索引，即A可以索引，B不可以。

A:select * from student where 'name' like '王%'
B:select * from student where 'name' like '%小'
1
2

对于索引进行计算不走索引
B给age+8了做运算，所以走不了索引

A:select * from student where age = 10+8
B:select * from student where age + 8 = 18
1
2

对索引使用函数不走索引
A对索引列用了函数，不走索引

A:select * from student where  concat('name','哈') ='王哈哈';
B:select * from student where name = concat('王哈','哈');
1
2

最后不等号也不走索引

唯一索引和主键索引的区别

唯一索引和主键索引都要求是唯一。
一张表可以有多个唯一索引，但是一般只有一个，而且允许为空。
主键是一个特殊的唯一索引，一张表最多一个主键索引，可以没有，值不得为空。

聚集索引和非聚集索引有什么区别？

数据结构都是B+树
聚集索引
数据行的物理顺序和列值（一般是主键的列）的逻辑顺序相同，一个表只能有一个聚集索引。
比如id在前面的数据实际存放的内存地址空间也靠前。
叶子节点存放着所有的数据。
速度上会更有优势。

非聚集索引
数据行的物理顺序和列值的逻辑顺序不同，一个表可以有多个非聚集索引。

其实吧，聚集索引好像对应的是二级索引。
聚集索引的叶子节点存放的是数据的值，二级索引的叶子节点存放的是主键

count()

在进行统计的时候，server会维护一个count变量，指定参数不为NULL的话，就＋1.
count()=count(1)>count(主键)>count(字段)
比如count()

select count(*) from t_dept;
1

如果是*相当于参数为0，所以和1是一样的。
在遍历的时候不会去比较任何一个字段的值，因为参数是1，不是字段，所以只要有一条数据就会＋1.不需要获取数据的值，所以比主键遍历会快一点
对于字段进行遍历的时候，如果没有二级索引，就会默认去使用主键索引，如果有就有二级索引。因为二级索引其实比主键索引更矮胖IO次数更少。

对于count(字段)，是最慢的。
因为它会进行全盘扫描
为什么要通过遍历的方式呢，如果是MyISAM引擎，每个表会有meta元属性，维护一个变量eow_count，直接读取就可以了，复杂度O(1)。
InnoDB的话，因为事务的存在，结果可能不准确所以得遍历

二分查找、二分查找树、自平衡二叉树（AVL树）、B树、B+树

二分查找
使用数组存储索引的话，通过每次对比mid，如果小于就去左半边继续找，大于就去右边继续找，以此类推。
时间复杂度会降为O(log n)，但是每次需要额外计算一次中间节点
二分查找树
二分查找时间复杂度可以，但是如果插入数据的话，就比较麻烦，需要把它后面的数据依次移动一位。如果数据储存在硬盘上，这个移动时间会非常慢，相比于内存可能慢几万几十万倍。
因此就需要一个非线性的天然适合二分查找的结构，基于上面的二分查找，把所有的中间节点从中间依次向两边提起来，构建一棵树。
特点就是，节点左子树的所有值都小于该节点，右子树所有节点的值都大于当前节点值，比较好的解决了插入数据的性能问题。


但是当每次插入的时候都是最大的元素的时候，就会退化为一个链表，查找效率降为O(n)。

因为树是存储在磁盘中，每个节点的查询都需要进行一次磁盘IO操作，树越深，IO操作数越多，查询时间就越慢。
而且不利于范围查找，只能精确查找，也不适合。
自平衡二叉树（AVL树）
AVL在二叉查找树的基础上，添加了一个约束条件，要求左右子树的高度差不能超过1.这样查询的复杂度一直会维持O(log n)。在每次插入数据的时候都会修改相应的节点去满足这个条件。
但是不管什么二叉树，插入的数据越多都会导致树越深，那就会查询速度很慢，当改为三叉树或者m叉树，显然一定程度上会降低深度，减少搜索次数。
B树
因此提出了B树，B树实质上是一个M叉树。但是B树每个节点都需要保存索引信息和数据，而用户记录数据的大小可能远超过索引数据，需要更多IO操作来读取到有用的索引数据。
而且比如我们搜索到最后一层找到需要的数据，但是上面几层节点的数据也被加载到内存里了，而我们只需要他们的索引即可，这样就会浪费时间和内存资源。进行范围查询的时候需要使用中序遍历，也很慢。
B+树
因此提出了B+树

• B+树只有在叶子节点才会储存数据信息，其他的中间节点只会存储索引信息。
• 所有索引都会在叶子直接点出现，叶子节点构成有序链表，有前后指引

B树和B+树
B树查找波动较大，因为可能有的数据在第一个节点就找到了，可能有的数据需要找到叶子节点才会找到，而B+树只有找到叶子节点才能找到数据。
对于相同的数据量来说，因为B+树的中间节点只保存索引信息，所以可以存储更多的叶子节点数据，同时也会更加矮胖，查找的IO次数就越少
B+树删除数据的时候，直接删除对应的叶子节点就好了。B树删除的话可能会导致树的结构发生比较大的变化
查询的话，都是从根节点进行查找，但是B+树还有一个链表的特性，叶子节点通过双向链表连接起来，对数据的查询非常有帮助，比如如果需要找到在这个数据的下一个或者后几个数据，直接从叶子节点往后遍历即可，不需要重新从根节点遍历

MyISAM引擎的B+树叶子节点存放的是用户指针（数据的物理地址），指向实际的数据
InnoDB则指向的是具体的数据值

索引的底层实现、B+树，为什么用b+

B树：平衡多路查找树，由平衡二叉树演化而来。
B+树由B树优化而来。
B+树特点：

• 每个节点的键是有序的
• m阶B+树出度最大为m，m取决于硬盘的页的大小
• 非叶子节点储存键值信息：主键和子节点的指针信息
• 数据记录在叶子节点中
• 每个节点都占用存储结构的一个页

B树和B+树相比：

• B+中间节点不保存数据，所以页能容纳更多元素
• B+查找必须找到叶子节点，查询更稳定，B树不需要，只要匹配到即可
• B+支持随机索引和顺序检索，B只支持随机
• B+空间利用率高，减少磁盘IO

索引的实现为什么用B+不用哈希，为什么不用红黑树

用B+不用哈希

• 哈希是将索引字段映射成对应哈希值，然后储存在对应位置，模糊查找的话不行，但是B+树可以，使用最左前缀原则可以快速找到对应数据。
• 索引字段如果都哈希的话，可能会有多个字段冲突，然后会形成一个较长的链表，查找会比较复杂。
• 范围查找的话，比如找id在100-400中不能使用哈希，只能遍历B+树。
• 哈希作为索引的时候，需要将整个哈希表装入内存，然后依次读取，如果是B+树，只需要将每个节点装入内存即可，不需要消耗较大内存。
  不用红黑树
  当大规模数据的时候，红黑树过深，查询效率低，硬盘读写IP频繁，性能过滤。
  B+提高读写效率

为什么使用自增主键所谓索引

自增自动增加，保证了顺序，不需要移动相关叶子节点等，提高性能。

唯一索引和普通索引的区别

读
唯一索引在读取到数据后直接返回结果
而普通索引在读取之后需要继续完后判断是否存在相同的索引，这里如果索引结构是B+树的话，只需要往后移动一位即可判断是否有相同的索引，因此性能差异不大
写
唯一索引需要先判断是否有重复值，需要先随机访问到数据页，没有插入缓冲，性能较差
普通索引可以使用插入缓冲，几个操作一起执行，一起对数据页进行修改

主键索引和普通索引

主键索引会创建一个聚集索引，叶子节点保存的是数据的值
普通索引的叶子节点则保存的是字段的主键。
在使用普通索引进行查询的时候，其实需要搜索两个B+树，先通过普通索引的叶子节点找到对应的主键值，然后利用这个主键值，在聚集索引中进行查找，找到叶子节点中的数据值。
以上的步骤叫<font color="red>回表。
如何避免回表
尽量使用聚集索引查询
通过索引覆盖的形式。将这个字段添加到联合索引里面，或者说把这个字段也弄成索引

InnoDB常见的索引结构

• B+：
• 全文索引：
• 哈希索引：把索引的值进行哈希运算得到一个哈希值，放在哈希表里，但是一般是MEMORY引擎才会这么做，性能比B树好；哈希不能模糊查询，如果有大量相同的哈希会造成性能下降，也就是冲突了

MySQL有哪些存储引擎？除了innodb 还用过其他引擎吗(提了myisam和内存索引)

存储引擎分为MyISAM、InnoDB和MEMORY。
InnoDB（聚集索引）、MyISAM（非聚集索引）
其中有这个几个主要的

• MyISAM：不支持事务和外键，访问速度快。对事务完整性没有要求、主要是访问读物数据、并发小而且数据修改较少，可以使用这个
• InnoDB：支持事务，具有回滚等功能，需要更多的磁盘空间和内存占用。如果需要频繁进行更新删除等操作，业务需要事务机制、高并发等、以及需要较高的一致性（如银行转账），用这个
• MEMORY：用内存来存储数据，访问速度快，安全性不保证。因此适用于数据量小访问速度快的场景

视图

本质上是一个虚拟表，行列数据来自于其他基本表，在引用视图的时候动态生成。
使得使用者只能看到视图所定义的数据，看不到基本表中的所有数据，提高了安全性，比如员工工资保密，不应该给其他人看的。
特点：

• 视图是由基本表产生的(虚)表 ，可以来自不同表
• 视图来自多个基本表的时候，不允许添加和删除数据
• 对视图的更新（添加删除修改）直接影响基本表

事务

数据库的事务（ACID）

在一个用户修改数据的时候，可能会有其他用户也进行相关操作，为了保证数据从一个一致性状态顺利转为另一个一致性状态，引入事务的概念。一个事务其实就是包含了对数据库操作的一个序列，要不然全部执行，要不然都不执行。
事物具有四个特点ACID：

1. 原子性：事务中的所有操作都是原子的，只有两个结果，一个是不执行，另一个是执行完成
2. 一致性：十五完成后，必须使得数据从一种一致性状态转为另一种一致性状态
3. 隔离性：一个事务中的操作修改必须和其他事务相互隔离，不能访问到其他事务修改中的数据，只能是修改前或修改后的数据，通过锁机制保证
4. 持久性：使得事务执行的结果可以永久性地保留下来，重启或者宕机也不会丢失

不处理隔离会出现什么情况

会出现如下三种情况：

1. 脏读：脏读就是一个事务读取了另一个事务修改但是没有提交的数据。如果那个事务回滚了没有保存提交，那么就会出现错误。
2. 不可重复读：当多次执行某个查询语句时，发现数据被修改或者删除了，导致两次查询结果不一致
3. 幻读：同一个事务中执行多次操作，但是由于其他事务的插入操作导致读取的结果不一致。如已经执行删除，但是另一个事务又插入，读取到了本该不存在的数据，产生了幻觉

数据库事务的隔离级别

定义了四种隔离级别。

1. 未提交读：是最低级的一种隔离，每个事务可以看到其他事务所做的任何修改，不做隔离；
2. 已提交读：每个事务只能看到其他事务提交过的数据，还没有提交的不会被访问到，这是大多种数据库的默认隔离级别，没有提交的修改都是不可见的；
3. 可重复读：保证一个事务中每次读取的数据都是一致的。可能会造成幻读，是InnoDB的默认级别。
4. 可串行化：所有事务串行化，每次只执行一个事务，不会造成冲突，安全性最高，效率不高

多版本并发控制可以解决不可重复读，间隙锁解决幻读。

锁

锁粒度分为行锁和表锁，表锁管理开销小，允许并发量夜宵写入数据的时候把整个表锁起来，行锁支持大并发。

• 表锁：针对非索引字段上锁，对整个表加锁，实现简单开销小，粒度大，并发度很低的，不会死锁
• 行锁：粒度最小，只对操作的记录上锁，是针对索引字段加的锁，并发度高，开销也大速度慢，可能会死锁

MyISAM和MEMORY只支持表锁
InnoDB支持表锁和行锁
InnoDB行锁针对索引字段，如果update或者delete的where里面索引用不成，就会变成表锁了。

悲观锁

在操作数据之前先执行加锁。行锁，表锁，读锁，写锁等，都是在做操作之前先上锁，悲观锁的实现往往依靠数据库本身的锁功能实现。
开启事务后，所有增删改查都会给对应的数据行加锁（这是基于索引的，如果没有索引，上表锁）
InnoDB引擎下使用多版本并发控制mvcc实现并发，不会上锁。
在mysql里面悲观锁的调用要加上for update
如select * from db_stock where goods_id = 1 for update
事务在执行着一条语句的时候，就会给这条记录加一个锁，直到执行完成以后，会释放锁。在这个过程中，如果其他事务正常读取数据，不会有影响，但是如果有类似for update的命令，那么这个事务需要在当前事务修改完以后执行这条语句。
悲观锁可以有效保证事务的顺序性和一致性，但是对于高并发的场景并不适用，再给一套数据加锁以后，其他事务只能进行查询操作；而且如果加锁时间过长，其他事务等待的时间也很长。

乐观锁

因此引入乐观。
对数据进行操作前，总是认为最好情况，认为不会有其他事务修改数据，因此不上锁。而是在修改完数据后进行判断数据是否被需改过，如果和预期的结果一致则正常更新。
可以使用版本号机制和CAS机制实现。
CAS
是一种无锁的思想，所有线程对数据库的访问操作都是没有限制的，如果存在冲突的话，使用一种CAS（比较交换）的技术鉴别线程冲突，如果检测到冲突，就重试直到没有冲突。
它包含了三个参数位V（读写的内存位置）、A（旧的预期值）、B（新的值）
机制是在执行语句以后，只有当V的值等于A的值的时候，才会修改为B的值。
如果发现V不等于A就会一直循环。
缺点是：

• 如果数据一直没有改回来，会一直循环，对CPU造成一些负担
• 会导致ABA问题，V一开始是A，在过程中被修改为B然后又被改成A，就会认为没有发生修改，然后会将新的B值赋给这个A。问题来了，虽然同样是A，但是在实际应用的时候，值相等不一定完全一致，可能会出错。可以使用时间戳后者版本号解决这个问题。

适用于读多写少的场景。

版本号机制
版本号机制就是说，加一个字段叫版本号，每次读取数据的时候，还会记录下对应版本号，更新的时候对比版本号，如果一致的话说明数据没有被更改，然后修改数据，版本号+1。如果版本号不一致，重新进行查询操作

共享锁和排他锁

还有两种锁

• 共享锁（S）：又叫读锁，事务读取记录的时候可以获得这个锁，然后允许多个事务同时获得。select … LOCL IN SHARE LOCK
• 排他锁（X）：又叫写锁和独占锁，事务在修改记录的时候获得排他锁，不允许其他事务获得这个锁。当一个记录被加上排他锁以后，不能够再加其他的任何锁。SELECT … UPDATE
  当需要上表锁的时候，如何判断记录是否已经有行锁呢，使用意向锁进行判断。
• 意向共享锁（IS）：事务有意向对表中的数据加共享锁，枷锁之前需要先获得这个表的IS锁
• 意向排他锁（IX）：事务有意向给表中的记录加排他锁（X），加排他锁之前需要先获得IX锁

意向锁是不能手动添加的，是引擎自己维护的，加排他锁和共享锁之前，InnoDB会获取该数据行所在的数据表对应的意向锁。

日志

比较重要的日志主要有三个，binlog、redo log和undo log

redo log

重做日志
是InnoDB特有的日志，使得MySQL有崩溃恢复的能力，如果数据库挂了，InnoDB会使用redo log恢复数据，保证持久性和完整性
数据库中的数据都是页为单位的，查询一条记录以后，会从硬盘上读取出相应的页，加载的数据叫做数据页，放在Buffer pool里面，之后就会从pool里面加载，不会再去重新读取硬盘，减少IO降低开销。
在更新表的时候如果Pool里面有存在的数据，就会将数据在这里面更新。然后将这个修改写在重做日志缓存中，之后刷新到redo log里面。
刷盘时机
有一个参数用来控制刷新数据的机制。

• 设置为0：事务提交的时候不进行刷盘
• 1：事务提交的时候进行刷盘。事务提交就会有记录在硬盘，不会丢失
• 2：事务提交的时候只把重做缓存中的内容写入到page缓存。mysql挂了没事，但是宕机会损失一秒的数据

还有个单独的线程，每隔一秒就会把redo log buffer写入到page cache然后调用fsunc刷盘。就是每隔一秒刷新一下。这样
日志文件组
一般都是几个文件在一起组成变成一个日志文件组，比如四个1G文件组成一个4G的。
是一个环形数组，一个写满以后写入下一个文件。
使用write pos和checkpoint属性，分别记录当前位置和擦除位置。
每次redo写入文件，write pos后移。恢复数据时候会清空redo记录，把checkpoint后移。
两者中间的空闲部分可以用来记录数据，当write追上checkpoint时，表示满了，需要清空数据再写入

binlog

归档日志。
是一个逻辑日志，记录语句的原始逻辑，比如”给ID为2的数据行C字段加1“，属于MySQL Server层。
不管什么引擎发生表更新就会产生binlog日志。
数据备份、主备主主和主从都少不了binlog日志，需要使用binlog同步保证一致性。
有三种格式，statement、row和mixed

• statement记录了原始的sql语句，但是如果里面有类似于now()这种时间函数，在执行的时候会导致数据不一致
• 因此使用row包含具体的数据行数据，需要使用专门的工具解析出来。相当于记住每行每个字段都是什么。但是很占空间，而且同步和恢复很慢，影响速度
• 因此提出了mixed，会自行判断是否会导致不一致的情况出现，如果不会就用statement，会的话就用row

写入机制
事务执行中，先写入到binlog cache，然后提交以后写入到binlog文件里。
一样有三种刷盘日志

• 0：提交事务不刷新，由系统判断什么时候fsync
• 1：每次提交事务的时候都进行刷盘写入操作
• 2：可以设置一次提交N个事务，当宕机后，会丢失N个事务的数据

两阶段提交

redo保证了崩溃恢复，binlog保证了数据一致性
redo log在事务的过程中可以一直写入，binlog则只有提交的时候才可以写入
有一个场景：update一个数据，c是0，更新成1。然后执行完redo，bin写入错误会发生什么。
bin里面没有相应的数据记录，在恢复的时候就没有这个，c就是0，而redo里面c是1，会出现冲突了。
解决这个问题redo log拆成两个部分，prepare和commit。
大致过程：

• 事务执行期间写入到prepare
• 提交事务的时候分为两步，先写入binlog，然后再commit redo log（commit的时候就会检测prepare和binlog是否一致）

当恢复日志的时候发现redo处于prepare的时候，如果没有对应的binlog就会回滚事务。
当commit出问题的时候出问题了，不会影响，因为binlog能找到相应记录，直接用binlog了。

undo log

所有事务的修改都会记录在undo log里面。出现问题回滚的时候按照undo log的信息把数据回复即可，而且是持久化保存的，宕机也没事

数据类型

CHAR(x)
是固定长度的字符串，读取速度快，因为是固定长度，如果值长度小于x，则空格填充。空间换时间，最长255
VARCHAR(x)
是可变长度的字符串，存取慢，不消耗多余空间，时间换空间，最长65532
如果指定x，则最长长度为x，x越大排序就越消耗内存。
INT(x)
显示字符的宽度，仍然使用4字节存储，只不过显示的长度为x
不易设置为NULL，建议NOT NULL
因为NULL在数据库中占用的内存空间更大，需要更多字节保存

执行一条语句的过程

1. 应用于数据库服务器建立连接
2. 数据库进程得到sql语句
3. 先检查缓存有没有，有就直接返回
4. 解析sql语句是否合法
5. 读取数据到内存进行逻辑处理
6. 通过链接返回给客户端
7. 关闭连接释放资源

redis

Redis面试题 最新最强

redis为什么快？除了他是内存型数据库外，还有什么原因