插入排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
void InsertionSort(vector<int> &arr, int len){
for(int i=1; i<len; i++){
int key=arr[i]; //需要插入的元素
int j=i-1; //排好序的区间
while(j>=0 && arr[j]>arr[i]){
arr[j+1]=arr[j]; //向后移动
j--;
}
arr[j+1]=key;
}
}

分析

  • 时间复杂度:最好情况下数组已经有序,此时复杂度为O(n);最坏情况下数组为倒序,此时复杂度为O(n^2)。
  • 空间复杂度:原地排序算法,没有额外内存消耗。
  • 稳定性:只有遇到比当前元素大的才需要把它们移动到后面,所以是稳定排序。(注:我们分析稳定性有一定的实际意义。如果对有多个属性的复杂元素排序,使用稳定排序可以使我们对其中一个属性排序时不影响其它属性。)

选择排序

代码实现

1
2
3
4
5
6
7
8
9
void SelectionSort(vector<int> &arr, int len){
for(int i=0; i<len-1; i++){
int min=i;
for(int j=i+1; j<len; j++){
if(arr[j]<arr[min]) min=j; //寻找未排序区间里的最小值
}
swap(arr[i], arr[min]);
}
}

分析

  • 时间复杂度:最好和最坏情况下都需要遍历未排序区间,所以时间复杂度都是O(n^2)。
  • 空间复杂度:没有额外的内存消耗。
  • 稳定性:不稳定,因为每次都要在未排序区间找到最小值和前面的值交换,这样前面的值可能会被换到和它相等的值的后面(比如,232154 -> 132254)。

冒泡排序

代码实现

1
2
3
4
5
6
7
8
void BubbleSort(vector<int> &arr, int len){
for(int i=0; i<len-1; i++){ //i是已排好的区间的长度
for(int j=0; j<len-i-1; j++){ //j用来遍历未排好的区间中的元素(最后一个没遍历)
if(arr[j]>arr[j+1])
swap(arr[j], arr[j+1]);
}
}
}

分析

  • 时间复杂度:最好情况下,内层循环过一遍发现没有元素发生交换,直接结束,复杂度为O(n)。最坏情况下复杂度为O(n^2),平均复杂度也是O(n^2)。
  • 空间复杂度:没有用到额外空间。
  • 稳定性:在元素相等的情况下,我们不予交换,因此冒泡排序是稳定排序。

归并排序

代码实现

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 Merge(vector<int> &arr, int left, int mid, int right){
int len=right-left+1;
vector<int> tmp(len);
int i=left, j=mid+1, k=0;
while(i<=mid && j<=right){
tmp[k++]=(arr[i]<=arr[j])?arr[i++]:arr[j++]; //这里的 <= 保证了优先放入左边数组元素
}
while(i<=mid){
tmp[k++]=arr[i++];
}
while(j<=right){
tmp[k++]=arr[j++];
}
for(int m=0; m<len; m++){
arr[left+m]=tmp[m];
}
}

void MergeSort(vector<int> &arr, int left, int right){
if(left>=right) return;
int mid=(left+right)/2;
MergeSort(arr, left, mid);
MergeSort(arr, mid+1, right);
Merge(arr, left, mid, right);
}

分析

  • 时间复杂度:O(nlogn),需要数学推导。
  • 空间复杂度:需要分配临时数组tmp,空间复杂度为O(n)。
  • 稳定性:当需要归并的左右数组中有元素相同时,我们可以保证优先放入左边数组的元素,所以是稳定排序。

快速排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Partition(vector<int> &arr, int left, int right){
int pivot=right, location=left; //location用来记录比pivot小的元素在分好的数组中的位置
int r=rand()%(right-left+1)+left; //随机化,注意要在主调函数里写srand((unsigned)time(NULL));
swap(arr[r], arr[right]);
for(int i=left; i<=right; i++){
if(arr[i]<arr[pivot]){
swap(arr[i], arr[location]);
location++;
}
}
swap(arr[location], arr[pivot]);
return location;
}

void QuickSort(vector<int> &arr, int left, int right){
if(left>=right) return;
int pivot=Partition(arr, left, right);
QuickSort(arr, left, pivot-1);
QuickSort(arr, pivot+1, right);
}

分析

  • 时间复杂度:如果每次分区都能把数组分成大小一样的区间,那么时间复杂度是O(nlogn),但是最坏情况下可能退化成为O(n^2)。
  • 空间复杂度:没有额外内存消耗。
  • 稳定性:不是稳定排序。

计数排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> CountSort(vector<int> &arr){
int maxValue=arr[0];
int minValue=arr[0];
for(int i=1; i<arr.size(); i++){
maxValue=max(maxValue, arr[i]);
minValue=min(minValue, arr[i]);
}
vector<int> sortedArray(arr.size(), 0);
vector<int> count(maxValue-minValue+1, 0);

for(int i=0; i<arr.size(); i++){ //计数
count[arr[i]-minValue]++;
}
for(int i=1; i<count.size(); i++){ //累加
count[i]+=count[i-1];
}

for (int k = arr.size()-1; k >=0; k--) { //反向填充,可以保证稳定性
sortedArray[count[arr[k]-minValue]-1] = arr[k];
count[arr[k]-minValue]--;
}
return sortedArray;
}

分析

  • 时间复杂度:O(n+k),k就是maxValue-minValue+1。
  • 空间复杂度:O(n+k),与时间复杂度相同。
  • 稳定性:稳定,见代码。

桶排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BucketSort(vector<int>& arr) {
vector<vector<int>> buckets(10); //这里假设有10个桶
//基本思想是将数组中的元素分配到几个桶里,然后对每个桶分别排序(可能用到其它算法)
//如果桶的数量等于数组元素的数量,就变成了计数排序
for(int i=0; i<arr.size(); i++){
buckets[a[i] / 10].push_back(a[i]); //例如,0~9放到buckets[0]里,11~19放到buckets[1]里……
}
for(int i=0; i<10; i++){
sort(buckets[i].begin(), buckets[i].end()); //桶内排序
}
int index=0;
for(int i=0; i<10; i++){
for(int j=0; j<buckets[i].size(); j++){
arr[index++]=buckets[i][j];
}
}
}

分析

  • 时间复杂度:如果要排序的数据有n个,我们把它们分在m个桶中,这样每个桶里的数据就是k = n/m。每个桶内排序(假设用快排)的时间复杂度就为O(k*logk)。m个桶就是
    m*O(klogk)=m*O((n/m)*log(n/m))=O(n*log(n/m))。当桶的个数m接近数据个数n时,log(n/m)就是一个较小的常数,所以时间复杂度接近O(n)。但是如果运气不好,所有的元素都到了一个桶了,那么它的时间复杂度就退化成 O(nlogn) 了。
  • 空间复杂度:O(n+m),其中n为待排序元素的个数,m为桶的数量。
  • 稳定性:取决于桶内排序使用的算法。

基数排序

代码实现

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
void RadixSort(vector<int>& arr) 
{
int bit = maxbit(arr);
vector<int> tmp(arr.size());
vector<int> count(10); //0-9计数器
int i, j, k;
int radix = 1;
for (i = 1; i <= bit; i++) //进行bit次排序
{
for (j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空计数器
for (j = 0; j < arr.size(); j++)
{
k = (arr[j] / radix) % 10;
count[k]++;
}
for (j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j];

for (j = arr.size() - 1; j >= 0; j--) //和前面计数排序的原理相同
{
k = (arr[j] / radix) % 10;
tmp[count[k] - 1] = arr[j];
count[k]--;
}

for (j = 0; j < arr.size(); j++)
arr[j] = tmp[j];
radix = radix * 10;
}
}

分析

  • 时间复杂度:基数排序的时间复杂度是O(k*n),其中n是排序的元素个数,k是元素中最大元素的位数。
  • 空间复杂度:O(n+m),n为tmp数组的长度,m为count数组的长度。
  • 稳定性:是稳定的,原因同计数排序。

希尔排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ShellSort(vector<int>& arr) {
for (int gap = arr.size() / 2; gap > 0; gap /= 2) { //最初的gap是n/2,不断对步长折半
for (int i = gap; i < arr.size(); i++) { //每一轮循环,排序下标为i, i+gap, i+2*gap...的元素
int temp = arr[i];
int j;
//这里用的是插入排序
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}

arr[j] = temp;
}
}
}

分析

  • 时间复杂度:和步长序列有关,以上代码展示序列的时间复杂度为O(n^(1.3-2))。
  • 空间复杂度:原地排序,没有额外空间消耗。
  • 稳定性:将数据分组并存在元素的交换,所以不稳定。

堆排序

代码实现

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 Heapify(vector<int> &arr, int n, int i){
int smallest=i; //这里维护的是一个小顶堆
int left=2*i+1, right=2*i+2;
if(left<n && arr[left]<arr[smallest]){
smallest=left;
}
if(right<n && arr[right]<arr[smallest]){
smallest=right;
}
if(smallest!=i){
swap(arr[i], arr[smallest]);
heapify(arr, n, smallest);
}
}

void HeapSort(vector<int> &arr, int len){
for(int i=len/2-1; i>=0; i--){
Heapify(arr, len, i);
}
for(int i=len-1; i>0; i--){
swap(arr[0], arr[i]);
Heapify(arr, i, 0);
}
reverse(arr.begin(), arr.end());
}

分析

  • 时间复杂度:在所有情况下均为O(nlogn)。
  • 空间复杂度:没有用到额外空间。
  • 稳定性:堆排序是不稳定的,因为堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, …1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。

WebSocket

WebSocket是Web浏览器和Web服务器之间的全双工通信标准。它支持由服务器向客户端推送数据的推送功能,并且能够减少通信量。为了实现WebSocket通信,在HTTP连接建立之后,需要完成一次握手的步骤。

ASGI

ASGI的全称是异步服务器网关接口,它是一个介于Web服务器和Web应用程序之间的标准接口。与ASGI相关的另一个重要概念是WSGI,也就是Web服务器网关接口。WSGI是基于HTTP协议模式开发的,不支持WebSocket。ASGI是WSGI的扩展,在原有基础上增加了许多新的特性,比如支持HTTP2,WebSocket和异步通信等。

Starlette

Starlette是一个支持ASGI的异步框架,它可以用于构建Web应用程序。在以下示例中,我们通过Starlette类构建了一个应用(app),并注册了主页(homepage)的路由。

1
2
3
4
5
6
7
8
9
10
11
12
from starlette.applications import Starlette
from starlette.responses import JSONResponse
from starlette.routing import Route


async def homepage(request):
return JSONResponse({'hello': 'world'})


app = Starlette(debug=True, routes=[
Route('/', homepage),
])

Uvicorn

Uvicorn是一个快速的ASGI服务器,基于uvloop(用于处理事件循环)和httptools(用于处理HTTP协议)构建。通过它,前端可以与后台的应用程序进行交互。Uvicorn要求应用程序实现一个包含三个参数(连接信息scope,接收信道receive,发送信道send)的函数或示例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
async def app(scope, receive, send):
assert scope['type'] == 'http'
await send({
'type': 'http.response.start',
'status': 200,
'headers': [
[b'content-type', b'text/plain'],
]
})
await send({
'type': 'http.response.body',
'body': b'Hello, world!',
})

if __name__ == "__main__":
uvicorn.run("main:app", port=5000, log_level="info")

可以通过以下命令运行Uvicorn:

1
uvicorn main:app

Pydantic

Pydantic是一个Python库。用户只需定义一个类,用Python的类型提示标注其字段,Pydantic就会自动处理验证和序列化。
在以下示例中,我们将输入数据传递给一个Order类,如果数据无效,Pydantic将自动抛出一个详细的错误,指出哪个字段无效以及为什么。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from pydantic import BaseModel, Field

class Order(BaseModel):
product_id: int = Field(..., gt=0)
quantity: int = Field(..., gt=0, le=100)
payment_method: str = Field(..., regex="^(credit_card|paypal)$")

order_data = {
"product_id": 1,
"quantity": 50,
"payment_method": "credit_card"
}

try:
order = Order(**order_data)
except ValidationError as e:
print(e.json())

我们还可以将order序列化为字典或者JSON格式。

1
2
order_dict = order.dict()
order_json = order.json()

FastAPI

FastAPI是一个基于Starlette和Pydantic的API框架,它具有非常高的性能,并且包含数据处理的功能。此外,它可以自动生成交互式API文档,便于开发和测试。

输入输出

标准输入输出对象

iostream库包含两个基础类型istream和ostream,分别表示输入流和输出流,一个流就是一个字符序列。cin是istream类型的对象,被称为标准输入。cout是ostream类型的对象,被称为标准输出。此外,标准库还定义了其它两个ostream对象,分别是cerr(标准错误,输出警告和错误信息)和clog(输出程序运行时的一般性信息)。

输入输出有关符号

1
cout<<"Hello World!"<<endl;
  • <<是输出运算符,它接受两个运算对象,左侧是ostream对象,右侧是要打印的值。输入运算符>>与它类似。
  • endl是一个被称为操纵符的特殊值。写入endl的效果是结束当前行,并将与设备关联的缓冲区中的内容刷到设备中(可以保证程序输出真正写到输出流中,而不是在内存中等待)。

几种输入方式的对比

  • cin:
    • 不管数据类型是什么,输入一开始都是字符数据,然后cin对象负责将数据转换成其他类型。
    • 使用空白(空格,制表符和换行符)来确定字符串的结束位置,在读取字符数组时,cin将只会读取第一个单词。比如输入“Michael Jackon”,cin第一次只会读入“Michael”。
      1
      2
      string name;
      cin>>name;
  • getline:
    • 用于读取整行,通过换行符来确定输入的结尾。
    • 并不保存换行符,保存字符串时会用空字符来代替换行符。
      1
      2
      string name;
      getline(cin, name);
  • get:
    • 工作方式和getline类似,也是读取到行尾。
    • 读取到行尾时不丢弃换行符,而是把它留在输入队列中,所以下一次读取的时候会读到换行符。
      1
      2
      3
      4
      string name, dessert;
      cin.get(name,50); //第一个参数是字符数组名,第二个参数是接受字符的数目(包括结尾的\0)
      cin.get(); //用于去掉换行符
      cin.get(dessert,50);

控制流与数据输入

1
2
3
4
5
int sum = 0, value = 0;
//读取数据直到遇到文件尾,计算所有读入的值的和
while(cin >> value){
sum += value;
}

使用istream对象作为条件,可以检测流的状态。如果流是有效的,那么检测成功。当遇到文件结束符或无效输入时,istream对象的状态会变为无效,从而使条件变为假,退出循环。(getline函数也可以这么用,它的返回值是输入流对象。如果读取成功,则返回输入流对象本身;如果发生错误,则返回一个错误状态。)

变量和基本类型

基本内置类型

编译器可以根据自身硬件来选择基本类型的大小,但是需要满足约束:short和int型至少为16位,long型至少为32位,并且short型长度不能超过int型,而int型不能超过long型。下面列举在GCC编译器下32位机器和64位机器各个类型变量所占字节数:

类型转换

隐式转换

  • 编译器自动执行的类型转换称为隐式转换,它无需程序员的介入。
  • 隐式转换有一些风险,比如隐藏类型不匹配的错误,数据精度降低(double转到int),单参数类构造函数可能会被无意地用于隐式类型转换。
  • explicit关键字用于修饰类的构造函数,它禁止隐式调用拷贝构造函数以及类对象之间的隐式转换。
    1
    2
    3
    4
    5
    6
    7
    8
    class Test
    {
    explicit Test(int a);
    }

    Test aa(10); // OK
    Test aa = 10; // 非法,此操作被禁止。加入explicit 可以有效的防止隐式转换的发生,提高程序质量。
    Test bb = aa; // 非法,取消了隐式转换,除非重载操作符“=”

显式转换

  • 普通的显示转换主要有两种:函数型和类C型。它们可以满足大部分需求,但是这些操作符不加区别地应用于类和指向类的指针上,可能导致代码在语法正确的情况下导致运行时错误。
    1
    2
    3
    4
    double x = 10.3;
    int y;
    y = int (x); //函数型
    y = (int) x; //类C型
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //情况一,通过强制类型转换,不同类型的指针可以随意转换,编译器不报错
    Dummy d;
    Addition * padd;
    padd = (Addition *)&d;
    cout << padd->result()<<endl; //Dummy 类中没有result方法,但是编译器不报错

    //情况二:将指向const对象的指针转成指向非const
    int a = 666;
    const int *p1 = &a;
    int *p2 = (int *)p1;
    *p2 = 999; //经过强制类型转换后,失去了const属性,此时不报错
    cout <<"a = "<< a << endl; //a 的值已被更改了
  • 为解决以上问题,C++引入了四种类型转换,它们用于不同场景和需求:
    • dynamic_cast:用于将父类的指针或引用转换为子类的指针或引用,此场景下父类必须要有虚函数。
    • static_cast:用于基本数据类型之间的转换使用(例如float转int,int转char等),有类型指针和void *之间的转换使用,子类对象指针转换成父类对象指针。
    • const_cast:用于常量指针或引用与非常量指针或引用之间的转换。
    • reinterpret_cast:类似C语言中的强制类型转换,什么都可以转,一般情况下不要使用。

常量和变量

常量

在程序运行时值不可以改变。

  • 字面值常量:字面值常量的形式和值决定了它的数据类型,比如20,0x14,3.14,’a’,”Hello World”等。
  • 符号常量:
    • 宏定义:在预处理中使用,单纯的文本替换。
    • const常量:由C++编译器处理,提供类型检查和作用域检查。

变量

在程序运行时值可以改变。

  • static:
    • 如果用static修饰局部变量,那么这个变量就不会存储在栈区而是放在静态数据区。它的生命周期一直持续到程序结束,而且只在初次运行时进行初始化。
    • 如果用static修饰全局变量,那么在其它文件中也可以访问此变量。然而,如果是在源文件(cpp)中去操作这个静态全局变量,则这个静态全局变量只能在当前文件有效,但是在另外一个文件访问此静态变量,会是该变量初始的默认值,不会是其他文件中修改的值。虽然它们有相同的初始内容,但是存储的物理地址并不一样。如果想在不同文件共享同一个全局变量就要用到extern。
  • extern:如果想声明一个变量而非定义它,就在变量名前添加关键字extern,而且不要显式地初始化变量。
    1
    2
    extern int i;     //声明而非定义
    extern int i = 0; //定义

复合类型

复合类型是指基于其它类型定义的类型。

引用

1
2
int ival = 1024;
int &refVal = ival; //refVal指向ival(是ival的另一个名字)
  • 引用为对象起了另外一个名字,它本身不是对象。定义引用时,程序把引用和它的初始值绑定在一起,为引用赋值实际上是把值赋给了与引用绑定的对象。
  • 引用必须被初始化,而且一旦引用被初始化,就不能改变引用的关系。
  • 不能有NULL引用,引用必须与合法的存储单元关联。

指针

1
double dp1, *dp2;  //dp1是double型对象,dp2是指向double型对象的指针
  • 指针是“指向”另一种类型的复合类型,它本身就是一个对象,允许对指针赋值和拷贝,而且在指针的生命周期内它可以先后指向几个不同的对象。
  • 指针无需在定义时赋初值,但在块作用域内的指针如果没被初始化会有一个不确定的值。
  • 空指针不指向任何对象,得到空指针最直接的办法就是用字面值nullptr来初始化指针。
  • void*是一种特殊的指针类型,可用于存放任意对象的地址。

处理类型

需要一些方法来处理内置类型名字难记的问题。

类型别名

1
2
typedef double wages;
wages hourly, weekly;

类型别名是某种类型的同义词,它让原本复杂的类型名字变得易于理解和使用。

auto类型说明符

1
2
//由val1和val2相加的结果可以推断出item的类型
auto item = val1 + val2;

auto类型说明符由C++11新标准引入,它能让编译器替我们分析表达式所属的类型。

其它关键概念

命名空间

当程序用到多个供应商提供的库时,会发生某些名字相互冲突的情况,命名空间可以解决这个问题。

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 第一个命名空间
namespace first_space{
void func(){
cout << "Inside first_space" << endl;
}
}
// 第二个命名空间
namespace second_space{
void func(){
cout << "Inside second_space" << endl;
}
}
int main ()
{
// 调用第一个命名空间中的函数
first_space::func();
// 调用第二个命名空间中的函数
second_space::func();
return 0;
}

在以上代码中,我们定义了两个命名空间,它们都有函数func。

使用

1
2
using namespace std;  //引入std中的所有内容
using std::cout; //只引入cout

std命名空间是C++中标准库类型对象的命名空间。使用上面的第一行代码可以引入std命名空间的所有内容,但是这是一种不保险的做法,因为这样相当于引入了所有的组件名称,重新引发了名字空间泛滥的问题。更好的做法是按需引入,比如第二行代码。另外,头文件不应包含using声明,因为头文件的内容会拷贝到所有引用它的文件中,如果头文件里有某个using声明,那么所有使用了该头文件的文件都会有这个声明,这可能会产生始料未及的名字冲突。

迭代器

迭代器用于访问容器中的元素,所有标准库容器都可以使用迭代器。迭代器有有效和无效之分,有效的迭代器或者指向某个元素,或者指向容器中尾元素的下一位置,其它所有情况都属于无效。

运算符

以下运算符是所有容器的迭代器都支持的。string和vector的迭代器提供了更多额外的运算符,比如iter+=n,>=等。

遍历

1
2
3
for(auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " ";
}

可以使用迭代器遍历容器中的元素,比如上面的代码在遍历一个set中的元素。

异常处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int a, b;
cin>>a>>b;
try{
if(a!=b){
throw runtime_error("not equal");
}else{
throw exception();
}
}catch(runtime_error err){
cout<<err.what()<<endl;
}catch(exception err){
cout<<"exception"<<endl;
}
//当输入的a和b不相等时,程序输出"not equal";当a和b相等时,程序输出"exception"。

在以上示例中,try语句块里的代码抛出异常,catch子句用来捕获异常并执行对应的操作。C++标准库里定义了一些异常类。例如,stdexcept库里定义的异常类如下所示:

函数重载

1
2
3
4
5
6
7
8
void print(const char *cp);                 //func1
void print(const int *beg, const int *end); //func2
void print(const int ia[], size_t size); //func3

int j[2] = {0,1};
print("Hello World"); //调用func1
print(j, end(j)-begin(j)); //调用func2
print(begin(j), end(j)); //调用func3

如果同一作用域内的几个函数名字相同但形参列表不同,我们称之为重载函数。当调用这些函数时,编译器根据传递的实参类型推断想要的是哪个函数。

基本情况

HTTP协议的全称是“Hyper Text Transfer Protocol”(超文本传输协议),它定义了客户端和服务器之间交换报文的格式和方式。

URI和URL

  • URI:统一资源标识符,用来唯一地标识一个资源(比如文档、图像、视频等)。
  • URL:统一资源定位器,是一种具体的URI,可以用来标识一个资源,而且还指明了如何定位这个资源。一个完整的URL包含以下几个部分:

短连接和长连接

  • 短连接:在HTTP/1.0中默认使用短连接。也就是说,客户端和服务器每进行一次HTTP操作,就建立一次连接,任务结束就中断连接。
  • 长连接:从HTTP/1.1起,默认使用长连接,采用同一个TCP连接来发送和接收多个HTTP请求/应答,避免了连接建立和释放的开销。长连接还给HTTP流水线技术(客户端可以先一次性发送多个请求,而在发送过程中不需先等待服务器的回应)提供了可实现的基础。此外,需要注意与TCP保活(keep-alive)机制(当客户端和服务端长达一定时间没有数据交互时,内核为了确保该连接还有效,发送探测报文来检测对方是否在线,然后决定是否要关闭该连接)的对比,TCP保活机制是由内核实现的,而HTTP长连接是由应用程序实现的。

Cookie和Session

  • Cookie:
    • 背景:HTTP是无状态的,服务器记不住用户,每刷新一次网页就要重新登录。为解决此问题,HTTP/1.1引入Cookie。
    • 定义:Cookie 是服务器发送到用户浏览器并保存在本地的一小块数据,它会在浏览器之后向同一服务器再次发起请求时被携带上,用于告知服务端两个请求是否来自同一浏览器。
    • 用途:会话状态管理(如用户登录状态),个性化设置(如用户自定义主题),浏览器行为跟踪(如跟踪分析用户行为)
  • Session:
    • 原理:当用户登录时,服务器会创建对应的Session,Session创建完之后,会把Session的ID(这个ID相当于Cookie)发送到客户端并存储在浏览器中。这样客户端每次访问服务器时,都会带着这个ID,服务器拿到Session ID之后,在内存找到与之对应的Session。
    • 对比:Cookie是客户端保持状态的方法,而Session是服务器保持状态的方法。

与其它协议的关系

  • DNS:通过域名获取相应的IP地址
  • HTTP:生成针对目标Web服务器的HTTP请求报文。
  • TCP:为了方便通信,将HTTP请求报文分割成报文段,按序号分为多个报文段,把每个报文段可靠地传给对方。
  • IP:搜索对方的地址,一边中转一边传送。

报文结构

请求报文主要包括请求行(包含请求方法、请求URI和HTTP版本)、请求头和请求体。响应报文主要包括状态行(包含状态码、原因短语和HTTP版本)、响应头和响应体。

请求方法

HTTP中主要有以下请求方法:

状态码

状态码主要有以下几种:

HTTPS

HTTP与HTTPS的对比

  • HTTP协议传输的数据都是未加密的,也就是明文的,因此使用HTTP协议传输隐私信息非常不安全, HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议,要比HTTP协议安全。
  • HTTPS协议需要到ca申请证书,一般免费证书较少,因而需要一定费用。此外,HTTPS因为有SSL验证,所以更耗费服务器资源,响应速度也更慢。
  • HTTP和HTTPS使用的是不同的连接方式,用的端口也不一样,前者是80,后者是443。

SSL/TLS

SSL代表安全套接字层,它是一种用于加密和验证应用程序(如浏览器)和Web服务器之间发送的数据的协议。SSL握手的主要过程如下:

概述

在Web系统中,身份验证是十分关键的,它保证访问系统的都是具有合法状态的用户。Web身份验证的方法有很多种,本文将重点介绍一种基于令牌的验证技术JWT,同时与其它的验证技术相对比。
JSON Web Token(缩写 JWT)是目前最流行的跨域认证解决方案,用于创建具有可选签名和加密的数据,于2010年被首次提出。它的出现源于互联网服务中用户认证的需求。
基于会话的认证是用户认证的一个常见方法,它的一般流程是:用户向服务器发送用户名和密码;服务器验证通过后,在当前会话(session)里面保存相关数据,比如用户角色、登录时间等等;服务器向用户返回一个 session_id,写入用户的 cookie;用户随后的每一次请求,都会通过 cookie,将 session_id 传回服务器;服务器收到 session_id,找到前期保存的数据,由此得知用户的身份。
这种模式有一个问题,它的扩展性不好。如果是服务器集群,或者是跨域的服务导向架构,就要求 session 数据共享,每台服务器都能够读取 session,而上述认证过程无法做到这一点。一种解决方案是 session 数据持久化,写入数据库或别的持久层。各种服务收到请求后,都向持久层请求数据。这种方案的优点是架构清晰,缺点是工程量比较大。另外,持久层万一挂了,就会单点失败。另一种方案是服务器索性不保存 session 数据了,所有数据都保存在客户端,每次请求都发回服务器。JWT 就是这种方案的一个代表。
JWT 的原理是,服务器认证以后,生成一个 JSON 对象并发回给用户。以后,用户与服务端通信的时候,都要发回这个 JSON 对象。服务器完全只靠这个对象认定用户身份。为了防止用户篡改数据,服务器在生成这个对象的时候,会加上签名。返回的JWT主要包括三个部分:Header(头部,用于描述JWT的元数据)、Payload(负载,用来存放实际需要传递的数据)和Signature(签名,防止数据篡改),如下图所示。

JWT的应用场景主要有两种。首先是授权,这是使用 JWT 最常见的场景。通过授权,可以验证发送到服务器的请求是否属于通过身份验证登录的用户,从而可以授予该用户访问系统的权限,继而批准该用户使用获得的 token 访问路由、服务和资源。其次是信息交换。因为 JWT 可以被签名(例如,使用公钥/私钥对),所以能确保发送方是他们所声称的那一方。此外,由于签名是使用 Header 和 Payload 计算的,因此还能验证发送的内容没有被篡改。

特点

JWT主要有这么几个优点。首先,JWT的使用比较灵活。它默认不加密,但也是可以加密的。生成原始 Token 以后,可以用密钥再加密一次。在JWT 不加密的情况下,不能将秘密数据写入 JWT。其次,JWT 不仅可以用于认证,也可以用于交换信息。有效使用 JWT,可以降低服务器查询数据库的次数。然而,JWT也存在一些缺陷。它的最大缺点是,由于服务器不保存 session 状态,因此无法在使用过程中废止某个 token,或者更改 token 的权限。也就是说,一旦 JWT 签发了,在到期之前就会始终有效,除非服务器部署额外的逻辑。此外,JWT 本身包含了认证信息,一旦泄露,任何人都可以获得该令牌的所有权限。为了减少盗用,JWT 的有效期应该设置得比较短。对于一些比较重要的权限,使用时应该再次对用户进行认证。

产品介绍与比较

除JWT外,还有一些其它的身份验证技术,比如基于会话的验证、一次性密码等。下面我将逐一介绍它们的特点,同时对比分析JWT。
HTTP协议提供了一些身份验证的机制,其中最基本的一种是把登录凭据随每个请求一起发送到请求标头中。这里的用户名和密码未加密,而是使用一个:符号将用户名和密码串联在一起,形成单个字符串:username:password,再使用 base64 编码这个字符串。它适用于 API 调用以及不需要持久会话的简单身份验证工作流。显然,采用这种技术是很容易被攻击的,因为base64 编码的字符串以纯文本格式发送,可以轻松解码。HTTP还提供了摘要认证技术(HTTP Digest Auth),它的密码以 MD5 哈希形式代替纯文本形式发送的,因此更加安全。验证时,服务器生成一个随机值(称为随机数,nonce),并发回一个 HTTP 401 未验证状态,带有一个WWW-Authenticate标头(其值为Digest)以及随机数。WWW-Authenticate标头使浏览器显示用户名和密码输入框。用户输入凭据后,系统将对密码进行哈希处理,然后与每个请求的随机数一起在标头中发送。最后服务器使用用户名获取密码,将其与随机数一起哈希,然后验证哈希是否相同。上述方法都有一个特点,那就是无状态,服务器不保存用户信息,而是通过随请求发来的凭据来验证用户身份,这一点和JWT十分类似。
会话验证是一种用户状态存储在服务器上的身份验证技术,我在前文的新技术概述部分对它进行过介绍。它不需要用户在每个请求中提供用户名或密码,而是在登录后由服务器验证凭据。如果凭据有效,它将生成一个会话,并将其存储在一个会话存储中,然后将其会话的ID 发送回浏览器。浏览器将这个ID 存储为 cookie,该 cookie 可以在向服务器发出请求时随时发送。与JWT不同,基于会话的身份验证是有状态的。每次客户端请求服务器时,服务器必须将会话放在内存中,以便将ID 绑定到关联的用户。
一次性密码(One Time Password,OTP)通常用作身份验证的确认。OTP 是随机生成的代码,可用于验证用户是否是他们声称的身份。它通常用在启用双因素身份验证的应用中,在用户凭据确认后使用。现代 OTP 是无状态的,可以使用多种方法来验证它们。尽管有几种不同类型的 OTP,但基于时间的 OTP(TOTP)可以说是最常见的类型。它们生成后会在一段时间后过期。TOTP的工作流程是:客户端发送用户名和密码。经过凭据验证后,服务器会使用随机生成的种子生成随机代码,并将种子存储在服务端,然后将代码发送到受信任的系统(经过验证的电子邮件或手机号码等)。用户在受信任的系统上获取代码,然后将其输入回 Web 应用。最后服务器使用存储的种子验证代码,确保其未过期,并相应地授予访问权限。OTP与JWT较为相似,但是它使用受信任的系统,添加了一层额外的保护,从而更加安全。

应用领域解决方案

JWT被广泛应用于各个厂商的软件产品中。比如,Google Cloud的API Gateway就使用了JWT技术。API Gateway是一个分布式API管理系统,可以通过在所有服务之间保持一致且定义明确的 REST API 来安全地访问各种服务,而不考虑服务实现。API Gateway支持使用 JWT 对用户进行身份验证。具体做法是将身份验证代码添加到客户端应用,客户端将HTTP 请求的授权标头中的JWT发送给后端,API Gateway 使用 JWT 颁发者的JSON Web密钥集(JWKS)高效地验证 JWT。此外,阿里云的网盘与相册服务(PDS)也支持JWT应用。用户可以在PDS 控制台创建自定义域和JWT应用,利用RSA算法创建一对公私钥,将公钥保存到PDS服务端,私钥保存到JWT应用服务端。JWT应用服务端将数据进行编码并用私钥进行签名生成JWT字符串,然后发送给PDS服务端。PDS服务端使用公钥验证JWT字符串合法后,返回access_token给JWT应用服务端,JWT应用服务端可以通过access_token来调用PDS服务端提供的API。
可以看到,JWT主要用于访问远程服务时的身份验证,但不同应用验证JWT的方法可能会有一些不同,就像上面的例子中,API Gateway使用JWKS验证JWT,而PDS使用RSA算法和公私钥进行验证。

对于程序员来说,写技术博客是十分必要的。今天我按照网上的教程,成功搭建了属于自己的博客网站,并部署在Github上,喜悦之情无以言表。这种凭借一己之力开创新事物的感觉仿佛让我回到了数年前,那时我写出了人生中第一个程序,也就是著名的”Hello World“。当看到终端上成功输出这句简单的英文时,我感到计算机世界的大门已向我徐徐打开。
如今,我接触到了更多的项目,更复杂的技术。然而,我的初心却从未改变。
一切正在开始 …… 不,一切已经开始!

0%