数据库事务的ACID和隔离级别

数据库事务的ACID四个基本特性

  • 原子性(Atomicity)
  • 一致性(Consistency)
  • 隔离性(Isolation)
  • 持久性(Durability)

通俗解释:原子性就是一个事物,要么就全部都执行,要么到就全部都不执行;一致性是指执行事务前后数据库都要保持一致性状态(满足主键约束、业务逻辑约束等);隔离性是指数据库一个事务的执行不受=其他事务的影响, 持久性是指事务一旦提交所做的更改是永久的。

数据库事务并发的三种问题:

脏读:一个事务在执行的过程中读到了另一个事务还未提交的修改。

不可重复读:事务A读到了一个输入,然后事务B对这个数据进行修改并提交,事务A1重新读取这个数据的时候发现不一致(针对update)

幻度:事务A通过一定的条件读到了一批数据,在这期间事务B对符合这个条件的数据进行了删除或者插入,那么数据A重新读到某条件下的一批数据时,数据的条数变化了(针对delete和insert)

数据库事务的四种隔离级别

  • 读未提交(Read Uncommitted)
  • 读提交(Read Committed)
  • 可重复读(Repeated Read)
  • 串行化(Serializable)

读未提交:可以读到未提交的内容;会产生“脏读”、“不可重复读”、“幻读”。如无特殊情况,基本是不会使用这种隔离级别的。

读提交:只能读到已经提交的内容。是SQL Server和Oracle的默认隔离级别。这种隔离级别能够有效的避免脏读,无法避免“不可重复读”和“幻读”。

可重复读:专门针对“不可重复读”这种情况而制定的隔离级别,它就可以有效的避免“不可重复读”(加update锁)(是MySql的默认隔离级别),不能避免“幻读”,因为幻读是由于“插入或者删除操作(Insert or Delete)”而产生的。

串行化:这是数据库最高的隔离级别,这种级别下,事务“串行化顺序执行”,“脏读”、“不可重复读”、“幻读”都可以被避免,执行效率差,开销大。

总结下面内容摘自: https://baijiahao.baidu.com/s?id=1611918898724887602&wfr=spider&for=pc

为什么会出现“脏读”?因为没有“select”操作没有规矩。

为什么会出现“不可重复读”?因为“update”操作没有规矩。

为什么会出现“幻读”?因为“insert”和“delete”操作没有规矩。

“读未提(Read Uncommitted)”能预防啥?啥都预防不了。

“读提交(Read Committed)”能预防啥?使用“快照读(Snapshot Read)”,避免“脏读”,但是可能出现“不可重复读”和“幻读”。

“可重复读(Repeated Red)”能预防啥?使用“快照读(Snapshot Read)”,锁住被读取记录,避免出现“脏读”、“不可重复读”,但是可能出现“幻读”。

“串行化(Serializable)”能预防啥?排排坐,吃果果,有效避免“脏读”、“不可重复读”、“幻读”,不过效果谁用谁知道。

参考资料:

https://baijiahao.baidu.com/s?id=1611918898724887602&wfr=spider&for=pc

字节抖音客户端提前批一面20200712

设计模式有了解那些?

写单例模式的代码

Java的四种引用类型

进程和线程的区别

volitile关键字是什么意思

进程中的sleep/wait/join/yeild方法分别有什么作用

Android有了解吗?安卓上的MVC、M什么的有了解吗?

一个ArrayList<String str> 里面删除所有特定的字符串要怎么做

编程题:

求两个单链表的交叉点

常见排序算法的稳定性分析

稳定性简而言之就是带相同元素在排序前和排序后的相对位置是否保持一致。

默认从小到大的进行排序

1.冒泡排序

思想:每一轮都是将最大的一个元素冒到数组的结尾。

分析:当相邻的两个元素相等的时候,通常的做法应该是选择后面的那个相同元素继续做冒泡的比较,这样稳定性就不会被破坏。但是如果你在两个相邻元素相同的时,还是选择了交换两个相同的元素,这样稳定性就会遭到破坏,当然没有人会这么多此一举,所以通常默认情况下,因此冒泡排序就是一个稳定的排序算法。

2.选择排序

思想:每一轮选择最小的值所在的下边,确定之后交换到特定位置

分析:举个反例 5,4,5,3 排序,第一轮之后 3,4,5,5 。两个5的相对位置发生了变化,因此选择排序不稳定

3.插入排序

思想:维护数组前部分有序,当前元素插入到合适的位置。

分析:如果再向前找的过程中发现相同元素,则插再这个相同元素的后面,这样相同元素的相对位置不发生变化,是一种稳定的排序算法。但是如果你找到相同元素的时候,硬是要插入到前面,那么就是不稳定了,这里的稳定是默认你不会做这么无聊的操作了。

4.快速排序

思想:主元+分治

分析:举一个反例:3,2,2 第一轮3作为主元,变成 2,2,3 ,这样就可以认为排好序了。两个2的相对位置发生了变化,一种不稳定的排序算法。

5.归并排序

思想:分治与归并

分析:元素的交换只发生的归并的阶段,就是merge两个有序的小数组的过程。归并的过程中需要借助辅助数组。两个有序数组中,小的数排前面,当遇到相同的数的时候,则左边数组的数先排,这样就可以保持相对位置。因此是一种稳定的算法。如果你非要先排右边数组的元素,那么就破坏了稳定性,当然也是需要考虑到你不会这么做。

其他排序算法:

桶排序(基数、计数):稳定

堆、希尔:不稳定

上述提到的稳定算法基本上都是理想上可以达到的,当程序员的实现上不严谨的时候,会导致稳定的排序算法变成一种不稳定的排序算法。

工程中的排序算法

工程中类库提供的排序都是经过高度集成与优化的,时间复杂度O(NlogN)的算法都涉及到递归的操作,工程中是不允许出现递归,递归排序都被改写成了非递归的。

Java中的Arrays.sort方法会先判断数据的长度,如果数据在一定范围内,会直接使用插入排序,因为插入排序虽然是一个时间复杂为O(N²)的排序算法,但是如果数据量并不是很大,那么相对来讲很快,并且插入排序的特点就是如果一个数据近似有序,那么时间复杂度也近似O(N)。如果数据量较大,那么Arrays.sort方法会再判断排序的data是基础类型还是一个自己定义的对象,如果是基础类型,那么会使用快排,因为基础类型要保持稳定性是无意义的,如果是对象例如自己定义的类Student,那么就会使用归并排序,保证data的稳定性。无论是归并排序还是快速排序,当数据量被分解到一定范围时,会再次转换为插入排序 。

参考文献:

https://blog.csdn.net/wumenglu1018/article/details/106712801

https://www.jianshu.com/p/a5b5b5c4ee0f

C++ 复习 STL库

参照传智播客的黑马的教程 https://www.bilibili.com/video/BV1et411b73Z/?p=2

Standard Template Library(标准模板库)

STL从广义上分为:容器、算法和迭代器 (container、algorithm、iterator)

容器之vector

三种遍历方法

#include<vector>
vector<int> v;
v.push_back(10);
vector<int>::iterator itBegin = v.begin(); //第一个元素的地址(指针)
vector<int>::iterator itEnd = v.end();    //最后一个元素的下一个元素的地址(指针)
while (itBegin != itEnd) {
    cont << * itBegin << endl;
    itBegin++;
}

for (vector<int> ::iterator it = v.begin(); it != v.end(); it++){
    cout<<*it<<endl;
}
#include <algorithm> //标准算法头文件
void myPring(int val){ cout<<val<<endl;}
for_each(v.begin(), v.end(), myPrint); //这里采用了回调函数的技术

自定义类型的容器

vector<Person> v;
for(vector<Person>::iterator it = v.begin(); it != v.end(); it++){
    cout << (*it).name << endl;
}
vecter<Person*>v;
for(vector<Person*>::iterator it = v.begin(); it != v.end(); it++){
    cout << (*(*it)).name << endl;
    cout << (*it)->name <<endl;
}

容器可以嵌套

vector<vector<int>> v;
for (vector<vector<int>>::iterator outerIt = v.begin(); outerIt != v.end(); outerIt ++) {
    for (vector<int> ::iterator innerIt = (*outerIt).begin(); innerIt != (*outerIt).end(); innerIt ++ ) {
        cout << *innerIt << " ";
    }
    cout<<endl;
}

string类,底层就是通过char*来实现的(字符串的字面量实际上时const char * 类型的)

string的四种构造函数

  • string()
  • string (const char * c)
  • string(const & string str)
  • string(int n, char a)

string类内部重载=赋值运算符,还重载了多个,还有提供了assign以及重载的多个方法。

string类内部还重载+=等拼接字符串的方法,还提供了append一些列重载函数。

string类的查找函数find,rfind,一个从左往右找,一个从右边往左边查,并且重载了一系列。

string类的替换函数replace,详细函数的定义需要查查文档。

字符串比较 int compare(const & str)

字符串重载[]实现字符的读写,也提供了at函数提供访问。(这和java不同)下面两种都是合法的。

  • str[1] = ‘a’;
  • str.at(1) = ‘b’;

字符串插入删除 insert() erase()方法

字符串的字串 subStr()

vector

是一个动态的数组,有以下四种方式的构造函数

  • vector()
  • vector(v.begin(), v.end())
  • vector(int n, element)
  • vector(const vector & v)

vector容器可以赋值(重载了operator=),也可以调用assign方法

vector的size() capacity() empty() resize()方法

vector的插入和删除

push_back() pop_back() insert() erase()

vector元素存储 重载[]运算符,调用at(), front() 第一个元素,back()最后一个元素

vector容器的swap()方法

看得懂这个代码吗 vector<int>(v).swap(v)

调用拷贝构造函数创建匿名对象并实现vector的内容交换,一定程度上会节省v中capacity多余的空间浪费,而匿名对象会被系统回收。

reserve()函数,预留空间,减少动态扩容是的复制数据的开销。

deque容器

双端队列 #include<deque>

头部插入的效率高于vector,具体需要数据结构看底层源码

vector访问元素的速度会比deque快

API基本和vector类似,只是多了一些在头部的方法

deque没有capacity()方法,和底层实现有关(中控器)

//deque容器的排序
#include <algorithm>
sort(d.begin(), d.end())

stack容器

#include<stack>

stack<T> stk; stack<T>(const & stack stk); 普通构造和拷贝构造

pop push top 三个方法

size empty 方法

queue容器

#include<queue>

queue<T> que; queue<T>(const & queue que);

pop push front back 方法

size empty 方法

list容器

list表示链表(注意和java中的区别),c++底层实现是双向循环列表

多数的API和vector差不多,但是没有capacity的概念,不支持[] 和at访问,l.begin() 只能++或者– 不能 +=1 +=2 之类的(不支持随机访问)

反转和排序 list<int> l; l.reverse(); l.sort()

所有不支持随机访问迭代器的容器,不可以使用标准算法,(#include <algorithm>),一般来说这种容器的内部会提供对应的成员方法。

bool compare(int v1, int v2){ return v1 > v2; }
l.sort(compare);   //降序排序

自定义数据类型排序需要指定排序规则。

set/multiset

#include<set>

底层是用二叉树来实现的数据结构,是一种关联式容器

set不允许重复元素,multiset允许重复元素

插入元素只能用insert函数,删除erase,清空clear

find函数返回的是迭代器,count函数非1即0(multiset可能是其他值)

    set<int> s;
    pair<set<int>::iterator, bool> res = s.insert(100);
    if (res.second) {
        cout << "successful insertion!" << endl;
    } else {
        cout << "inserted failed!" << endl;
    }
    res = s.insert(100);
    if (res.second) {
        cout << "successful insertion!" << endl;
    } else {
        cout << "inserted failed!" << endl;
    }

set 的函数返回的结果是pair<iterator, bool> 第二个参数表示是否插入成功。

pair队组

两种创建队组的方式

  • pair<string, int> p(“Amy”, 17);
  • pair<string, int> p2 = make_pair(“Jerry”, 30);

cout << p.first << ” ” << p.second << endl;

set的排序(仿函数)

class MyCompare {
    public:
        bool operator()(int a, int  b) const{
            return a > b;
        }
};

int main() {
    cout << 'a' << endl;
    set<int, MyCompare> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);
    s.insert(5);
    for (set<int, MyCompare>::iterator iter = s.begin(); iter != s.end(); iter ++) {
        cout << *iter << endl;
    }

}

自定义数据类型装入set中必须在创建set的时候,指定仿函数比较器,或者在自定义类中重载比较运算符。

Map容器

#include <map> //一种关联式容器

map里面存的都是队组pair

int main() {
    map<int, int> m;
    m.insert(pair<int, int>(10,10));
    m.insert(make_pair(30,10));
    m.insert(pair<int, int>(20,10));
    for (map<int, int>::iterator iter = m.begin(); iter != m.end(); iter++) {
        cout << iter->first << " " << iter->second <<endl;
    }
}

empty size swap erase(重载多个) clear

查找元素

map<int, int>::iterator iter pos = m.find(key);

函数对象(仿函数)

特点

  • 函数对象在使用时,像普通函数一样调用
  • 函数对象超出普通函数的概念,可以有自己的状态
  • 函数对象可以作为参数传递

谓词

仿函数返回值是bool数据类型,称为谓词。(有些类似java中的函数式接口或者python中的filter)

一元谓词(有一个形式参数)–过滤

二元谓词(有两个形式参数) –排序

内建函数对象

算术仿函数

#include <functional>
negate<int>n; //一元
cout<<n(50)<<endl;
plus<int> q;  //二元
cout<<q(10,5)<<endl;

关系仿函数(greater 最常用)

#include<vector>
#include<functional>
vector<int>v;
sort(v.begin(), v.end(), greater<int>());  //关键在这里
for(vector<int>::iterator it = v.begin(); it != v.end(); it ++) {
     cout << (*it) << endl;
}

逻辑仿函数(基本用不到)

STL常用算法

  • #include<algorithm>
  • #include <numeric>
  • #include <functional>

遍历

for_each(v.begin(), v.end(), 函数或者仿函数);

搬运、转换(类似java8的stream或者python的列表表达式)

trandform(s.begin(), s.end(), d.begin(), 函数或者仿函数); //目标容器需要提前开辟空间

查找:

find (v.begin(), v.end(), int val); //自定义类型需要重写运算符==方法。

find_if(v.begin(), v.end(), 仿函数); //

adjacent_find 查找重复相邻元素的地址

binary_search(v.begin(), v.end(), int val);

count(v.begin(), v.end(), int val);

count_if(v.begin(), v.end(), 一元谓词);

排序

sort(v.begin(), v.end(), 二元谓词);

random_shuffle(v.begin(), v.end());//记得加随机数种子

merge(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()); //target需要先开辟,v1,v2需要有序

reverse(v1.begin(), v2.begin());

拷贝和替换

copy(v1.begin(), v1.end(), target.begin()); //先开辟空间

replace(v1.begin(), v2.end(), int old, int new);

replace_if(v.begin(), v.end(), 一元谓词, int new);

swap(v1,v2);//同种类型的容器才能交换

算术生成算法

#include <numeric>
int total = accumulate(v.begin(), v.end(), int start_sum);
fill(v.begin(), v.end(), 100);

“集合”算法

set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()) //target的容量需要先开辟,前提必须是两个有序的序列

set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()) //target的容量需要先开辟, 要求有序

set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()) //target的容量需要先开辟, 要求有序 ,差集有先后顺序关系