codecat blog

哈希表

哈希表的概念

散列表也叫哈希表（Hash table），是根据关键字（key）而直接访问在内存存储位置的数据结构。

在很多高级语言中都有哈希表的身影，比如在Python中，有一种数据结构叫做dict，中文翻译是字典，应该是基于哈希表实现的。下面以生活中查电话号码作为一个通俗的例子，讲解什么是哈希表。

一个例子理解哈希表

可以把哈希表想象成一本按照人名首字母顺序排列电话簿，当我们要查找张三的电话号码时，可以轻易得知张三的首字母是Z。理想情况下，张三可能在电话簿Z开头的第一个，不理想的情况下，可能要往后再找几个人。

显然，根据姓名首字母查找电话，要比挨个查找快很多，这就是哈希表的特点，快。

人名首字母顺序排列电话簿：

与上面例子所对应的哈希表相关名词:

1. 哈希表：电话簿
2. 关键字(key)：姓名，如张三
3. 哈希函数(F)：计算姓名的首字母的方法，参数是姓名，返回是对应的首字母
4. 哈希地址：哈希函数的返回值，例子中，可以将A-Z理解为哈希地址

什么是冲突

对于不同关键词，经过哈希函数的计算，可能得到同一哈希地址。比如，尽管奔波儿灞(key1)和灞波儿奔(key2)是不同的名字（key1≠key2）但经过哈希函数计算得到的是同一结果(F(key1)=F(key2)=B)，他们名字的首字母都是B。这种情况就叫做冲突。

解决冲突的方法

解决冲突的方法有很多种，比如开放地址法和链地址法，可以根据具体使用场景来选择。一般来说，在实际项目和开发中采用链地址法比较多。

链地址法的基本思路是，把相同哈希地址的关键字放在同一个链表中。

采用链地址法解决冲突的哈希表，可以理解为数组和链表的组合。在上图中，存放首字母的是一个长度为26的数组，而数组的每一个元素可以看作是一个单链表，链表的数据域存放着姓名，指针域指向下一个存放相同首字母的姓名的节点。

字典的设计

上面我们对哈希表有了一个大概的了解，接下来设计并实现一个字典(dict)，在这个字典中，可以存放键值对，也可以根据键(key)获取对应的值(val)。

1. 基本思想：采用链地址法，用定长数组(Array) + 单链表的方式表示字典，假定数组长度为SIZE，初始化状态的哈希表是一个元素全为0的数组。
2. 存键值对：给定一个键值对(key1, val1)，通过哈希函数F计算得到哈希值(hash_code)，也即hash_code1 = F(key1)。然后，通过hash_code1 % SIZE得到地址(由于是在数组中的位置，这里用Array[index]表示)，取模操作是为了确保该地址在数组地址的范围内。接着，新建一个单链表节点（节点1），指针域next为NULL，数据域存放key1和val1。最后，在Array[index]中存放指向节点1的指针。
3. 发生冲突：给定一个键值对(key2, val2)，key2≠key1，如果通过哈希函数计算，hash_code2 = hash_code1，那么将得到同一个地址Array[index]，此时发生冲突，因为数组此位置中已经存放了指向节点1的指针。
4. 解决冲突: 新建一个单链表节点（节点2），数据域保存key2和val2，指针域next为NULL。让节点1的next指针指向节点2即可解决冲突，这就是链地址法，也叫拉链法，后面的冲突，继续使用此方法解决即可。
5. 更新操作：在前面我们插入了键值对(key1, val1), 如果在此基础上又需要插入新的键值对(key1, val0),其中val0≠val1，就需要进行更新操作。有两种方法，第一种是直接将此键值的节点作为数组对应位置的第一个节点，第二种是在对应数组位置找到key=key1的节点，然后更新其val指针。
6. 查字典：给定一个key，查val。首先要计算出地址Array[index] = F(key) % SIZE，如果有数据，此地址会存放一个指向单链表节点的指针，接着对比该指针指向的节点的数据域key是否与要查找的key相等。理想情况下是相等的，但由于冲突的存在，可能需要沿着节点的next指针往下找，也因此，哈希算法的时间复杂度并没有O(1)。找到数据后，返回即可。如果没数据，Array[index]=0，返回NULL。

字典的表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/* 字典类型 */
#define DICT_TYPE_INT 0
#define DICT_TYPE_STR 1

typedef struct dict_entry 
{
    struct dict_entry *next;
    void *key;
    void *val;
}dict_entry;

typedef struct dict 
{
    /* 哈希函数 */
    unsigned int (*hash)(void *key);
    /* table数组用于存放dict_entry指针 */
    dict_entry **table;
    /* table数组的长度 */
    int size;
    /* 掩码（size-1） */
    int sizemask;
}dict;

首先看dict_entry结构体，它有三个成员，分别用来表示后继节点next指针和键与值，用以表示单链表的节点。

接着是dict结构体，用来表示字典本身。

1. hash：对于不同类型的键，比如整型或字符数组（字符串），需要用不同的hash函数来处理，该成员是指针函数，指向该字典的hash函数。

2. table：注意，该成员table是一个数组，用来存放dict_entry类型的指针。可以用dict_entry* table[size]来辅助理解。

3. size：table数组的长度。

4. sizemask：掩码，用于通过与运算来计算数组索引。通常sizemask = size-1， 给定一个数x, x % size 等价于 x & sizemask。与运算可能会比模运算更快，所以选择前者。

   字典的结构：

函数清单

下面是用于操作队列的函数名及其作用与复杂度

哈希函数的选择

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

/* 哈希函数(适用整数) */
static unsigned int hash_integer(void *key)
{
    return (*(int *)key * 2654435769) >> 28;
}

/* 哈希函数 TIME33 算法 (适用字符串)*/
static unsigned int hash_33(void *key)
{
    unsigned int hash = 0;
    while (*(char *)key != 0)
    {
        /* 左移5位相当于*32，再+hash则相当于*33; */
        hash = (hash << 5) + hash + *(char *)key++;
    }
    return hash;
}

哈希函数是一种映射关系，构造哈希函数是一个数学问题，方法也很多，总的来说，要尽量减少冲突，地址尽量分布的均匀。

这里我们选择一个简单的用于计算整数哈希值的函数，以及用于计算字符串哈希的TIME33算法。

哈希表的创建

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

/* 创建一个dict */
dict *dict_create(int type)
{
    dict *dict = (struct dict *)malloc(sizeof(struct dict));
    if(dict == NULL) return NULL;
    if(type == DICT_TYPE_INT)
        dict->hash = &hash_integer;
    else
        dict->hash = &hash_33;
    dict->size = 1024;
    dict->sizemask = dict->size - 1;
    /* 为数组申请内存 */
    dict->table = (dict_entry **)malloc(sizeof(dict_entry *) *(dict->size));
    if (dict->table == NULL) return NULL;
    /* 数组元素全部置零 */
    memset(dict->table, 0, sizeof(dict_entry *) * (dict->size));
    return dict;
}

函数接受一个参数type，用以下面判断字典的类型，从而确定对应的hash函数。然后是设置字典的大小，并为table数组申请内存，然后table所有元素置0，代表数组该位置为空。最后返回该新建的字典。

创建dict_entry

1
2
3
4
5
6
7
8
9
10

/* 创建一个dict_entry */
dict_entry * dict_create_entry(void *key, void *val)
{
    dict_entry * entry = (dict_entry *)malloc(sizeof(dict_entry));
    if(entry == NULL) return NULL;
    entry->key = key;
    entry->val = val;
    entry->next = NULL;
    return entry;
}

创建一个dict_entry,也即是单链表的节点。这里接受俩void类型指针为参数，使得字典可以保存各类数据。

字典插入键值对

第一种方法：

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

/* 字典插入一个键值对 */
dict *dict_put_head_entry(dict *dict, void *key, void *val)
{
    unsigned int hash = dict->hash(key);
    int pos = hash & dict->sizemask;

    dict_entry *entry;
    entry = dict_create_entry(key, val);

    entry->next =  dict->table[pos];
    dict->table[pos] = entry;

    return dict;
}

这种方法简单有效，无论是新增、冲突或者更新操作，都以要插入的键值对生成的新结点作为对应数组位置的第一个节点。

新增和冲突，本质都是链表插入，使用此方法时，更新并非实质更新。

由于新结点作为对应数组位置的第一个节点，这就导致旧数据（相同key的节点）排列在新结点之后，而查询时，是从数组对应位置链表的第一个节点开始查找，所以总是先查找到新的键值对。

优缺点：

• 优点，操作简单、优雅，插入效率高，无需遍历链表和计算每个节点key的hash值。
• 缺点，旧节点还存留在该链表中，所以多占了点内存。

值得一提的是，Redis的dcit在插入键值对时，就使用了该方法。

第二种方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

/* 字典插入一个键值对 */
dict *dict_put_entry(dict *dict, void *key, void *val)
{
    unsigned int hash = dict->hash(key);
    int pos = hash & dict->sizemask;
    dict_entry *entry, *current;
    /* 新增 */
    if(dict->table[pos]==0){
        printf("新增\\\\n");
        entry = dict_create_entry(key, val);
        dict->table[pos] = entry;
    } else {
        current = dict->table[pos];

        /* 首先判断第一个节点是否符合更新的情况 */
        if(dict->hash(current->key) == dict->hash(key)) {
            printf("更新\\\\n");
            current->val = val;
            return dict;
        }

        /* 如果不符合，往下找，直到找到hash值相等的key的节点，则更新，
         * 或者直到next==NULL，此时新增在链表尾部。 */
        while(current->next != NULL) {
            printf("往下找\\\\n");
            if(dict->hash(current->next->key) == dict->hash(key)) {
                printf("更新\n");
                current->next->val = val;
                return dict;
            };
            current = current->next;
        }

        printf("尾部插入\n");
        entry = dict_create_entry(key, val);
        current->next = entry;
    }
    return dict;
}

这个方法可以参考上文提到的字典的设计，优点是利用内存更加少一点，缺点就是不够优雅，增加了算法复杂度。

在调试和测试时，可以将dict->size设置为1，进而观察新增、更新、冲突等情况。

查字典

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

/* dict获取值 */
void * dict_get_value(dict *dict, void *key)
{
    unsigned int hash = dict->hash(key);
    int pos = hash & dict->sizemask;
    if(dict->table[pos]==0) return NULL;
    dict_entry *current = dict->table[pos];
    while (current)
    {
        if(dict->hash(current->key) == dict->hash(key))
            return current->val;
        else
            current = current->next;
    }
    return NULL;
}

查字典就是给定一个key，查对应的val。

参考上文提到的字典的设计。

字典的清除与释放

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

/* 清除dict所有entry，而不清除dict本身 */
void dict_empty(dict *dict)
{
    int i;
    for(i=0;i<dict->size;i++){
        if(dict->table[i] != 0){
            dict_entry * current, *next;
            current = dict->table[i];
            while (current)
            {
                next = current->next;
                free(current);
                current = next;
            }
            dict->table[i] = 0;
        }
    }
}

/* 释放dict */
void dict_release(dict *dict)
{
    dict_empty(dict);
    free(dict->table);
    free(dict);
}

在清除dict所有entry，而不清除dict本身时，只需要遍历table数组，发现不为0的元素时再遍历清除对应的链表即可。

释放dict的操作，只需要释放所有entry后，再释放dict本身即可。

在main函数中测试

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

int main ()
{
	dict *dict = dict_create (DICT_TYPE_STR);

	char str_name[] = "name";
	char str_person1[] = "codecat";
	char str_person2[] = "codepig";
	char str_age[] = "age";
	int age = 26;

	dict_put_entry (dict, &str_person1, &str_person1);
	puts (dict_get_value (dict, &str_person1));

	dict_put_entry (dict, &str_name, &str_person1);
	puts (dict_get_value (dict, &str_name));

	dict_put_entry (dict, &str_name, &str_person2);
	puts (dict_get_value (dict, &str_name));

	dict_put_entry (dict, &str_age, &age);
	printf ("age: %d\\n", *( int * ) dict_get_value (dict, &str_age));

	dict_empty (dict);
	dict_release (dict);
}

测试时，插入键值对我使用的是第二种方法，此外我还将dict中的size设置为1，这样table中就一个位置，方便观察插入、更新、冲突时，链表的变化。

前言：

我们刚开始学习C 时，都是使用iostream里面的cin和cout进行控制台的输入和输出，现在我们学习如何从文件读取流和向文件写入流。

IO: 向设备输入数据和输出数据

C 的文件流：

设备:

文件 控制台 特定的数据类型(stringstream) c 中,必须通过特定的已经定义好的类, 来处理IO(输入输出)

欲要使用文件流，这就需要用到 C 中的标准库 #include < fstream >，它定义了三个数据类型： ofstream：该数据类型表示输出文件流，用于创建文件并向文件写入信息。 ifstream：该数据类型表示输入文件流，用于从文件读取信息。 fstream：该数据类型表示输入和输出文件流，且同时具有 ofstream 和 ifstream 两种功能，这意味着它可以创建文件，向文件写入信息，从文件读取信息。

定义文件流

想要使用文件流对文件进行操作，修必须要先定义它。 定义时须包含头文件#include< fstream >

三种定义方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <fstream>

using namespace std;	// 声明命名空间

int main(void) {
	// 1》
	// 声明输出文件流，用于创建文件并向文件写入信息。
	ofstream outFile;

	// 2》
	// 声明输入文件流，用于从文件读取信息。
	ifstream inFIle;

	// 3》
	// 声明输入和输出文件流，且同时具有 ofstream 和 ifstream 两种功能，这意味着它可以创建文件，向文件写入信息，从文件读取信息。
	fstream stream;

	return 0；
}

打开文件

在从文件读取信息或者向文件写入信息之前，必须先打开文件。ofstream 和fstream 对象都可以用来打开文件进行写操作，如果只需要打开文件进行读操作，则使用 ifstream 和 fstream对象。

打开文件的方法： 使用open()函数进行文件的打开

#include < fstream > void open( const char *filename );

例1：ofstream打开文件的方式（写数据进文件中）

1
2

ofstream outFile;
outFile.open("demo.txt");		// 默认方式打开文件

例2：ifstream打开文件的方式（读取文件中的数据）

1
2

ifstream inFile;
inFile.open("demo.txt");		// 默认当方式打开文件

例3： fstream打开文件的方式（读写文件中的数据）

1
2

fstream stream
stream.open("demo.txt");		// 默认方式打开文件

文件的打开方式

1
2
3
4
5
6
7
8

模式标志	描述
ios::in	读方式打开文件
ios::out	写方式打开文件
ios::trunc	如果此文件已经存在, 就会打开文件之前把文件长度截断为0
ios::app	尾部最加方式(在尾部写入)
ios::ate	文件打开后, 定位到文件尾
ios::binary	二进制方式(默认是文本方式)
以上打开方式， 可以使用位操作 | 组合起来

例： 如果你只是想对文件进行写入操作，当文件已经存在时，你希望对该文件进行截断操作，那么就可这样组合：

1
2

fstream stream;
stream.open("demo.txt", ios::out | ios::trunc);

如果你只是想对文件进行读取操作，而且想在文件尾部读取，那么就可以这样组合：

1
2

fstrem inFile;
inFile.open("demo.txt", ios::in | ios::ate);

判断文件是否打开成功 使用is_open()函数进行文件的判断 当成功打开文件返回真（true），失败返回假（false）

例：

1
2
3
4
5
6
7
8
9

fstream stream;

stream.open("demo.txt");
// 判断文件是否打开成功
if (!stream.is_open()) {
cout << "文件打开失败！" << endl;
system("pause");
exit(-1);
}

关闭文件

使用close()函数进行关闭文件 函数的作用是:关闭相关的文件流。

例：

1
2
3
4
5
6
7
8

// 定义文件流
fstream stream;
// 打开文件
stream.open("demo.txt");
// 关闭文件
stream.close();

我们要养成好习惯，打开文件后，一定义要关闭文件再结束程序。

写文件

在C 中，写文件除了要用到ofstream 或者 fstream 外，我们还需要用到一个流插入运算符（<<）。

例：

需求： 让用户来输入姓名和年龄，并保存到文件中。 直到用户输入ctrl z

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

/*
需求：
让用户来输入姓名和年龄，并保存到文件中。
直到用户输入ctrl z
*/

#include <iostream>
#include <Windows.h>
#include <string>
#include <fstream>

// 写文件
using namespace std;

int main(void)
{
	string name;
	int age;
	ofstream outfile;	// 定义写文件流

	// 打开文件
	outfile.open("text.txt", ios::out | ios::trunc);
	if (!outfile.is_open()) {	// 判断文件是否打开失败
		cout << "文件打开失败！" << endl;
		system("pause");
		exit(-1);
	}

	while (true) {
		cout << "请输入姓名：";
		cin >> name;

		if (cin.eof()) {
			break;
		}
		
		// *******************************
		outfile << name << "\\t";		// 将从键盘读取的数据写入文件中
		// *******************************

		cout << "请输入年龄：";
		cin >> age;

		// 将从键盘读取的数据写入文件中
		outfile << age << endl;

		// 可以连环写入文件
		// outfile << name << "\\t" << age << endl;
	}

	// 关闭文件
	outfile.close();
	system("pause");
	return 0;
}

读文件

在C 中，读文件除了要用到ifstream 或者 fstream 外，我们还需要用到一个流插入运算符（>>）。

例： 需求： 在上一个写入文件的例子中，把它写入的text.txt文件中的所有内容都读取出来，并打印出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <iostream>
#include <Windows.h>
#include <string>
#include <fstream>

// 读文件
using namespace std;

int main(void) {
	ifstream inFile;
	string name;
	int age;

	// 打开文件
	inFile.open("text.txt");
	if (!inFile.is_open()) {	// 判断文件是否打开失败
		cout << "文件打开失败！" << endl;
		system("pause");
		exit(-1);
	}

	while (1) {
		// 从文件中读取第一个数据，并将其打印出来
		inFile >> name;
		if (inFile.eof()) {
			break;
		}
		cout << name << "\\t";

		// 从文件读取第二数据，并将其打印出来
		inFile >> age;
		cout << age << endl;
	}

	system("pause");
	inFile.close();
	return 0;
}

读取文件中的一行数据

使用getline()可以读取文件中的一行数据

例：

1
2
3
4
5
6
7

stream inFile;
string line;

inFile("text.txt");

// 从文件中读取一行数据，并将读取到的数据写入字符串变量line中
getline(inFile, line);

好了，这就是文件的基本用法，C 文件并不难，只要理解好，读取文件要用到搞混文件流，写入文件要用到哪个文件流；需要用到什么方式打开文件等等。不要搞混。

个人博客

这是一个天坑转行，游戏菜鸡的个人博客。

随心写一点学习日记，生活点滴以及游戏攻略。

1 简介
　　SSH（安全外壳协议，Secure Shell 的缩写）由 IETF 的网络小组（Network Working Group）所制定，是建立在应用层基础上的安全协议。SSH 是目前较可靠，专为远程登录会话和其他网络服务提供安全性的协议，利用 SSH 协议可以有效防止远程管理过程中的信息泄露问题。SSH 最初是 UNIX 系统上的一个程序，后来又迅速扩展到其他操作平台。SSH 客户端适用于多种平台，几乎所有 UNIX 平台都可运行 SSH。

2 作用
　　传统的网络服务程序，如：FTP、POP 和 Telnet 在本质上都是不安全的，因因为它们在网络上用明文传送口令和数据，别有用心的人非常容易就可以截获这些口令和数据。而且，这些服务程序的安全验证方式也是有其弱点的， 就是很容易受到“中间人攻击”（Man-in-the-middle attack）。

    所谓“中间人攻击”， 就是“中间人”冒充真正的服务器接收你传给服务器的数据，然后再冒充你把数据传给真正的服务器。服务器和你之间的数据传送被“中间人”一转手做了手脚之后，就会出现很严重的问题。通过使用 SSH，你可以把所有传输的数据进行加密，这样”中间人”这种攻击方式就不可能实现了，而且也能够防止 DNS 欺骗和 IP 欺骗。使用 SSH，还有一个额外的好处就是传输的数据是经过压缩的，所以可以加快传输的速度。

3 层次

SSH 主要由三部分组成：传输层协议 [SSH-TRANS]、用户认证协议 [SSH-USERAUTH] 和连接协议 [SSH-CONNECT] 组成。

  传输层协议 [SSH-TRANS]：提供了服务器认证，保密性及完整性。此外它有时还提供压缩功能。 SSH-TRANS 通常运行在 TCP/IP 连接上，也可能用于其它可靠数据流上。 SSH-TRANS 提供了强力的加密技术、密码主机认证及完整性保护。该协议中的认证基于主机，并且该协议不执行用户认证。更高层的用户认证协议可以设计为在此协议之上。

    用户认证协议 [SSH-USERAUTH]：用于向服务器提供客户端用户鉴别功能，它运行在传输层协议 SSH-TRANS 上面。当 SSH-USERAUTH 开始后，它从低层协议那里接收会话标识符，会话标识符唯一标识此会话并且适用于标记以证明私钥的所有权。 SSH-USERAUTH 也需要知道低层协议是否提供保密性保护。

    连接协议 [SSH-CONNECT]：将多个加密隧道分成逻辑通道。它运行在用户认证协议上。它提供了交互式登录话路、远程命令执行、转发 TCP/IP 连接和转发 X11 连接。

4 用法

4.1 基本操作

SSH 主要用于远程登录。假定我们要以用户名user登录远程主机host，只要一条简单命令就可以啦！

1

$ ssh user@host

如果本地用户名与远程用户名一致，登录时可以省略用户名。

1

$ ssh host

SSH 的默认端口是22，也就是说，我们的登录请求会送进远程主机的22端口。使用p参数，可以修改这个端口。

1

$ ssh -p 2222 user@host

上面这条命令表示，SSH 直接连接远程主机的2222端口。

4.2 口令登录

如果我们是第一次登录对方主机，系统会出现下面的提示：

1
2
3
4

$ ssh user@host
The authenticity of host 'host (12.18.81.21)' can't be established.
RSA key fingerprint is 98:2e:d7:e0:de:9f:ac:67:28:c2:42:2d:37:16:58:4d.
Are you sure you want to continue connecting (yes/no)?

这段话的意思是，无法确认 host 主机的真实性，只知道它的公钥指纹，问你还想继续连接吗？

所谓”公钥指纹”，是指公钥长度较长（这里采用 RSA 算法，长达 1024 位），很难比对，所以对其进行 MD5 计算，将它变成一个 128 位的指纹。上例中是98:2e:d7:e0:de:9f:ac:67:28:c2:42:2d:37:16:58:4d，再进行比较，就容易多啦！很自然想到的一个问题就是，用户怎么知道远程主机的公钥指纹应该是多少？回答是没有好办法，远程主机必须在自己的网站上贴出公钥指纹，以便用户自行核对。假定经过风险衡量以后，用户决定接受这个远程主机的公钥。

1

Are you sure you want to continue connecting (yes/no)? yes

系统会出现一句提示，表示 host 主机已经得到认可。

1

Warning: Permanently added 'host,12.18.429.21' (RSA) to the list of known hosts.

然后，会要求输入密码。

1

Password: (enter password)

如果密码正确，就可以登录了。

当远程主机的公钥被接受以后，它就会被保存在文件$HOME/.ssh/known_hosts之中。下次再连接这台主机，系统就会认出它的公钥已经保存在本地了，从而跳过警告部分，直接提示输入密码。每个 SSH 用户都有自己的known_hosts文件，此外系统也有一个这样的文件，通常是/etc/ssh/ssh_known_hosts，保存一些对所有用户都可信赖的远程主机的公钥。

4.3 公钥登录

   使用密码登录，每次都必须输入密码，非常麻烦。好在 SSH 还提供了公钥登录，可以省去输入密码的步骤。

    所谓”公钥登录”，原理很简单，就是用户将自己的公钥储存在远程主机上。登录的时候，远程主机会向用户发送一段随机字符串，用户用自己的私钥加密后，再发回来。远程主机用事先储存的公钥进行解密，如果成功，就证明用户是可信的，直接允许登录 shell，不再要求密码。这种方法要求用户必须提供自己的公钥。如果没有现成的，可以直接用ssh-keygen生成一个：

1

$ ssh-keygen

运行上面的命令以后，系统会出现一系列提示，可以一路回车。其中有一个问题是，要不要对私钥设置口令（passphrase），如果担心私钥的安全，这里可以设置一个。运行结束以后，在$HOME/.ssh/目录下，会新生成两个文件：id_rsa.pub和id_rsa。前者是你的公钥，后者是你的私钥。这时再输入下面的命令，将公钥传送到远程主机 host 上面：

1

$ ssh-copy-id user@host

好了，从此我们再登录，就不需要输入密码了。如果还是不行，就打开远程主机的/etc/ssh/sshd_config这个文件，检查下面几行前面#注释是否取掉。

1
2
3

RSAAuthentication yes
PubkeyAuthentication yes
AuthorizedKeysFile .ssh/authorized_keys

然后，重启远程主机的 SSH 服务。

1
2
3
4

/* ubuntu系统 */
service ssh restart
/* debian系统 */
/etc/init.d/ssh restart

4.4 authorized_keys文件

远程主机将用户的公钥，保存在登录后的用户主目录的$HOME/.ssh/authorized_keys
文件中。公钥就是一段字符串，只要把它追加在authorized_keys文件的末尾就行了。这里不使用上面的ssh-copy-id命令，改用下面的命令，解释公钥的保存过程

1

$ ssh user@host 'mkdir -p .ssh && cat >> .ssh/authorized_keys' < ~/.ssh/id_rsa.pub

这条命令由多个语句组成，依次分解开来看：

• $ ssh user@host，表示登录远程主机；
• 单引号中的mkdir .ssh && cat >> .ssh/authorized_keys，表示登录后在远程 Shell 上执行的命令：
• $ mkdir -p .ssh”的作用是，如果用户主目录中的.ssh`目录不存在，就创建一个；
• cat >> .ssh/authorized_keys < /.ssh/id_rsa.pub的作用是，将本地的公钥文件/.ssh/id_rsa.pub，重定向追加到远程文件authorized_keys的末尾。

写入authorized_keys文件后，公钥登录的设置就完成啦！

4.5 绑定本地端口

    既然 SSH 可以传送数据，那么我们可以让那些不加密的网络连接，全部改走 SSH 连接，从而提高安全性。假定我们要让`8080`端口的数据，都通过 SSH 传向远程主机，命令就这样写：

1

$ ssh -D 8080 user@host

  SSH 会建立一个 Socket，去监听本地的`8080`端口。一旦有数据传向那个端口，就自动把它转移到 SSH 连接上面，发往远程主机。可以想象，如果`8080`端口原来是一个不加密端口，现在将变成一个加密端口。

4.6 本地端口转发

   有时，绑定本地端口还不够，还必须指定数据传送的目标主机，从而形成点对点的”端口转发”。为了区别后文的”远程端口转发”，我们把这种情况称为“本地端口转发（Local forwarding）”。

    假定 host1 是本地主机，host2 是远程主机。由于种种原因，这两台主机之间无法连通。但是，另外还有一台 host3，可以同时连通前面两台主机。因此，很自然的想法就是：通过 host3，将 host1 连上 host2。我们在 host1 执行下面的命令

1

$ ssh -L 2121:host2:21 host3

   命令中的L参数一共接受三个值，分别是本地端口:目标主机:目标主机端口，它们之间用冒号分隔。这条命令的意思，就是指定 SSH 绑定本地端口2121，然后指定 host3 将所有的数据，转发到目标主机 host2 的21端口（假定 host2 运行 FTP，默认端口为21）。这样一来，我们只要连接 host1 的2121端口，就等于连上了 host2 的21端口。

1

$ ftp localhost:2121

“本地端口转发”使得 host1 和 host3 之间仿佛形成一个数据传输的秘密隧道，因此又被称为”SSH 隧道”。下面是一个比较有趣的例子。

1

$ ssh -L 5900:localhost:5900 host3

它表示将本机的5900端口绑定 host3 的5900端口（这里的 localhost 指的是 host3，因为目标主机是相对 host3 而言的）。另一个例子是通过 host3 的端口转发，SSH 登录 host2。

1

$ ssh -L 9001:host2:22 host3

这时，只要 SSH 登录本机的9001端口，就相当于登录 host2 了。

1

$ ssh -p 9001 localhost

上面的-p参数表示指定登录端口。

4.7 远程端口转发

   既然”本地端口转发”是指绑定本地端口的转发，那么“远程端口转发（Remote forwarding）”当然是指绑定远程端口的转发。

    还是接着看上面那个例子，host1 与 host2 之间无法连通，必须借助 host3 转发。但是，特殊情况出现了，host3 是一台内网机器，它可以连接外网的 host1，但是反过来就不行，外网的 host1 连不上内网的 host3。这时，本地端口转发就不能用了，怎么办？

     解决办法是，既然 host3 可以连 host1，那么就从 host3 上建立与 host1 的 SSH 连接，然后在 host1 上使用这条连接就可以了。我们在 host3 执行下面的命令：

1

$ ssh -R 2121:host2:21 host1

    R参数也是接受三个值，分别是远程主机端口:目标主机:目标主机端口。这条命令的意思，就是让 host1 监听它自己的2121端口，然后将所有数据经由 host3，转发到 host2 的21端口。由于对于 host3 来说，host1 是远程主机，所以这种情况就被称为远程端口绑定。绑定之后，我们在host1就可以连接 host2 了：

1

$ ftp localhost:2121

4.8 SSH的其他参数

    SSH 还有一些别的参数，也值得介绍。`N`参数，表示只连接远程主机，不打开远程 Shell；`T`

参数，表示不为这个连接分配 TTY。这个两个参数可以放在一起用，代表这个 SSH 连接只用来传数据，不执行远程操作。

1

$ ssh -NT -D 8080 host

f参数，表示 SSH 连接成功后，转入后台运行。这样一来，你就可以在不中断 SSH 连接的情况下，在本地 Shell 中执行其他操作。

1

$ ssh -f -D 8080 host

要关闭这个后台连接，只能用kill
命令去杀掉进程。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment