2023-05-17 22:15 杭州电子科技大学测试开发

关注

积累

Linux

进程与线程的区别

1.定义

进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，它是系统进行资源分配和调度的一个独立单位。例如，用户运行自己的程序，系统就创建一个进程，并为它分配资源，包括各种表格、内存空间、磁盘空间、I/O设备等，然后该进程被放入到进程的就绪队列，进程调度程序选中它，为它分配CPU及其他相关资源，该进程就被运行起来。

线程是进程的一个实体，是CPU调度和分配的基本单位，线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器、一组寄存器和栈），但是它可以与同属一个进程的其他的线程共享进程所拥有的全部资源。

在没有实现线程的操作系统中，进程既是资源分配的基本单位，又是调度的基本单位，它是系统中并发执行的单元。而在实现了线程的操作系统中，进程是资源分配的基本单位，而线程是调度的基本单位，是系统中并发执行的单元。

2.关系

一个线程可以创建和撤销另一个线程;同一个进程中的多个线程之间可以并发执行.相对进程而言，线程是一个更加接近于执行体的概念，它可以与同进程中的其他线程共享数据，但拥有自己的栈空间，拥有独立的执行序列。

3.区别

进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

1) 简而言之,一个程序至少有一个进程,一个进程至少有一个线程.

2) 线程的划分尺度小于进程，使得多线程程序的并发性高。

3) 另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。

4) 线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。

5) 从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。

线程的

Contents

Linux 1

进程与线程的区别 1

线程的 2

生命周期，线程有哪些状态 2

什么是线程死锁 2

形成死锁的四个必要条件是什么 2

如何避免线程死锁 3

什么是线程安全？如何保证线程安全？ 3

Mysql 4

SQL模糊查询的四种匹配模式 4

1、% 4

2、_ 4

3、[ ] 5

4、[^ ] 5

数据库索引原理 5

概述 5

常见的索引类型 5

哈希表 6

有序数组 7

搜索树 7

InnoDB 的索引模型 9

MySQL中的内连接、左连接、右连接、全连接、交叉连接 10

数据库事务的四大特性以及事务的隔离级别 16

网络 19

TCP相比UDP为什么是可靠的 19

TCP 与 UDP 的区别 20

在浏览器输入url后发生了什么 21

POST和GET请求的区别小结 21

Python 22

列表和元组的区别 22

list 22

tuple 22

find 与 findall 的区别 23

参数*和**的区别 24

Python 垃圾回收 24

软件测试 27

流程体系介绍 27

递归和循环 28

数据结构 28

二叉树的实际应用 28

排序 29

堆排序基本思想 29

生命周期，线程有哪些状态

线程通常分为五种状态：创建，就绪，运行，阻塞，死亡。

阻塞又分为三种：

　　等待阻塞：运行的线程执行wait方法，该线程会释放占用的所有资源，JVM会把线程放入等待池中，进入这个状态后，是不能自动唤醒的，必须依靠其他线程调用notify或notifyAll方法才能唤醒，wait是Object类的方法。

　　同步阻塞：运行的线程在获取对象的同步锁时，若该同步锁被别的线程占用，则JVM会把线程放入锁池中。

　　其他阻塞：运行的线程执行sleep或join方法，或者发出了I/O请求时，JVM会把该线程置为阻塞状态。当sleep状态超时，join等待线程终止或超时，或者I/O请求处理完毕，线程重新转入就绪状态。sleep时Thread类的方法。

1.新建状态：新创建一个线程对象

2.就绪状态：线程对象创建后，其他线程调用了该对象的start方法，该状态的线程位于可运行线程池中，变得可运行，等待获取cpu的使用权。

3.运行状态：就绪状态的线程获取了cpu，执行程序代码。

4.阻塞状态：阻塞状态时线程因为某种原因放弃cpu使用权，暂时停止运行，直到线程进入就绪状态，才有机会转到运行状态。

5.死亡状态：线程执行完了或者因异常退出了run方法，该线程结束生命周期。

什么是线程死锁

死锁是指两个或两个以上的进程（线程）在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程（线程）称为死锁进程（线程）。

多个线程同时被阻塞，它们中的一个或者全部都在等待某个资源被释放。由于线程被无限期地阻塞，因此程序不可能正常终止。

如下图所示，线程 A 持有资源 2，线程 B 持有资源 1，他们同时都想申请对方的资源，所以这两个线程就会互相等待而进入死锁状态。

形成死锁的四个必要条件是什么

（1）互斥条件：线程(进程)对于所分配到的资源具有排它性，即一个资源只能被一个线程(进程)占用，直到被该线程(进程)释放

（2）请求与保持条件：一个线程(进程)因请求被占用资源而发生阻塞时，对已获得的资源保持不放。

（3）不剥夺条件：线程(进程)已获得的资源在末使用完之前不能被其他线程强行剥夺，只有自己使用完毕后才释放资源。

（4）循环等待条件：当发生死锁时，所等待的线程(进程)必定会形成一个环路（类似于死循环），造成永久阻塞

如何避免线程死锁

我们只要破坏产生死锁的四个条件中的其中一个就可以了。

破坏互斥条件

这个条件我们没有办法破坏，因为我们用锁本来就是想让他们互斥的（临界资源需要互斥访问）。

破坏请求与保持条件

一次性申请所有的资源。

破坏不剥夺条件

占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源。

破坏循环等待条件

靠按序申请资源来预防。按某一顺序申请资源，释放资源则反序释放。破坏循环等待条件。

我们对线程 2 的代码修改成下面这样就不会产生死锁了。

什么是线程安全？如何保证线程安全？

线程安全：

线程安全就是多线程访问时，采用了加锁机制，当一个线程访问该类的某个数据时，进行保护，其他线程不能进行访问直到该线程读取完，其他线程才可使用。不会出现数据不一致或者数据污染。线程不安全就是不提供数据访问保护，有可能出现多个线程先后更改数据造成所得到的数据是脏数据。

如何保证呢：

1、使用线程安全的类；

2、使用synchronized同步代码块，或者用Lock锁；

> 由于线程安全问题，使用synchronized同步代码块

原理：当两个并发线程访问同一个对象object中的这个synchronized(this)同步代码块时，一个时间内只能有一个线程得到执行。

另一个线程必须等待当前线程执行完这个代码块以后才能执行该代码块。

3、多线程并发情况下，线程共享的变量改为方法局部级变量；

Mysql

SQL模糊查询的四种匹配模式

关于条件，SQL提供了四种匹配模式：

1、%

表示任意0个或多个字符，可匹配任意类型和长度的字符。有些情况下是中文，需用两个百分号（%%）表示：

SELECT * FROM [user] WHERE u_name LIKE ‘%三%’

复制

将会把 u_name 为“张三”、“张猫三”、“三脚猫”、“唐三藏”等有“三”的记录全找出来

另外，如果须要找出 u_name 中既有“三”又有“猫”的记录，请运用 and 条件

SELECT * FROM [user] WHERE u_name LIKE ‘%三%’ AND u_name LIKE ‘%猫%’

复制

如果运用：

SELECT * FROM [user] WHERE u_name LIKE ‘%三%猫%’

复制

虽然能搜索出“三脚猫”，但不能搜索出符合条件的“张猫三”

2、_

表示任意单个字符。匹配单个任意字符，它常用来限定表达式的字符长度语句：

SELECT * FROM [user] WHERE u_name LIKE ‘三’

复制

只找出“唐三藏”这样 u_name 为三个字且中间一个字是“三”的；

再比如

SELECT * FROM [user] WHERE u_name LIKE ‘三__’；

复制

只找出“三脚猫”这样 name 为三个字且第一个字是“三”的；

3、[ ]

表示括号内所列字符中的一个（类似正则表达式）。指定一个字符、字符串或范围，要求所匹配对象为它们中的任一个：

SELECT * FROM [user] WHERE u_name LIKE ‘[张李王]三’

复制

将找出“张三”、“李三”、“王三”（而非“张李王三”）；

如 [ ] 内有一系列字符（01234、abcde之类的）则可略写为“0-4”、“a-e”

SELECT * FROM [user] WHERE u_name LIKE ‘老[1-9]’

复制

将找出“老1”、“老2”、……、“老9”；

4、[^ ]

表示不在括号所列之内的单个字符。其取值和 [] 相同，但它要求所匹配对象为指定字符以外的任一个字符：

SELECT * FROM [user] WHERE u_name LIKE ‘[^张李王]三’

复制

将找出不姓“张”、“李”、“王”的“赵三”、“孙三”等；

SELECT * FROM [user] WHERE u_name LIKE ‘老[^1-4]’;

复制

将排除“老1”到“老4”，寻找“老5”、“老6”、……

数据库索引原理

概述

在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。一句话简单来说，索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。

常见的索引类型

索引的出现是为了提高查询效率，但是实现索引的方式却有很多种，所以这里也就引入了索引模型的概念。可以用于提高读写效率的数据结构很多，这里主要讲三种常见、也比较简单的数据结构：哈希表、有序数组和搜索树。

哈希表

哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的值即 key，就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。

不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。假设，你现在维护着一个身份证信息和姓名的表，需要根据身份证号查找对应的名字，这时对应的哈希索引的示意图如下所示：

图中，User2 和 User4 根据身份证号算出来的值都是 N，但没关系，后面还跟了一个链表。假设，这时候你要查 ID_card_n2 对应的名字是什么，处理步骤就是：首先，将ID_card_n2 通过哈希函数算出 N；然后，按顺序遍历，找到 User2。

需要注意的是，图中四个 ID_card_n 的值并不是递增的，这样做的好处是增加新的 User时速度会很快，只需要往后追加。但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。

你可以设想下，如果你现在要找身份证号在 [ID_card_X, ID_card_Y] 这个区间的所有用户，就必须全部扫描一遍了。

所以，哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些NoSQL 引擎。

有序数组

而有序数组在等值查询和范围查询场景中的性能就都非常优秀。还是上面这个根据身份证号查名字的例子，如果我们使用有序数组来实现的话，示意图如下所示：

这里我们假设身份证号没有重复，这个数组就是按照身份证号递增的顺序保存的。这时候如果你要查 ID_card_n2 对应的名字，用二分法就可以快速得到，这个时间复杂度是O(log(N))。

同时很显然，这个索引结构支持范围查询。你要查身份证号在 [ID_card_X, ID_card_Y] 区间的 User，可以先用二分法找到 ID_card_X（如果不存在 ID_card_X，就找到大于ID_card_X 的第一个 User），然后向右遍历，直到查到第一个大于 ID_card_Y 的身份证号，退出循环。

如果仅仅看查询效率，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。

所以，有序数组索引只适用于静态存储引擎，比如你要保存的是 2017 年某个城市的所有人口信息，这类不会再修改的数据。

搜索树

二叉搜索树也是课本里的经典数据结构了。还是上面根据身份证号查名字的例子，如果我们用二叉搜索树来实现的话，示意图如下所示：

二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF ->User2 这个路径得到。这个时间复杂度是 O(log(N))。

当然为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。

树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。

你可以想象一下一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的。

为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N 叉”树。这里，“N 叉”树中的“N”取决于数据块的大小。

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。

InnoDB 的索引模型

在 MySQL 中，索引是在存储引擎层实现的，所以并没有统一的索引标准，即不同存储引擎的索引的工作方式并不一样。而即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。由于 InnoDB 存储引擎在 MySQL 数据库中使用最为广泛，所以下面我就以 InnoDB 为例，和你分析一下其中的索引模型。

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。又因为前面我们提到的，InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+树中的。

每一个索引在 InnoDB 里面对应一棵 B+ 树。

假设，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。

这个表的建表语句是：

mysql> create table T(

id int primary key,

k int not null,

name varchar(16),

index (k))engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下。

从图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。

主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。

非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

根据上面的索引结构说明，我们来讨论一个问题：基于主键索引和普通索引的查询有什么区别？

如果语句是 select * from T where ID=500

，即主键查询方式，则只需要搜索 ID 这棵B+ 树；如果语句是 select * from T where k=5

，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。

也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询

MySQL中的内连接、左连接、右连接、全连接、交叉连接

创建两个表（a_table、b_table），两个表的关联字段分别为：a_table.a_id和b_table.b_id

CREATE TABLE a_table (

a_id int NOT NULL,

a_name varchar(10) DEFAULT NULL,

a_part varchar(10) DEFAULT NULL

);

CREATE TABLE b_table (

b_id int(11) DEFAULT NULL,

b_name varchar(10) DEFAULT NULL,

b_part varchar(10) DEFAULT NULL

) ENGINE=InnoDB DEFAULT CHARSET=utf8

分别向两个表中插入数据：

a_table:　　　　　　　　　　　　　　　　b_table:

一、内连接

说明：组合两个表中的记录，返回关联字段相符的记录，即：两个表的交集（阴影）部分。

关键字：inner join on

SQL语句：

select * from a_table a inner join b_table b on a.a_id = b.b_id;

执行结果：

二、左连接（左外连接）

说明：左连接全称是左外连接，是外连接中的一种。

左表(a_table)的记录将会全部表示出来，而右表(b_table)只会显示符合搜索条件的记录，右表记录不符合搜索条件的地方均为NULL。

关键字：left join on / left outer join on（left join 是left outer join的简写）

SQL语句：

select * from a_table a left join b_table b on a.a_id = b.b_id;

select * from a_table a left outer join b_table b on a.a_id = b.b_id;

执行结果：

---------------------------------------------------

当两个表的记录行数不同时，以左表为准。

例：

a_table有四条记录：　　　　　　　　　　　　b_table有五条记录：

SQL语句：

select * from a_table as a left join b_table as b on a.a_id = b.b_id;

执行结果：

三、右连接（右外连接）

说明：右连接的全称是右外连接，是外连接中的一种。

与左连接相反，右连接中，右表(b_table)的记录将会全部表示出来，左表(a_table)只会显示符合搜索条件的记录，记录不符合搜索条件的地方均为NULL。

关键字：right join on / right outer join on（right join是right outer join的简写）

SQL语句：

select * from a_table a right join b_table b on a.a_id = b.b_id;

select * from a_table a right outer join b_table b on a.a_id = b.b_id;

执行结果：

---------------------------------------------------

当两个表的记录行数不同时，以右表为准。

例：

a_table有四条记录：　　　　　　　　　　　　b_table有五条记录：

SQL语句：

select * from a_table as a right join b_table as b on a.a_id = b.b_id;

执行结果：

四、全连接（全外连接）

说明：返回左右表的所有行。哪个表中没有的就用null填充。

关键字：MySQL不支持全外连接，所以只能采取关键字UNION来联合左、右连接

SQL语句：

select * from a_table as a left join b_table as b on a.a_id = b.b_id

UNION

select * from a_table as a right join b_table as b on a.a_id = b.b_id;

执行结果：

五、交叉连接

说明：没有where条件的交叉连接中，产生连接表就是笛卡尔积。将两个表的所有行进行组合，连接后的行数为两个表的行数的乘积数。

关键字：cross join

1. SQL语句：

select * from a_table cross join b_table;

#等价于：select * from a_table, b_table;

执行结果：

2. SQL语句

select * from a_table as a cross join b_table as b on a.a_id = b.b_id;

执行结果：

数据库事务的四大特性以及事务的隔离级别

事务：是指是程序中一系列严密的逻辑操作，而且所有操作必须全部成功完成，否则在每个操作中所作的所有更改都会被撤消

如果一个数据库声称支持事务的操作，那么该数据库必须要具备以下四个特性：

⑴ 原子性（Atomicity）

　　原子性是指事务包含的所有操作要么全部成功，要么全部失败回滚，这和前面两篇博客介绍事务的功能是一样的概念，因此事务的操作如果成功就必须要完全应用到数据库，如果操作失败则不能对数据库有任何影响。

⑵ 一致性（Consistency）

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

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

⑶ 隔离性（Isolation）

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

　　即要达到这么一种效果：对于任意两个并发的事务T1和T2，在事务T1看来，T2要么在T1开始之前就已经结束，要么在T1结束之后才开始，这样每个事务都感觉不到有其他事务在并发地执行。

　　关于事务的隔离性数据库提供了多种隔离级别，稍后会介绍到。

⑷ 持久性（Durability）

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

　　例如我们在使用JDBC操作数据库时，在提交事务方法后，提示用户事务操作完成，当我们程序执行完成直到看到提示后，就可以认定事务以及正确提交，即使这时候数据库出现了问题，也必须要将我们的事务完全执行完成，否则就会造成我们看到提示事务处理完毕，但是数据库因为故障而没有执行事务的重大错误。

　　以上介绍完事务的四大特性(简称ACID)，现在重点来说明下事务的隔离性，当多个线程都开启事务操作数据库中的数据时，数据库系统要能进行隔离操作，以保证各个线程获取数据的准确性，在介绍数据库提供的各种隔离级别之前，我们先看看如果不考虑事务的隔离性，会发生的几种问题：

1，脏读

　　脏读是指在一个事务处理过程里读取了另一个未提交的事务中的数据。

　　当一个事务正在多次修改某个数据，而在这个事务中这多次的修改都还未提交，这时一个并发的事务来访问该数据，就会造成两个事务得到的数据不一致。例如：用户A向用户B转账100元，对应SQL命令如下

update account set money=money+100 where name=’B’; (此时A通知B)

update account set money=money - 100 where name=’A’;

　　当只执行第一条SQL时，A通知B查看账户，B发现确实钱已到账（此时即发生了脏读），而之后无论第二条SQL是否执行，只要该事务不提交，则所有操作都将回滚，那么当B以后再次查看账户时就会发现钱其实并没有转。

2，不可重复读

　　不可重复读是指在对于数据库中的某个数据，一个事务范围内多次查询却返回了不同的数据值，这是由于在查询间隔，被另一个事务修改并提交了。

　　例如事务T1在读取某一数据，而事务T2立马修改了这个数据并且提交事务给数据库，事务T1再次读取该数据就得到了不同的结果，发送了不可重复读。

　　不可重复读和脏读的区别是，脏读是某一事务读取了另一个事务未提交的脏数据，而不可重复读则是读取了前一事务提交的数据。

　　在某些情况下，不可重复读并不是问题，比如我们多次查询某个数据当然以最后查询得到的结果为主。但在另一些情况下就有可能发生问题，例如对于同一个数据A和B依次查询就可能不同，A和B就可能打起来了……

3，虚读(幻读)

　　幻读是事务非独立执行时发生的一种现象。例如事务T1对一个表中所有的行的某个数据项做了从“1”修改为“2”的操作，这时事务T2又对这个表中插入了一行数据项，而这个数据项的数值还是为“1”并且提交给数据库。而操作事务T1的用户如果再查看刚刚修改的数据，会发现还有一行没有修改，其实这行是从事务T2中添加的，就好像产生幻觉一样，这就是发生了幻读。

　　幻读和不可重复读都是读取了另一条已经提交的事务（这点就脏读不同），所不同的是不可重复读查询的都是同一个数据项，而幻读针对的是一批数据整体（比如数据的个数）。

　　现在来看看MySQL数据库为我们提供的四种隔离级别：

　　① Serializable (串行化)：可避免脏读、不可重复读、幻读的发生。

　　② Repeatable read (可重复读)：可避免脏读、不可重复读的发生。

　　③ Read committed (读已提交)：可避免脏读的发生。

　　④ Read uncommitted (读未提交)：最低级别，任何情况都无法保证。

　　以上四种隔离级别最高的是Serializable级别，最低的是Read uncommitted级别，当然级别越高，执行效率就越低。像Serializable这样的级别，就是以锁表的方式(类似于Java多线程中的锁)使得其他的线程只能在锁外等待，所以平时选用何种隔离级别应该根据实际情况。在MySQL数据库中默认的隔离级别为Repeatable read (可重复读)。

　　在MySQL数据库中，支持上面四种隔离级别，默认的为Repeatable read (可重复读)；而在Oracle数据库中，只支持Serializable (串行化)级别和Read committed (读已提交)这两种级别，其中默认的为Read committed级别。

乐观锁和悲观锁

数据库的乐观锁和悲观锁是什么？怎么实现的？

数据库管理系统（DBMS）中的并发控制的任务是确保在多个事务同时存取数据库中同一数据时不破坏事务的隔离性和统一性以及数据库的统一性。乐观并发控制（乐观锁）和悲观并发控制（悲观锁）是并发控制主要采用的技术手段。

悲观锁：假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作。在查询完数据的时候就把事务锁起来，直到提交事务。实现方式：使用数据库中的锁机制

乐观锁：假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。在修改数据的时候把事务锁起来，通过version的方式来进行锁定。实现方式：一般会使用版本号机制或CAS算法实现。

两种锁的使用场景

从上面对两种锁的介绍，我们知道两种锁各有优缺点，不可认为一种好于另一种，像乐观锁适用于写比较少的情况下（多读场景），即冲突真的很少发生的时候，这样可以省去了锁的开销，加大了系统的整个吞吐量。

但如果是多写的情况，一般会经常产生冲突，这就会导致上层应用会不断的进行retry，这样反倒是降低了性能，所以一般多写的场景下用悲观锁就比较合适。

视图

为什么要使用视图？什么是视图？

为了提高复杂SQL语句的复用性和表操作的安全性，MySQL数据库管理系统提供了视图特性。所谓视图，本质上是一种虚拟表，在物理上是不存在的，其内容与真实的表相似，包含一系列带有名称的列和行数据。但是，视图并不在数据库中以储存的数据值形式存在。行和列数据来自定义视图的查询所引用基本表，并且在具体引用视图时动态生成。

视图使开发者只关心感兴趣的某些特定数据和所负责的特定任务，只能看到视图中所定义的数据，而不是视图所引用表中的数据，从而提高了数据库中数据的安全性。

视图有哪些特点？

视图的特点如下:

1视图的列可以来自不同的表，是表的抽象和在逻辑意义上建立的新关系。

2视图是由基本表(实表)产生的表(虚表)。

3视图的建立和删除不影响基本表。

4对视图内容的更新(添加，删除和修改)直接影响基本表。

5当视图来自多个基本表时，不允许添加和删除数据。

视图的使用场景有哪些？

视图根本用途：简化sql查询，提高开发效率。如果说还有另外一个用途那就是兼容老的表结构。

下面是视图的常见使用场景：

1重用SQL语句

2简化复杂的SQL操作。在编写查询后，可以方便的重用它而不必知道它的基本查询细节；

3使用表的组成部分而不是整个表；

4保护数据。可以给用户授予表的特定部分的访问权限而不是整个表的访问权限；

5更改数据格式和表示。视图可返回与底层表的表示和格式不同的数据。

视图的优点

1查询简单化。视图能简化用户的操作

2数据安全性。视图使用户能以多种角度看待同一数据，能够对机密数据提供安全保护

3逻辑数据独立性。视图对重构数据库提供了一定程度的逻辑独立性

视图的缺点

性能。数据库必须把视图的查询转化成对基本表的查询，如果这个视图是由一个复杂的多表查询所定义，那么，即使是视图的一个简单查询，数据库也把它变成一个复杂的结合体，需要花费一定的时间。

修改限制。当用户试图修改视图的某些行时，数据库必须把它转化为对基本表的某些行的修改。事实上，当从视图中插入或者删除时，情况也是这样。对于简单视图来说，这是很方便的，但是，对于比较复杂的视图，可能是不可修改的

这些视图有如下特征：1.有UNIQUE等集合操作符的视图。2.有GROUP BY子句的视图。3.有诸如AVG\SUM\MAX等聚合函数的视图。 4.使用DISTINCT关键字的视图。5.连接表的视图（其中有些例外）

SQL 约束有哪几种？

1. NOT NULL: 用于控制字段的内容一定不能为空（NULL）。

2. UNIQUE: 控件字段内容不能重复，一个表允许有多个 Unique 约束。

3. PRIMARY KEY: 也是用于控件字段内容不能重复，但它在一个表只允许出现一个。

4. FOREIGN KEY: 用于预防破坏表之间连接的动作，也能防止非法数据插入外键列，因为它必须是它指向的那个表中的值之一。

5. CHECK: 用于控制字段的值范围。

SQL的生命周期？

1应用服务器与数据库服务器建立一个连接

2数据库进程拿到请求sql

3解析并生成执行计划，执行

4读取数据到内存并进行逻辑处理

5通过步骤一的连接，发送结果到客户端

6关掉连接，释放资源

网络

TCP相比UDP为什么是可靠的

提供了以下四种机制：

[1] 确认和重传机制

建立连接时三次握手同步双方的“序列号 + 确认号 + 窗口大小信息”，是确认重传、流控的基础

传输过程中，如果Checksum校验失败、丢包或延时，发送端重传

[2] 数据排序

TCP有专门的序列号SN字段，可提供数据re-order

[3] 流量控制

窗口和计时器的使用。TCP窗口中会指明双方能够发送接收的最大数据量

[4] 拥塞控制

TCP的拥塞控制由4个核心算法组成。

“慢启动”（Slow Start）

“拥塞避免”（Congestion avoidance）

“快速重传 ”（Fast Retransmit）

“快速恢复”（Fast Recovery）

TCP 与 UDP 的区别

1. TCP 是面向连接的协议，UDP 是无连接协议

TCP 发送数据前使用三次握手建立连接，UDP 发送数据前不需要建立连接。

2. TCP 可靠，UDP 不可靠

TCP 丢包会自动重传，UDP 不会(任何必需的可靠性必须由应用层来提供)。 TCP 可靠性由三个机制保证：1. 序号（TCP 报文的序号）2. 确认（ACK 机制）3. 重传（超时或者冗余的 ACK）

3. TCP 有序，UDP 无序

消息在传输过程中可能会乱序，后发送的消息可能会先到达，TCP 会对其进行重新排序，UDP 不会。

4.TCP 无界，UDP 有界

TCP 通过字节流传输，UDP 中每一个包都是单独的。

5. TCP 有流量控制（拥塞控制），UDP 没有

TCP 协议的流量控制是基于滑窗协议实现的。拥塞控制和流量控制不同，流量控制是点对点的通信量抑制，抑制发送端发送速率，使得接收端来得及接收。

6. TCP 传输慢，UDP 传输快；

因为 TCP 需要建立连接、保证可靠性和有序性，所以比较耗时。这就是为什么视频流、广播电视、在线多媒体游戏等选择使用 UDP。

7. TCP 是重量级的，UDP 是轻量级的

TCP 要建立连接、保证可靠性和有序性，就会传输更多的信息，如 TCP 的包头比较大。

8. TCP 的头部比 UDP 大

总结：

• TCP 是面向连接的、可靠的、有序的、速度慢的协议；UDP 是无连接的、不可靠的、无序的、速度快的协议。

• TCP 开销比 UDP 大，TCP 头部需要 20 字节，UDP 头部只要 8 个字节。

• TCP 无界有拥塞控制，UDP 有界无拥塞控制。

TCP UDP

连接性面向连接无连接

可靠性可靠不可靠

有序性有序无序

有界性有界无界

拥塞控制有无

传输速度慢快

量级重量级轻量级

头部大小大小

在浏览器输入url后发生了什么

一个页面从输入 URL 到页面加载显示完成，这个过程中都发生了什么？

主要包括以下几个基本步骤：

浏览器的地址栏输入URL并按下回车。

浏览器查找当前URL是否存在缓存，并比较缓存是否过期（强缓存判断）。

DNS解析URL对应的IP。

根据IP建立TCP连接（三次握手）。

HTTP发起请求。

服务器处理请求，浏览器接收HTTP响应。

渲染页面，构建DOM树，CSS计算，最后生成布局树(Layout Tree)

关闭TCP连接（四次挥手）。

POST和GET请求的区别小结

请求参数：GET请求参数是通过URL传递的，多个参数以&连接，POST请求放在request body中。

请求缓存：GET请求会被缓存，而POST请求不会，除非手动设置。

收藏为书签：GET请求支持，POST请求不支持。

安全性：POST比GET安全，GET请求在浏览器回退时是无害的，而POST会再次请求。

历史记录：GET请求参数会被完整保留在浏览历史记录里，而POST中的参数不会被保留。

编码方式：GET请求只能进行url编码，而POST支持多种编码方式。

对参数的数据类型：GET只接受ASCII字符，而POST没有限制。

HTTP 和 HTTPS 的区别

一、HTTP 和 HTTPS 的基本概念

HTTP：超文本传输协议（HTTP，HyperText Transfer Protocol）是互联网上应用最为广泛的一种网络协议。设计 HTTP 最初的目的是为了提供一种发布和接收 HTML 页面的方法。它可以使浏览器更加高效。HTTP 协议是以明文方式发送信息的，如果黑客截取了 Web 浏览器和服务器之间的传输报文，就可以直接获得其中的信息。

HTTPS：是以安全为目标的 HTTP 通道，是 HTTP 的安全版。HTTPS 的安全基础是 SSL。SSL 协议位于 TCP/IP 协议与各种应用层协议之间，为数据通讯提供安全支持。SSL 协议可分为两层：SSL 记录协议（SSL Record Protocol），它建立在可靠的传输协议（如TCP）之上，为高层协议提供数据封装、压缩、加密等基本功能的支持。SSL 握手协议（SSL Handshake Protocol），它建立在 SSL 记录协议之上，用于在实际的数据传输开始前，通讯双方进行身份认证、协商加密算法、交换加密密钥等。

二、HTTP 与 HTTPS 的区别

1、HTTPS 协议需要到 CA （Certificate Authority，证书颁发机构）申请证书，一般免费证书较少，因而需要一定费用。(以前的网易官网是http，而网易邮箱是 https 。)

2、HTTP 是超文本传输协议，信息是明文传输，HTTPS 则是具有安全性的 SSL 加密传输协议。

3、HTTP 和 HTTPS 使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。

4、HTTP 的连接很简单，是无状态的。HTTPS 协议是由 SSL+HTTP 协议构建的可进行加密传输、身份认证的网络协议，比 HTTP 协议安全。(无状态的意思是其数据包的发送、传输和接收都是相互独立的。无连接的意思是指通信双方都不长久的维持对方的任何信息。)

两台主机通信的过程

主机A和主机B通信报文的转发过程

1、主机A和主机B在同一网段中

主机A查看自己的ARP缓存，检查是否有主机B的IP到MAC的映射，如果有映射，构造报文，目的IP为主机B的IP，源IP为主机A的IP，目的MAC为主机B的MAC，源MAC为主机A的MAC，将报文发送给交换机C，交换机C进行MAC地址表学习，将主机A的MAC和报文入端口号记录下来，然后交换机C查看自己的MAC转发表，检查是否有主机B的MAC到端口的映射，如果有映射，获取对应的端口，将报文从此端口转发出去，报文到达主机B。如果交换机C没有主机B的MAC转发表映射，采用洪泛的形式广播报文，主机B收到报文后向主机A回复，交换机C进行MAC表学习，将主机B的MAC和报文入端口号记录下来。

如果主机A没有主机B的ARP映射，主机A需要发送ARP请求，以获取主机B的MAC，将报文发往交换机C，交换机C采用洪泛的形式广播报文，主机B收到广播报文后，在自己的ARP缓存表中写入主机A的IP到MAC的映射，将自己的MAC封装到ARP回复报文中，单播给主机A，主机A获取到主机B的MAC后，在自己的ARP缓存表中写入主机B的IP到MAC的映射，构造报文发送给主机B，过程同上。

主机B向主机A回复报文的过程类似。

2、主机A和主机B不在同一个网络中

主机 A 会首先检查目的IP地址是否与自己在同一网段，如果在，就直接广播ARP请求来获取目的主机的MAC地址，如果不在同一网段，又配置有网关地址的话，那么主机 A 就通过 ARP 请求，询问192.168.0.1（网关）在哪里，网关收到后就会回应主机 A ，把网关的MAC地址告诉主机 A ，当获取到网关的MAC地址后，把网关的MAC地址作为MAC帧中的目的MAC地址，然后就把数据丢给网关 192.168.0.1 ，网关根据路由表，转发给下一个路由器，再由下一个路由器交付给主机 D 所在的网络，即网关，网关再通过ARP，找到目的主机 D ，完成数据交付。

主机A查看自己的ARP缓存表，检查是否有路由器E的IP到MAC的映射，如果有映射，获取路由器E的MAC，构造报文，目的IP为主机B的IP，源IP为主机A的IP，目的MAC为路由器E的MAC，源MAC为主机A的MAC，将报文通过交换机C发往路由器E，过程同上。如果主机A没有路由器E的IP到MAC的映射，需要发送ARP请求，获取路由器E的MAC，过程同上。路由器E收到主机A的报文后，剥离报文的MAC帧头，查询路由表，发现目标主机B所在的网络是直连的，查看自己的ARP缓存表，如果有主机B的IP到MAC的映射关系，获取主机B的MAC，封装报文MAC帧头，目的MAC为主机B的MAC，源MAC为路由器E的MAC，将报文通过交换机D发往主机B，如果路由器E没有主机B的IP到MAC的映射关系，需要发送ARP请求，获取主机B的MAC，过程同上。

主机B向主机A回复报文的过程类似。

注：路由器上的路由表一般是配置静态路由或者通过路由协议自动学习的。

目的主机接收到数据帧的操作：

当目的主机接收到数据帧后对比目的MAC，如是发送给自己的，则拆去数据帧头，发往网络层，网络层对比目的IP，如相同则拆包发往传输层，传输层再对比目的端口，确认相同则拆去数据段交给应用程进行数据组装。

Python

列表和元组的区别

list和tuple是Python内置的有序集合，一个可变，一个不可变。

list

list是一种有序的集合，可以随时添加和删除其中的元素，是一个可变的有序表

当索引超出了范围时，Python会报一个IndexError错误，所以，要确保索引不要越界，记得最后一个元素的索引是len(classmates) – 1。

tuple

另一种有序列表叫元组：tuple。tuple和list非常类似，但是tuple一旦初始化就不能修改，比如同样是列出同学的名字：

现在，classmates这个tuple不能变了，它也没有append()，insert()这样的方法。

不可变的tuple有什么意义？因为tuple不可变，所以代码更安全。如果可能，能用tuple代替list就尽量用tuple。

tuple的陷阱：当你定义一个tuple时，在定义的时候，tuple的元素就必须被确定下来

这个tuple定义的时候有3个元素，分别是'a'，'b'和一个list。不是说tuple一旦定义后就不可变了吗？怎么后来又变了？

别急，我们先看看定义的时候tuple包含的3个元素：

当我们把list的元素'A'和'B'修改为'X'和'Y'后，tuple变为：

表面上看，tuple的元素确实变了，但其实变的不是tuple的元素，而是list的元素。tuple一开始指向的list并没有改成别的list，所以，tuple所谓的“不变”是说，tuple的每个元素，指向永远不变。即指向'a'，就不能改成指向'b'，指向一个list，就不能改成指向其他对象，但指向的这个list本身是可变的！

find 与 findall 的区别

find 检测sub是否包含在字符串中，若有则返回索引值，否则返回-1

findall re模块的基于正则表达式，返回string中所有与pattern相匹配的全部字串，返回形式为数组

参数*和**的区别

单星号（*）：*agrs，将所以参数以元组(tuple)的形式导入：

双星号（**）：**kwargs，将参数以字典的形式导入

Python 垃圾回收

和C，C++不同Python这种高级语言，对内存的管理，分配和释放有独特的机制，即对于小对象(<=512bytes)使用内存池模型进行管理，即当对象被回收时，不会将内存归还给操作系统，而是将内存归还给对应的内存池中，对于大对象(>512bytes)则使用标准C allocator的方式进行内存的分配和管理

垃圾回收算法

标准CPython实现的垃圾收集器有两部分组件构成，一部分为引用计数模块(reference counting collector), 另一部分为分代垃圾回收器(generational garbage collector)。

引用计数(reference counting)

引用计数算法是最简单的垃圾回收算法即对象当没有引用指向时，会被回收(deallocated).

在Python中每一个对象，甚至是int都有一个引用(pointer)指向该对象，为了保持对每个对象引用的跟踪，Python对象额外维护了一个reference count的变量来自增或自减，用来标识当前对象是在copy复制或者被delete删除。

对Python对象进行如下操作可以导致该对象的引用计数自增

赋值操作 assignment operator

函数传参 argument passing

将对象放到列表中 appending an object to a list

当对象的引用计数变量变为0时，CPython将会自动的调用该对象特定的回收方法object-specific deallocation function。

获取对象的引用计数可以通过sys.getrefcount方法

foo = []

# 2 references, 1 from the foo var and 1 from getrefcount

print(sys.getrefcount(foo))

def bar(a):

# 4 references

# from the foo var, function argument, getrefcount and Python's function stack

print(sys.getrefcount(a))

bar(foo)

# 2 references, the function scope is destroyed

print(sys.getrefcount(foo))

标记清除(Mark and Sweep)

标记清除算法主要有两段操作构成，即标记(Mark),清除(Sweep)。

标记：即从根节点出发检测所有不可达的节点对象，通常是DFS的遍历。如下是伪代码。root即为根节点，markedBit为获取和修改当前节点的标记位。

清除：顾名思义，就是清除标记中不可达的节点。通常就是遍历所有堆内存的对象并将未被标记的节点进行回收。伪代码如下：

优缺点：

标记清除算法的优点在于可以解决循环引用的问题，并且在整个算法执行的过程中没有额外的开销。

标记清除算法的最主要缺点在于正常的程序将会被阻塞，当执行标记清除时。另外一个缺点在于，标记清除算法在执行很多次数，在程序的堆空间会产生一些小的内存碎片, 如下图所示。

分代回收(Generational garbage collector)

当经典的引用计数无法处理循环引用问题时，即出现下图所示场景时，出现循环引用，或者自引用，分代回收的算法就登场了。分代回收算法是基于标记清除(Mark and Sweep).

如下代码即展示了分代垃圾回收的机制：

 gc.disable() : 手动关闭分代垃圾回收

 当注释掉，手动运行gc的代码部分时，gc.collect()打印1, 1。即循环引用计数。

 去掉注释，手动执行gc.collect()时，打印0，0.

import gc

# We are using ctypes to access our unreachable objects by memory address.

class PyObject(ctypes.Structure):

_fields_ = [("refcnt", ctypes.c_long)]

gc.disable() # Disable generational gc

lst = []

lst.append(lst)

# Store address of the list

lst_address = id(lst)

# Destroy the lst reference

del lst

object_1 = {}

object_2 = {}

object_1['obj2'] = object_2

object_2['obj1'] = object_1

obj_address = id(object_1)

# Destroy references

del object_1, object_2

# Uncomment if you want to manually run garbage collection process

# gc.collect()

# Check the reference count

print(PyObject.from_address(obj_address).refcnt)

print(PyObject.from_address(lst_address).refcnt)

与经典的引用计数不同的是，引用计数是实时工作的，而分代垃圾回收是定期工作的。

首先GC分类器将对象分成3个不同代，每个新创建的对象属于第一代。每当对象在某代的的垃圾回收中存活下来时，则将该对象移动至下一代。较低的代会更加频繁的进行垃圾回收，(大部分对象在被创建后很快就会消亡)。分代垃圾回收提高了GC的性能，并降低了GC暂停时间。

为了决定在什么时候去执行分代垃圾回收，每一代都有各自独立的counter和threshold，counter为分配内存的对象数量减去上一次分代垃圾回收的数量。每次创建一个新的对象时，counter++，CPython就会检查counter是否达到了阈值，如果达到了阈值，则进行该代的垃圾回收。

软件测试

流程体系介绍

1. 需求分析，需求评审（RPD、产品原型图）

2. 制定测试计划、评审测试计划、优化测试计划（产品项目计划，人员安排、任务安排）

3. 制定测试方案（测试需求点分析，测试模块划分，流程图分析，制定测试规程）

4. 编写测试用例、评审测试用例、优化测试用用例（功能测试用例、脚本测试用例）

5. 执行测试用例、提交缺陷信息、编写阶段性测试报告（缺陷记录、缺陷管理流程）

6. 进行回归测试（跟踪bug修改情况，执行回归测试用例集、进行探索性测试、编写回归测试测试报告）

7. 测试执行阶段结束根据缺陷记录、阶段性报告编写测试总结报告

8. 进行验收测试，出验收测试报告（测试验收、测试评估与建议）

9. 测试归档（归类、存档测试过程中涉及的文档）

10. 产品上线后跟踪与维护（收集用户反馈问题）

测试的了解

①　测试流程

l 需求评审（需求是否合理、是否可测）

l 测试计划（进度计划、资源（人力、测试环境配置、测试工具等））

l 测试设计（形成测试用例）

l 测试执行

l BUG提交、跟踪、管理

l 回归测试

l 测试报告输出

②　测试类型

a. 按照项目流程阶段：单元测试、集成测试、系统测试、确认测试，验收测试；

b. 按照代码的可见程度划分：黑盒测试、白盒测试、灰盒测试；

c. 按照是否投入大量的人力：手工测试、自动化测试；

d. 还有冒烟测试、回归测试、随机测试等

e. 同时。从系统整体的角度考虑，可分为：功能测试、性能测试、兼容性测试、安全测试、易用性测试、可靠性测试、配置测试、UI测试、文档类测试等

③　测试方法

黑盒测试：等价类划分、边界值分析、错误推测、因果图、决策表、正交分析、场景法；

白盒测试：语句覆盖、条件覆盖、判定覆盖、判定条件覆盖、条件组合覆盖、路径覆盖；

④　测试工具

接口测试工具：postman、jmeter

性能测试工具：jmeter、loadrunner等

递归和循环

递归好处：代码更简洁清晰。一般来说，一个人可能很容易的写出前中后序的二叉树遍历的递归算法，要写出相应的非递归算法就比较考验水平了，恐怕至少一半的人搞不定。所以说递归代码更简洁明了。

递归坏处：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。

一般尾递归（即最后一句话进行递归）和单向递归（函数中只有一个递归调用地方）都可以用循环来避免递归，更复杂的情况则要引入栈来进行压栈出栈来改造成非递归，这个栈不一定要严格引入栈数据结构，只需要有这样的思路，用数组什么的就可以。

循环方法比递归方法快, 因为循环避免了一系列函数调用和返回中所涉及到的参数传递和返回值的额外开销。

递归和循环之间的选择。一般情况下, 当循环方法比较容易找到时, 你应该避免使用递归。这在问题可以按照一个递推关系式来描述时, 是时常遇到的, 比如阶乘问题就是这种情况。反过来, 当很难建立一个循环方法时, 递归就是很好的方法。

数据结构

二叉树的实际应用

哈夫曼编码，来源于哈夫曼树（给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为赫夫曼树(Huffman tree)。即带权路径长度最短的树），在数据压缩上有重要应用，提高了传输的有效性。

海量数据并发查询，二叉树复杂度是O(K+LgN)。二叉排序树就既有链表的好处，也有数组的好处，在处理大批量的动态的数据是比较有用。

C++ STL中的set/multiset、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。查找最大（最小）的k个数，红黑树，红黑树中查找/删除/插入，都只需要O(logk)。

B-Tree，B+-Tree在文件系统中的目录应用。

路由器中的路由搜索引擎。

完全二叉树和满二叉树

完全二叉树(Complete Binary Tree)

　　若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

满二叉树(Full Binary Tree)：

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上。

叶子结点

一棵树当中没有子结点（即度为0）的结点称为叶子结点

常见的map，线程安全的map

HashMap线程安全的吗？

Java中平时用的最多的Map集合就是HashMap了，它是线程不安全的。

看下面两个场景：

1、当用在方法内的局部变量时，局部变量属于当前线程级别的变量，其他线程访问不了，所以这时也不存在线程安全不安全的问题了。

2、当用在单例对象成员变量的时候呢？这时候多个线程过来访问的就是同一个HashMap了，对同个HashMap操作这时候就存在线程安全的问题了。

线程安全的Map

为了避免出现场景2的线程安全的问题，不能使用HashMap作为成员变量，要寻求使用线程安全的Map，下面来总结下有哪些线程安全的Map呢？

1、HashTable

private Map<String, Object> map = new Hashtable<>();

HashTable的get/put方法都被synchronized关键字修饰，说明它们是方法级别阻塞的，它们占用共享资源锁，所以导致同时只能一个线程操作get或者put，而且get/put操作不能同时执行，所以这种同步的集合效率非常低，一般不建议使用这个集合。

2、SynchronizedMap

private Map<String, Object> map = Collections.synchronizedMap(new HashMap<String, Object>());

这种是直接使用工具类里面的方法创建SynchronizedMap，把传入进行的HashMap对象进行了包装同步而已，来看看它的源码。

这个同步方式实现也比较简单，看出SynchronizedMap的实现方式是加了个对象锁，每次对HashMap的操作都要先获取这个mutex的对象锁才能进入，所以性能也不会比HashTable好到哪里去，也不建议使用。

3、ConcurrentHashMap - 推荐

private Map<String, Object> map = new ConcurrentHashMap<>();

这个也是最推荐使用的线程安全的Map，也是实现方式最复杂的一个集合，每个版本的实现方式也不一样，在jdk8之前是使用分段加锁的一个方式，分成16个桶，每次只加锁其中一个桶，而在jdk8又加入了红黑树和CAS算法来实现。

Hashmap 底层原理

在JDK8中,HashMap底层是采用“数组+链表+红黑树”来实现的。 HashMap是基于哈希算法来确定元素的位置（槽）的,当我们向集合中存入数据时,它会计算传入的Key的哈希值,并利用哈希值取余来确定槽的位置。如果元素发生碰撞,也就是这个槽已经存在其他的元素了,则HashMap会通过链表将这些元素组织起来。如果碰撞进一步加剧,某个链表的长度达到了8,则HashMap会创建红黑树来代替这个链表,从而提高对这个槽中数据的查找的速度。 HashMap中,数组的默认初始容量为16,这个容量会以2的指数进行扩容。具体来说,当数组中的元素达到一定比例的时候HashMap就会扩容,这个比例叫做负载因子,默认为0.75。 Put()方法的执行过程中,主要包含四个步骤：

1. 判断数组,若发现数组为空,则进行首次扩容。

2. 判断头节点,若发现头节点为空,则新建链表节点,存入数组。

3. 判断头节点,若发现头节点非空,则将元素插入槽内。

4. 插入元素后,判断元素的个数,若发现超过阈值则再次扩容。

其中,第3步又可以细分为如下三个小步骤：

1. 若元素的key与头节点一致,则直接覆盖头节点。

2. 若元素为树型节点,则将元素追加到树中。

3. 若元素为链表节点,则将元素追加到链表中。追加后,需要判断链表长度以决定是否转为红黑树。若链表长度达到8、数组容量未达到64,则扩容。若链表长度达到8、数组容量达到64,则转为红黑树。扩容机制向HashMap中添加数据时,有三个条件会触发它的扩容行为： 1. 如果数组为空,则进行首次扩容。

2. 将元素接入链表后,如果链表长度达到8,并且数组长度小于64,则扩容。

3. 添加后,如果数组中元素超过阈值,即比例超出限制（默认为0.75）,则扩容。并且,每次扩容时都是将容量翻倍,即创建一个2倍大的新数组,然后再将旧数组中的数组迁移到新数组里。由于HashMap中数组的容量为2^N

ConcurrentHashMap保证线程安全（简单）

其实ConcurrentHashMap保证线程安全主要有三个地方。

一、使用volatile保证当Node中的值变化时对于其他线程是可见的

二、使用table数组的头结点作为synchronized的锁来保证写操作的安全

三、当头结点为null时，使用CAS操作来保证数据能正确的写入。

使用volatile

可以看到，Node中的val和next都被volatile关键字修饰。

volatile的happens-before规则：对一个volatile变量的写一定可见（happens-before)于随后对它的读。也就是说，我们改动val的值或者next的值对于其他线程是

数组和链表

数组的特点

1、在内存中，数组是一块连续的区域。

2、数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。

3、插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。

4、随机读取效率很高。

5、并且不利于扩展，数组定义的空间不够时要重新定义数组。

链表的特点

1、在内存中可以存在任何地方，不要求连续。

2、每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。

3、增加数据和删除数据很容易。

4、查找数据时效率低，因为不具有随机访问性，

5、不指定大小，扩展方便。

数组的优点

随机访问性强

查找速度快

数组的缺点

插入和删除效率低

可能浪费内存

内存空间要求高，必须有足够的连续内存空间。

数组大小固定，不能动态拓展

链表的优点

插入删除速度快

内存利用率高，不会浪费内存

大小没有固定，拓展很灵活。

链表的缺点

不能随机查找，必须从第一个开始遍历，查找效率低

- 数组链表

读取 O(1) O(n)

插入 O(n) O(1)

删除 O(n) O(1)

排序

堆排序基本思想

什么是堆？堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 n-1 个 (0...n-1) 序列重新构造成一个堆，这样就会得到 n 个元素中的次小值。如此反复执行，便能得到一个有序序列了。

好了简单介绍之后，也没觉得有啥记忆的功能啊？

答: 其实堆是有记忆功能的，就是因为他自身的结构，每个结点的值都大于或等于其左右孩子结点的值（这是大顶堆，小顶堆则是每个结点的值都小于或等于其左右孩子结点的值），这就是记忆！当你将整个序列构建成一个堆之后，那么结点元素是比左右孩子大或者小的，这就是记忆！如果还是晕的，那么恭喜你，我在学习的过程中这个阶段的时候也是没想明白的，先看看实现吧！

关键点：

1. 初始化大顶堆

2. 构建大顶堆之后，交换堆顶元素和未排序序列的最后一个元素,并重新构建大顶堆

来了: 假设有一个初始集合 int[] arr = {13, 14, 99, 33, 82, 25, 59, 94};

那么 len=arr.length=8，第一个 for 循环，代码第 4 行，i 是从 len/2-1=3 开始，3→2→1→0 的变量变化。

为什么不是从 0 到 8，或者从 8 到 0，而是从 3 到 0 呢？其实下图就很明白了。它们都是有孩子的结点。

将待排序的序列构建成为一个大顶堆，其实就是从下往上，从右到左，将每个非终端结点（非叶结点）当作根结点，将其和其子树调整成大顶堆。

先构建成初始堆

然后构建初始大顶堆

到此为止构建大顶堆的过程算是完成了，任务完成了一半。接下来就是正式的排序过程，接着来