Redis_dict

发表于2021-07-30更新于2025-09-28阅读次数

引例

图书馆借书问题，图书馆有成千上万本图书，最初，需要有一个本子记录哪一天学生记录的情况。最初以日期为编号记录某一天来借书的情况。当有人来还书时，需要先问清借书者是几号来借的，然后还要在这天的记录里依次找到具体信息。如果借书者清楚自己是几号借的还好说，但是如果不记得了呢？比如说他只记得好像是上上个月来借的，那么就需要一天一天的从头到尾查找记录，显然效率是低下的。
image-20210807233939705
那么我们可以如此改进：我们搞一个000 0000 0000 ~ 199 9999 9999页的本子，某同学借书时让他提供电话号码，以电话号码为基准记录信息。待还书时，只需要报电话号则可以直接找到记录。但此方法不现实，因为本子太厚，要花费的空间太大。
image-20210807234740133
再改进：做一个1000页的本子，因为电话号码的范围远远大于页数，我们要想办法使电话号码映射到页数，则这个映射方案则称为“哈希函数”。如A同学电话号码为137 3456 9090，可取后三位090，存到90页。B同学电话号码为186 7890 1234，取后三位234，存到234页。
image-20210807235252067
此时又来了一个C同学，电话号码为156 9090 1234，虽然关键码与B同学不一样，但位置信息一样，则称之为“哈希冲突”。

哈希表

什么是哈希表

严蔚敏版本的数据结构教材中指出，在诸如线性表、树结构中，“记录”中结构中的相对位置是随机的，和“记录”的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。比如，数组存放的从小到大的10个数据，要用二分查找法找出某value的下标值就需要一直探测。这一类查找方法建立在“比较”的基础上。在顺序查找时，比较的结果为“=”与“≠”两种可能；在折半查找、二叉排序树查找和B树查找时，比较的结果为“<”、“=”和“>”3种可能。查找的效率依赖于查找过程中所进行的比较次数。

我们所向往的理想的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个惟一的存储位置相对应。因而在查找时只要根据这个对应关系f找到给定值K的“像”f(K)便能找到其存储位置。若结构中存在关键字和K相等的记录，则必定在f(K)这个存储位置上，由此不需要比较便可直接取得所查记录。在此我们称这个对应关系f为哈希（Hash）函数，由此思想建立的表称为哈希表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
#include<assert.h>
#define NIL -1
#define m 13
typedef int KeyType;
struct ElemType
{
  	KeyType key;
    void* ptr;	//value
};
typedef struct
{
    ElemType data[m];
    int cursize;
}HashTable;

image-20210808011308669

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
void Init_HashTable(HashTable* pt)
{
    assert(pt != nullptr);
    pt->cursize = 0;
    for(int i=0;i<m;++i)
    {
        pt->data[i].key = NIL;
        pt->data[i].ptr = nullptr;
    }
}
int Hash(KeyType kx)
{
    return kx%m;
}
bool Insert_Item(HashTable* pt, ElemType item)
{
    assert(pt != nullptr);
    int index = Hash(item.key);
    pt->data[index] = item;
    pt->cursize += 1;
}
int main()
{
    HashTable ht;
    Init_HashTable(&ht);
    int ar[]={12,23,25,8,19,29};
    int n=sizeof(ar)/sizeof(ar[0]);
    for(int i=0;i<n;++i)
    {
        struct ElemType item = {ar[i],nullptr};
        bool tag = Insert_Item(&ht,item);
    }
}

但是这种Insert_Item函数是有问题的，没有解决哈希冲突问题，比如在插入key为25的元素时会替换掉前期已经插入的key为12的元素。

image-20210808013500159

以下来通过 （增量）线性探测法来解决哈希冲突。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int Inc(int i)
{
    return i;
}
int Hash_Inc(KeyType kx, int i)
{
    return (Hash(kx) + Inc(i))%m;
}
bool Insert_Item(HashTable* pt, ElemType item)
{
    assert(pt != nullptr);
    for(int i = 0;i<m;++i)
    {
        int index = Hash_Inc(item.key, i);
        if(pt->data[i].key == NIL)//随着Inc更迭，找到一个空位置
        {
            pt->data[index] = item;
            pt->cursize += 1;
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    HashTable ht;
    Init_HashTable(&ht);
    int ar[]={12,15,28,23,25,38,36,49,14};
    int n=sizeof(ar)/sizeof(ar[0]);
    for(int i=0;i<n;++i)
    {
        struct ElemType item = {ar[i],nullptr};
        bool tag = Insert_Item(&ht,item);
    }
}

image-20210808015044675

这种线性探测法虽然解决了哈希冲突，但最终的数据分布太堆积化。可以通过平方探测法改善此问题。

1
2
3
4
int Inc(int i)
{
    return i*i;
}

但无论是线性探测法存储还是平方探测法存储，在这种纯顺序表（数组）中实现哈希表会遇到一个严重的问题！即插入数据后，不能轻易删除某一个数据，因为删除了某一数据后，查找另外的数据就会出现数据断层导致不能正常探测。比如下图：如果把3下标的28删除，则查找key为49的元素时，第一次探测49%13=10，23不等于49，第二次探测（线性探测，下标+1），36不等于49，第三次探测，12不等于49，……，直到探测到下标3，发现key值为-1。如果我们停止探测返回，则是错误的；所以我们只能遇到-1不停止继续探测，那么就失去了哈希表的意义，这相当于在查某个key对应的value时有可能把整个表都遍历了一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void* FindValue(HashTable* pt, KeyType kx)
{
    assert(pt != nullptr);
    for(int i = 0;i<m;++i)
    {
        int pos = Hash_Inc(kx,i);
        if(pt->data[pos].key==kx)
        {
            return pt->data[pos].ptr;
        }
        if(pt->data[pos].key==NIL)
        {
            return nullptr;
        }
    }
}

image-20210808020035825

链地址法

所以我们要改变这种存储哈希表的方式，改用链地址法存储。（视频01:27:42）

image-20210808191518194

看图设计结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>
#include<assert.h>
#define m 13
typedef int KeyType;
typedef struct ElemType
{
    KeyType key;
    void* ptr;
}ElemType;
typedef struct HashNode
{
    ElemType data;
    struct HashNode* next;
}HashNode;
typedef struct HashTable
{
    HashNode* table[m];
    int cursize;
}HashTable;

测试代码

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
int Hash(KeyType kx)
{
    return kx % m;
}
void Init_Hash(HashTable* pt)
{
    assert(pt!=nullptr);
    for(int i = 0;i<m;++i)
    {
        pt->table[i] = nullptr;
    }
    pt->cursize = 0;
}
void Insert_Item(HashTable* pt, ElemType item)//但是此函数没有解决存在相同key时的情况
{
    assert(pt!=nullptr);
    int index = Hash(item.key);
    HashNode* s = (HashNode*)malloc(sizeof(HashNode));
    if(nullptr == s) exit(1);
    s->data = item;
    s->next = pt->table[index];
    pt->table[index] = s;
    pt->cursize += 1;
}
int main()
{
    int ar[]={1,55,19,20,10,11,14,68,84,23,27,79};
    int n = sizeof(ar)/sizeof(ar[0]);
    HashTable ht;
    Init_Hash(&ht);
    for(int i = 0;i<n;++i)
    {
        ElemType elem = {ar[i],nullptr};
        Insert_Item(&ht,elem);
    }
}

API

Init

1
2
3
4
5
6
7
8
9
void Init_Hash(HashTable* pt)
{
    assert(pt != nullptr);
    for(int i = 0;i<m;++i)
    {
        pt->table[i]=nullptr;
    }
    pt->cursize=0;
}

Insert

1
2
3
4
5
6
7
8
9
10
11
12
13
void Insert_Item(HashTable* pt, ElemType item)
{
    assert(pt != nullptr);
    int index = Hash(item.key);
    HashNode* pnode = (HashNode*)malloc(sizeof(*pnode));
    if (nullptr == pnode) exit(1);
    pnode->data = item;//讲外部elem封装到新建结点的数据域
    //以下两步为入表操作，采用头插法，时间复杂度为O(1)，不用判头结点是否为空
    pnode->next = pt->table[index];
    pt->table[index] = pnode;
    
    pt->cursize++;//现有大小+1
}

FindNode

查看字典中是否已存在某key值对应的节点并返回。

1
2
3
4
5
6
7
8
9
10
HashNode* FindNode(HashTable* pt, KeyType kx)
{
	int index = Hash(kx);
	HashNode* p = pt->data[index];
	while (p != nullptr && p->item.key != kx)
	{
		p = p->next;
	}
	return p;
}

Clear

自己写的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//free掉所有节点，HashTable的指针数组数据全赋空
void ClearTable(HashTable* pt)
{
	for (int i = 0;i < m;++i)
	{
		HashNode* p = pt->data[i];
		HashNode* q = nullptr;
		while (p)
		{
			q = p->next;
			free(p);
			pt->cursize--;
			p = q;
		}
		pt->data[i] = nullptr;
	}
}

老师写的

1
2
3
4
5
6
7
8
9
10
11
12
13
void ClearHash(HashTable* pt)
{
    for(int i = 0;i<m;++i)
    {
        while(pt->data[i]!=nullptr)
        {
            HashNode* q = pt->data[i];
            pt->data[i]=q->next;
            free(q);
        }
    }
    pt->cursize=0;
}

Remove

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 RemoveNode(HashTable* pt, KeyType kx)
{

	int index = Hash(kx);
	HashNode* p = pt->data[index];
	if (p == nullptr) exit(1);//不存在要删除的key的对应节点，因为Table数组此下标的值既然为空则肯定不会有key值相应的节点存在
	HashNode* q = p->next;
	//若删除的节点为头结点，则特殊处理
	if (p->item.key == kx)
	{
		pt->data[index] = q;
		free(p);
	}
	else//
	{
		while (q != nullptr && q->item.key != kx)
		{
			p = p->next;
			q = q->next;
		}
		if (q == nullptr) exit(1);//不存在要删除的key的对应节点，因为遍历这一条链后不存在相同的key值对应的节点。
		else//q->item.key == kx
		{
			p->next = q->next;
			free(q);
		}
	}
	pt->cursize--;
	return;
}

老师写法

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
//Remove节点更老套的写法：
bool Remove(HashTable* pt,KeyType kx)
{
    assert(pt!=nullptr);
    int index=Hash(kx);
    HashNode* pr=nullptr;//前驱指针
    HashNode* p=pt->table[index];
    while(p!=nullptr)
    {
        if(p->item.key==kx)
        {
            if(pr!=nullptr)
            {
                pr->next=p->next;
            }
            else
            {
                pt->table[index]=p->next;
            }
            free(p);
            pt->total-=1;
            return true;
        }
        pr=p;
        p=p->next;
    }
    return false;
}

习题

定义大小为100 的整型数组，使用随机函数给数组元素赋值。数值的范围是1 … 100 ，并且不容许重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int* My_NonRepeating_RandArr(int* ar, int n)
{
    assert(ar != nullptr);
    int br[101];
    for (int i = 0;i < n + 1;++i)
    {
        br[i]=0;
    }
    int temp;
    srand(time(NULL));
    int i = 0;
    do
    {
        temp = rand() % 100 + 1;
        if (br[temp] != 1)
        {
            br[temp] = 1;
            ar[i] = temp;
            ++i;
        }
    } while (i<n);
    return ar;
}

如果题中数组大小改为1000000，那么数组开辟空间就很大，如果仍然按照旧的方式去做肯定是对程序不利的。考虑用哈希算法解决！

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<stdio.h>
#include<assert.h>
#define m 100
typedef int KeyType;
typedef struct ElemType
{
    KeyType key;
    void* ptr;
}ElemType;
typedef struct HashNode
{
    ElemType data;
    struct HashNode* next;
}HashNode;
typedef struct HashTable
{
    HashNode* table[m];
    int cursize;
}HashTable;
void Init_Hash(HashTable* pt)
{
    assert(pt != nullptr);
    for(int i = 0;i<m;++i)
    {
        pt->table[i]=nullptr;
    }
    pt->cursize=0;
}
void Insert_Item(HashTable* pt, ElemType item)
{
    assert(pt != nullptr);
    int index = Hash(item.key);
    HashNode* pnode = (HashNode*)malloc(sizeof(*pnode));
    if (nullptr == pnode) exit(1);
    pnode->data = item;//讲外部elem封装到新建结点的数据域
    //以下两步为入表操作，采用头插法，时间复杂度为O(1)，不用判头结点是否为空
    pnode->next = pt->table[index];
    pt->table[index] = pnode;
    
    pt->cursize++;//现有大小+1
}
int Hash(KeyType kx)
{
    return kx%m;
}
HashNode* FindValue(HashTable* pt, KeyType kx)
{
    int index = Hash(kx);
    HashNode* p = pt->table[index];
    while(p != nullptr && p->data.key != kx)
    {
        p=p->next;
    }
    return p;
}
int* My_NonRepeating_Hash(int* ar, int n)
{
    assert(ar != nullptr);
    HashTable ht;
    Init_Hash(&ht);
    int temp;
    srand(time(NULL));
    int i = 0;
    do
    {
        temp = rand()* rand() % 1000000 + 1;
        if (FindValue(&ht, temp) == nullptr || *(int*)(FindValue(&ht, temp)->data.ptr) != 1)
        {
            ElemType item = { temp,new int(1) };
            Insert_Item(&ht, item);
            ar[i] = temp;
            ++i;
        }
    } while (i < n);
    return ar;
}
int 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
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<assert.h>
#define m 13
#define INC	2
typedef int KeyType;
typedef struct
{
    KeyType key;
    void* ptr;
}ElemType;
typedef struct HashNode
{
    ElemType data;
    struct HashNode* next;
}HashNode;
typedef struct HashTable
{
    HashNode** table;
    int capacity;
    int total;
}HashTable;
int Hash(HashTable* pt, KeyType kx)
{
    //return kx % m; //原始不考虑增容的情况下默认%m
    return kx % pt->capacity;
}
void Init_Hash(HashTable* pt)
{
    assert(pt!=nullptr);
    pt->table = (HashNode**)malloc(sizeof(HashNode*)*m);
    if(pt->table == nullptr)exit(EXIT_FAILURE);
    pt->capacity = m;
    for(int i = 0;i<pt->capacity;++i)
    {
        pt->table[i] = nullptr;
    }
    pt->total = 0;
}
HashNode* FindNode(HashTable* pt, KeyType kx)
{
    int index = Hash(pt,kx);
    HashNode* p = pt->table[index];
    while(p != nullptr && p->data.key != kx)
    {
        p=p->next;
    }
    return p;
}
bool Inc(HashTable* pt)//对哈希表的增容操作
{
    int incsize = pt->capacity * INC;//INC为增容系数，默认为2，incsize表示增容后的新大小，为此前哈希表容量的2倍。
    HashNode** newtable = (HashNode**)malloc(sizeof(HashNode*)*incsize);
    if(newtable == nullptr)return false;
    for(int i = 0;i<incsize;++i)
    {
        newtable[i] = nullptr;
    }
    pt->captacity = incsize;
    //以上，开辟新的哈希表完毕，下面要把旧表复制到新表
    int oldsize = pt->capacity;
    for(int i = 0;i<oldsize;++i)
    {
        if(pt->table[i]!=nullptr)
        {
            
        }
    }
}
bool Insert_Item(HashTable* pt, ElemType item)
{
    assert(pt!=nullptr);
    HashNode* p = FindNode(pt,item.key);
    if(p!=nullptr)return false;//哈希表中已存在相同key值的节点
    if(pt->total > pt->capacity && !Inc(pt))//需要增容但没有增容成功
    {
        return false;
    }
    int index 
}

C++就一个东西引用返回，B站的老师永远搞不清楚

Redis字典

字典，又称为符号表(symbol table)、关联数组(associative array)或映射(map)，是一种用于保存键值对(key-value pair)的抽象数据结构。
在字典中，一个键(key)可以和一个值(value)进行关联（或者说将键映射为值），这些关联的键和值就称为键值对。
字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对，等等。
字典经常作为一种数据结构内置在很多高级编程语言里面，但Redis所使用的C语言并没有内置这种数据结构，因此 Redis构建了自己的字典实现。
字典在Redis中的应用相当广泛，比如 Redis的数据库就是使用字典来作为底层实现的，对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

与相似结构对比

HashTable是无序的；
Map是有序的；HashMap是无序的，底层有红黑树实现。因此Map效率较低。

字典的实现

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

哈希表

Redis字典所使用的哈希表由dict.h/dictht结构定义：

1
2
3
4
5
6
7
typedef struct dictht
{
    dictEntry** table;//哈希表数组
    unsigned long size;//哈希表大小
    unsigned long sizemark;//哈希表大小掩码，用于计算索引值。总是等于size-1
    unsigned long used;//表中已有节点的数量
}dictht;

成员table的功能是一个数组（指向首元素的指针），数组中的每个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对。

image-20210818030916272

哈希表节点

即dictEntry结构。

1
2
3
4
5
6
7
8
9
10
11
typedef struct dictEntry
{
    void* key;
    union
    {
        void* val;
        uint64_tu64;
        int64_ts64;
    }v;
    struct dictEntry* next;
}dictEntry;

image-20210818031224095

字典

Redis中的字典由dict.h/dict结构表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct dictType 
{
    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;
typedef struct dict
{
    dictType* type;//结构体指针，用于存放特定类型的操作函数
    void* privdata;//私有数据
    dictht ht[2];//内部定义了两个哈希表
    int rehashidx;//当没有在rehash时值为-1
}dict;

image-20210818032212233

面试

  1. 渐进式增容/缩容
  2. 一致性哈希–解决负载均衡的问题。比如登陆项目。一千万个用户同时登陆。
  3. 操作系统一定要开始看了，内存管理、进程管理、线程管理。

dictDelete

  1. 删除第一节点
  2. 删除后个数会少，要处理

time

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
/*
 * 返回以毫秒为单位的 UNIX 时间戳
 *
 * T = O(1)
 */
long long timeInMilliseconds(void) 
{
    struct timeval tv;

    gettimeofday(&tv,NULL);
    return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
}
/* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
/*
 * 在给定毫秒数内，以 100 步为单位，对字典进行 rehash 。
 *
 * T = O(N)
 */
int dictRehashMilliseconds(dict *d, int ms) 
{
    // 记录开始时间
    long long start = timeInMilliseconds();
    int rehashes = 0;

    while(dictRehash(d,100)) {
        rehashes += 100;
        // 如果时间已过，跳出
        if (timeInMilliseconds()-start > ms) break;
    }

    return rehashes;
}

微机原理

发表于2021-07-25更新于2025-09-28阅读次数

二进制转化为十进制

https://blog.csdn.net/weixin_42857472/article/details/103966229

除10取余法

设计程序时候的二进制转化为十进制的算法
二进制转化为十进制（除10取余法）

除10取余法中，对于二进制转化为10进制来讲要除于1010，就是把10转化为二进制数，再用二进制数除于1010

例如：二进制11101除于1010，余数1001，转化为十进制数为9，这个是相当于十进制数的个位，再用中间商0010再除于1010，余数为0010，转化为十进制数为2，相当于十进制数的十位。

image-20210725001626129

比较法

假如一个数393
最高位为百位，所以让393和100比较
如果393>=100
则393减去100，然后统计百位的数＋1，然后用结果差继续和100比较，也就是293和100比较，仍然大于，所以293再减去100，统计一百的数再+1，直到不大于一百了，说明这个数没有百位只有十位和个位了，所以和10比较，类似的减去10，然后统计十位的数+1，再继续比较，知道不大于十，那么剩下的就是个位的数了。

二进制转化为十进制的话比较的对象100就要化成二进制，即1100100
十的二进制就是1010。

比如(11101)2–>(29)10：11101>1010，十位+1；11101-1010=10011>1010，十位+1；10011-1010=1001<1010，十位结束，(1001)2=(9)10。则结果为(29)10。

8位寄存器

以8086为例，虽然8086是16位处理器，但也可以以8位方式存储数据到寄存器中。

8位寄存器有：AH、AL。H代表高八位，L代表低八位，AH与AL一起组成AX寄存器即16位寄存器。相应地，BH、BL；CH、CL；DH、DL，也是8位寄存器。BX、CX、DX是16位寄存器。

二进制数的运算

算术运算+、-、*、/

比如97+89

1
2
mov AL,97	;汇编后:B0 61	;B0h就表示“把一个字节数传送给AL寄存器中”的机器源代码，61h代表97的十六进制。
add AL,89	;(AL)=BAh	;带括号就表示括号中地址的内容，此处表示AL寄存器的内容

mov AL,97 <—> B0 61 ;B0h就表示“把一个字节数传送给AL寄存器中”的机器源代码，61h代表97的十六进制。

处理器状态字寄存器PSW

也称为标志寄存器，主要用于CPU运算后根据结果设置各个标志，一个标志一个状态，一个状态用一个bit位表示。

补码

补码的范围有一个疑惑点。假如一个8位补码，可以表示的范围是-128~+127，如果只是按照老师上课讲的“取反加一法”来看，就会不清楚-128这个数是怎么来的。因为带符号位（带符号位这种说法是有误的，下面会提到）的8位二进制码的绝对值最大是127。

这时，我们要深刻地纠正我们对补码概念的误区。

补码的范围https://www.zhihu.com/question/20458542/answer/40759880
补码的定义https://blog.csdn.net/xiang_shao344/article/details/118490004

第一步，就像练北冥神功要先散功一样，先把你心中对原码，反码，补码的一套认识全部忘掉。

第二步，正式开讲

首先灌输一个新的概念叫，模
什么是“模”，想象日常使用的钟表，它可以显示0～12点的时间，假设现在是2点钟，请用手动拨动时针的方式将时间减4小时，你会怎么做？
有两种方式：

  1. 逆时针将时针拨4小时
  2. 顺时针将时针拨8（12-4）小时

这里要讲的是第二种方式，为什么顺时针拨12-4也可以达到和正常思维的第一种方式一样的位置。
12就是模。
同样的，如果是十进制的两位数，80-10 和 80＋90在不考虑百位数的基础上都是70。这里的90就是100-10得来的，这种情况下100就是模
模就好比是一个极限，在它的范围内，两个相加等于模的数互为补数，还是举100的例子
90和10， 55和45，68和32，互为补数
在模的范围内做减法，可以将“X－Y”的减法变更为“X＋Y的补数“的加法，当然前提是不考虑百位数。

思考题，上面举的例子是大数减小数，那么如果是小数减大数会怎么样呢？

如果是10-80，结果应该是－70，但如果按照10+（100-80），结果是30。
而很明显－70和30不是一回事，这里也没有百位数的问题，这种情况应该怎么破？
当初的那些先贤们想出来的办法很简单，就是把这两个数直接划上等号，正好顺便解决了负数的表达方式。再来仔细看看这两个数的关系：－70绝对值的补数就正好是30
所以在计算机中，负数的表达方式就是它绝对值的补数
但是问题又来了，看起来这个解决方式很完美了，但别忘了，30他已经代表了正数的30了，现在又要用来代表负数的－70，谁知道它出现的时候到底是代表哪个数？
为了解决这个问题，需要给这套规则划定一个范围，原来是0～99的正数，现在既然要用部分正数来代替负数了，那就要规定一个范围来使得一个数只代表一个含义，正好一人一半，0～49这个区间就代表正数，50～99的区间就用来代表各自补数的负值，例：98就代表－2

第三步，现在回到二进制的计算机世界

8位二进制数一共可以表示2的8次方，256个数，即0～255 （别忘了0也要占一位的），他们的极限就是256，即256是8位二进制数的模 ，应该不难理解吧，同上十进制的两位数0～99的模是100。
还是用二进制来说明清楚，8位二进制能表示的数的极限是
1 1 1 1 1 1 1 1， 就是255，在这基础上加0 0 0 0 0 0 0 1，出现了进一位 即 1 0 0 0 0 0 0 0 0
这个1 0 0 0 0 0 0 0 0就是8位二进制数的模，256

同样按照第二步讲的逻辑，一半的数0～127，代表其正数本身，另一半的数 128～255，代表其补数的负值，即“－1～－128”的区间。
而 “X－Y”的减法 就用 “X＋Y的补数” 的加法来表示，完美！ 唯一需要注意的事情是任何计算的输入值和输出结果值都需要严格遵守－128～127的范围，一旦溢出就会报错。
这也就是我们在编程里强调的为什么 byte＋byte还得是byte，int＋int还得是int，数据溢出问题也是每一个程序员都需要注意的问题。

这样一说是不是可以理解－128的补码是怎么来的了吧？ 他就是256 - |-128|＝128
二进制的128是不是就是1 0 0 0 0 0 0 0 ？

最终问题，那书和老师为什么要用原码，反码来讲补码 ？

空穴来风，未必无因
那是因为计算机就是这样求负数的补码的，我们在键盘上敲一个负数的时候，计算机要把它用补码的形式存储下来，还记得上面我们讲的补码是怎么来的吗？
模－绝对值，这是不是个减法公式？但计算机没有减法逻辑，我们费了那么大的劲搞了一套补码的规则就是为了用加法来替代减法，但为了实现这么套规则，却跨不过一个坎，就是把负数计算成补码仍然是需要减法逻辑的。怎么办呢，那些伟大的先贤们 （膜拜）就想出了这么个办法：
首位不变，其余位取反后，再加一

问题：上面说到了，负数计算成补码需要取反加1，但-128在8位数中，没有其原码表示形式，如果要人工手工计算，将-128先看做是9位带符号数，再转换为补码：1 1000 0000首位不变，其余取反加1会变成1 1000 0000，进位溢出舍去，即为1000 0000。

下面是吐槽

不知道是哪个书呆子教书，照搬了机器的逻辑，把取反加一的方法当做补码的计算逻辑就这么教下来了。搞笑的是，还保留了补码这个名字，照理说这种教法应该叫 取反加一码 更合理，你还补什么啊？
不仅如此，还搞出了个首位符号位的说法，弄出了个正0负0，还用负0来充当－128，真是不把人弄疯不罢休啊！！

寄存器

通用寄存器

数据寄存器

AX

累加

BX

基址寄存器

CX

计数器

DX

数据寄存器。在I/O端口的IN/OUT操作中充当I/O地址寄存器。

地址指针与变址寄存器

地址指针寄存器

SP

堆栈指针寄存器–用来指示PUSH/POP堆栈操作时所操作单元的段内16位地址的寄存器。

BP

地址指针寄存器–作用和BX基址寄存器是一样的，都可以存放16位段内偏移地址，但是是有区别的，存放16位段内偏移地址不在同一个逻辑段，CPU默认BX在DS数据段，BP在SS堆栈段。CPU默认BP指向的是SS段的地址。
当然，想要BP指向数据段也可以，必须在汇编语句中写明前缀，称之为段超越前缀，如：

1
2
3
MOV AL,56H
MOV BP,0003H
MOV DS:[BP],AL

变址寄存器

SI

源变址寄存器

DI

目的变址寄存器

总结

用BX/SI/DI外加中括号即间接找到的地址都默认在DS段内。只用BP中括号间接找到的地址默认在SS段内。

image-20210726185205000

段寄存器

分别放的是各自逻辑段的段地址

CS

代码段寄存器。CS的值指明的是，程序代码所在的那个逻辑段的段地址。

CS初始化的值用户不可设置，由操作系统决定。

DS

数据段寄存器

ES

附加数据段寄存器

SS

堆栈段寄存器

控制寄存器

IP

指令指针寄存器。等效于一般处理器中程序计数器PC的作用。即用于CPU取指令时需要用到的偏移地址寄存器。与CS（代码段）不可分家，CS:IP。

PSW

处理器状态字寄存器。16位寄存器，但有用的只有9位。

image-20210726144858440

9位分为两类标志。

状态标志（6个）

ZF、CF、PF、OF、SF、AF。反映的是ALU运算后结果的状态。

只有运算指令执行后才会影响这些状态值的改变。

控制标志（3个）

IF、PF、TF。用来控制CPU的运行状态的。

DF

方向控制标志。用于控制字符串操作中SI和DI变址的方向。

1
2
CLD	;DF=0;控制SI/DI加1或2
STD	;DF=1;控制SI/DI减1或2

image-20210726150833012

IF

中断允许标志。

执行用户程序期间，某个特殊事件发生，让CPU暂时停止正在执行的程序，转去为该事件服务，即去执行中断服务子程序。服务完成后，CPU尚可返回到刚才中止的位置继续执行。

CLI会置0，STL会置1。

如果IF为0，则会屏蔽外部中断请求（8086的18脚INTR输入）。但CPU芯片内部中断不可屏蔽。

TF

陷阱（单步）标志。Debug专用。

没有清零置一的指令。那该如何设计程序使TF置1？

image-20210726151453188

以上程序：先PUSHF（F即PSW），再POP给AX赋值；再OR把AX中第九位置1；将AX压栈，在POPF给PSW赋值。

TF在PSW寄存器的第九位（如果从0开始，是第8位），我们知道，OR语句可以让数据置1，则让PSW或上0000 0001 0000 0000即可使TF置1。

如果TF标志为1，则程序将进行单步操作。常用于Debug调试。

8086存储器和I/O组织

存储器地址空间与数据存放格式

地址空间

A_19~A_16/A_15~A_10/A_9~A_0：均为外部存储器编址。所以能寻址的空间为2^20字节即1MB。

低16位给外部I/O端口编址。I/O地址空间为2^16字节=64KB。

在IBM PC机中只用了低10位给I/O分配地址，地址空间为1KB。前512个I/O地址即000H~1FFH给主板上的I/O分配地址；后512个I/O地址即200H~3FFH给插件版上的I/O分配地址。

数据存放格式

字节型、字型、双字型。

字节型数据

字节型数据定义伪指令：DB（Data Byte）

字型数据定义伪指令：DW（Data Word）

双字型数据定义伪指令：DD（Data Double）

存储器的分段与物理地址的形成

分段

1、为什么分段？

地址线有20根，而寄存器只有16位，无法直接管理220位空间。我们可以通过给内存分段使16位寄存器有效管理若干段（最少24=16段）的每个逻辑段的2^16位信息。

2、怎么分？

根据需求进行分段，每段最大2^16=64KB。每个逻辑段的起始地址必须能被16整除。

已知某存储器单元的逻辑地址，求物理地址

PA（Physical Address）=段地址*10H + 段内偏移地址（也称段内有效地址EA(Effective Address)）

段地址*10H 就相当于左移一位。

例：逻辑地址0001H: 0010H，PA=0001H*10H + 0010H=00010H+0010H=00020H

8086CPU的指令系统

名词解释

指令：

指令系统：CPU能识别的所有指令的集合

机器语言：指令代码语言

机器语言程序：用户用机器语言编写的程序

汇编语言：一种符号化语言，用一组符号和数字替代CPU能认识的指令。如MOV AL,12H替换了B0 12。

汇编语言（源）程序：用户用汇编语言编写的程序，但CPU不能直接执行，必须要翻译为机器语言程序

汇编：将汇编语言（源）程序翻译为机器语言程序的过程。

反汇编：将机器语言程序翻译为汇编语言（源）程序的过程。

8086汇编语言程序

语句的种类

指令语句

CPU能执行的语句称为指令语句；

能汇编/翻译成二进制指令代码的语句，称为指令语句。

伪指令语句

CPU不能执行的语句称为指令语句；

汇编时不能汇编/翻译成二进制指令代码的语句，称为伪指令语句。如"DB"，只是告诉汇编程序（masm.exe）开始定义字节型数据，开始分配空间。这条语句是汇编时完成的，并不是执行时完成的。

宏指令语句

本身是8086指令系统没有的指令，是用户用宏定义伪指令定义的一条新的语句。

汇编语言中语句的组成

名称+助记符+操作数+注释

变量名称、标号名必须以字母打头，操作数必须以0~9打头。

1
2
3
4
5
6
7
DAT1 DB 12H,-12,12	;注释	;DAT1为变量名
DAT2 DW ?	;定义时若不赋值，则需标问号;可以MOV DAT2,AX写入数据
...
NEXT: MOV AX,BX		;NEXT为标号名，将此处语句的地址符号化
...
ADD AX,DAT2			;
JZ NEXT				;判ZF标志是否为1，若为1则说明AX加和为0，则跳转的条件满足，则跳至NEXT

汇编语言中的常数及表达式

常数

十六进制常数，以H结尾；二进制常数，以B结尾；十进制常数，以D结尾，可以缺省

字符常数’A’；字符串常数’THIS IS A …’

表达式

算术表达式

逻辑表达式

AND/OR/NOT

关系表达式

LT: 小于

属性表达式

标号

标号一旦定义了，就具有3个属性。

  1. 16位段地址。获取属性操作符：SEG

  2. 16位段内偏移地址。获取属性操作符：OFFSET（常用）

    1
    MOV BX,OFFSET NEXT	;NEXT是标号名称

  3. 类型。获取标号对应的类型：TYPE

    有两种类型，一种是跳转目的地和跳转语句在同一个代码段，则为段内NEAR近程型，值为-1；一种是跳转目的地和跳转语句不在同一个代码段，则是段间FAR远程型，值为-2。

变量及变量定义伪指令
变量定义伪指令 用途
DB 定义字节型变量，8位
DW 定义字型变量，16位
DD 定义双字型变量，32位

变量一旦定义了，就具有5个属性。

  1. 16位段地址。获取属性操作符：SEG

  2. 16位段内偏移地址。获取属性操作符：OFFSET（常用）

  3. 类型。获取标号对应的类型：TYPE

    变量定义伪 类型 类型值（字节数）
    DB 字节型变量 1
    DW 字型变量 2
    DD 双字型变量 4 
    1
    MOV AL,TYPE DAT1	;等效于MOV AL,1

  4. 长度。获取属性操作符：LENGTH

    变量的长度指在变量名定义语句中，所定义的变量的个数。比如在变量定义的语句中出现了DUP重复操作符，那么重复操作符前的数值便是定义的变量的个数；如果没有出现DUP重复操作符，则认为只定义了一个变量。

  5. 大小。获取属性操作符：SIZE

    变量的长度指在变量名定义语句中，所定义的所有变量占用的总的字节数。那么，SIZE=TYPE*LENGTH

总结

OFFSET获取的段内偏移地址属性最好赋给地址寄存器，BX/BP为基址寄存器，SI/DI为变址寄存器。如果赋给AX没有意义。

例

在DS段有以下变量定义

1
DAT1 DB 12,12H,-12,'1'

image-20210728155350067

在masm.exe编译过程中，有一个"$"符号——位置计数器，记录偏移地址。每定义一个变量，$则会指向下一个将要被使用的存储单元地址。是16位变量。本身的值也是一个常数，既然是常数，那么在程序中也可以引用。

1
2
3
DAT1 DB 12,12H,-12,'1'
;DAT2 DB $	;DB定义不对，因为$是16位数据。
DAT2 DW $	;当执行到这一句时，$已经指向了下一个将要被使用的存储单元地址，即$中的值是0004H，则这条语句的意思是将0004H存入0004H存储单元，其中，低地址存放低位数据04H，高地址存放高位数据00H。

image-20210728160206056

1
2
3
;假设DAT3的段地址是1500H，偏移地址是000AH；DAT6的偏移地址是0016H
DAT6 DW DAT3	;此语句的意思不是取DAT3的值给DAT6，而是把DAT3的偏移地址赋给DAT6。即把000AH赋给DAT6存储空间。
DAT7 DD DAT3	;此时DAT7对应的偏移地址是0018H，DD变量将占用4个字节存储单元，由于4个字节可以分为2个双字空间，则汇编时会将DAT3的偏移地址和段地址都存放到DAT7中。

image-20210728161510404

重复操作符(DUP)
1
DAT8 DB 4 DUP(?)	;DUB为重复操作符，左边的4是指要重复的次数，括号内是要重复定义的值，这里的?代表随机值。

image-20210728161729544

1
DAT9 DW 3 DUP(?)

image-20210728162021258

注意区分

要区分变量定义和赋值时的区别。

1
2
MOV AL,DAT1+2	;指的是把(DAT1+2)存储单元中的“内容”赋给AL寄存器。(DAT1+2)存储单元中的内容目前是“F4H”，则把“F4H”传给了AL。采用的寻址方式是直接寻址。
DAT123 DW DAT1	;指的是把DAT1的偏移地址存到DAT123的存储单元中去。
属性临时修改操作符(PTR)
1
MOV AX,DAT1	;此句语法错误，因为AX是16位寄存器，而DAT1是DB类型的变量，占8位。类型不匹配，无法完成赋值。

类型不一致无法赋值时，可以使用PTR

1
MOV AX,WORD PTR DAT1	;将DAT1在这条语句中临时转换为字型数据。脱离这条语句后仍然是字节型变量。
应用

BYTE PTR [BX]

1
2
MOV [BX],10H	;语法错误，因为不知道[BX]找到的地址的那个存储单元是什么类型的，就不知道那个存储单元占几字节，那么就不知道10H该如何处理（是处理为10H还是0010H）。
MOV BYTE PTR [BX],10H	;运用PTR操作符正确处理

数据与转移地址的寻址方式

寻址方式就是求操作数的所在地或者所在存储器单元地址的方式。求得的操作数一是可以用来作为数据用，二是可以用来作为转移地址用。那么寻址方式就分为了两大类，第一大类是取数据的寻址方式，第二大类是关于转移到目的地地址的操作数在哪放着的寻址方式。如果是段内转移，则要求得16位偏移地址给IP，如果是段间转移，还要求得16位段地址给CS。
image-20210728172308349

关于寻找数据的寻址方式（8种）

立即数寻址

立即数只能做源操作数，不能做目的操作数。

MOV AX,1234H

注意

立即数只能传送给通用寄存器和存储器单元。

当段寄存器DS/ES/SS作为DST操作数时，SRC操作数不能是立即数寻址。

寄存器寻址

要寻找的操作数在寄存器当中。则是寄存器寻址。

1
MOV AX,BX

注意

MOV两个操作数时类型要一致
1
MOV AX,CL	;ERROR
类型要明确
1
2
MOV [0200H],56H				;ERROR
MOV WORD PTR [0200H],56H	;指明了该单元是一个字单元
当段寄存器DS/ES/SS作为DST操作数时，SRC操作数不能是立即数寻址。

但可以采用寄存器寻址作为中介。

1
2
3
MOV DS,1500H	;ERROR
MOV AX,1500H
MOV DS,AX
CS/IP只能作源操作数

CS代码段寄存器，IP指令指针寄存器，都不可作DST操作数。往往只读不写。用户无权主观更改CS/IP的值，CS/IP的值一是在初始值是程序中的内存启动时由操作系统赋予的。二是执行期间由转移指令CPU执行后改变而赋予的。

存储器寻址（5种）

要寻找的OPR（操作数）在存储器某单元中，存储操作数单元的EA（段内偏移地址）可以由以下5种寻址方式求得。

直接寻址

操作数所在单元的EA指令中直接给出。

1
2
3
4
5
6
7
8
MOV AL,[2000H]	;实际编程中，2000H将会符号化为变量
;在ds段：
		dat1 DB 12H
		dat2 DB 34H
		...
;在CS段：
		...
		MOV AL,dat1		;AL是寄存器寻址，dat1是直接寻址。语句执行完成后，AL中的内容则为(AL)=12H
注意

两个存储器单元之间不能直接传送数据

1
2
3
MOV DAT2,DAT1	;错误，两存储器单元之间不能直接进行一切的操作
MOV AL,DAT1
MOV DAT2,AL

寄存器间接寻址

[BX/SI/DI]

三个寄存器都是默认存放的DS中的地址。

image-20210729135603135

1
2
MOV BX,OFFSET DAT1	;将dat1的16位偏移地址给了BX
MOV AL,[BX]			;(DS:(BX))-->AL	;AL默认是字节型数据，则把12H给AL
1
MOV [BX],56H	;ERROR,因为源操作数是立即数寻址而[BX]没有说明类型。
1
2
3
4
5
MOV BX,OFFSET DAT1
MOV SI,OFFSET DAT2
MOV [BX],[SI]	;ERROR,两存储器单元之间不能直接传送数据。
MOV AL,[SI]
MOV [BX],AL

寄存器相对寻址

EA=[BX/BP/SI/DI] + 8/16位disp(相对位移量)

例：MOV [BX]+3,AL ;也可等效为**[BX+3]或3+[BX]**,如果相对位移量写在左边，则+号可以缺省。

如果相对位移量为常数：如果寄存器是BX,SI,DI则段地址默认在DS段；如果寄存器是BP则段地址在SS段。

1
2
MOV BX,OFFSET DAT1
MOV [BX]+3,AL	;也可等效为[BX+3]或3+[BX],如果相对位移量写在左边，则+号可以缺省。

image-20210729142813193

如果相对位移量是变量：段地址由变量的段地址决定。

1
2
3
MOV BX,0
MOV AL,0
MOV DAT1[BX],AL	;完成的功能是：先计算16位偏移地址，即OFFSET DAT1+(BX)作为偏移地址，段地址由DAT1决定，再把AL的内容赋给SEG DAT1:BX+OFFSET DAT1这个存储单元中。
通过一个例子体现为何要设计一个默认在SS段的BP

image-20210729143703028

1
2
MOV BP,SP
MOV DX,[BP]+4

image-20210729144042088

该例说明了，如果不想破坏SP栈顶指针，则可以方便的用BP来替代其指向栈顶，而且默认的段地址在堆栈段，所以操作栈比较方便。

基址、变址寻址

基址：[BX/BP]，变址：[SI/DI]。EA=[BX/BP]+[SI/DI]

段地址的确认以基址寄存器来决定。BX默认为DS，BP默认为SS。

1
2
3
4
5
6
7
8
9
10
	DAT1 DB 12H
	DAT2 DB 34H
	...
	MOV CX,10
	MOV BX,OFFSET DAT1
	MOV SI,0
	MOV AL,0
NEXT: MOV [BX][SI],AL
	INC SI			;SI的值增1
	LOOP NEXT		;CX的值循环减1，若不为0则跳转到NEXT

image-20210729145047000

基址、变址且相对寻址

基址：[BX/BP]，变址：[SI/DI]。EA=[BX/BP]+[SI/DI]+8/16disp

如果相对位移量是变量，则段地址以变量的段地址为准。

隐含寻址

指令中并未写出操作数，但CPU执行指令时知道操作数在哪里。

1
2
3
4
5
...
PUSH AX
...
;1.        SP <-- (SP)-2
;2. (SS:(SP)) <-- (AX)

关于转移地址的寻址方式