15.哈希表

15.哈希表

明廷盛 嘻嘻😁
  2025-05-13 21:58:59 2025-05-13 21:58:59 Created   2025-05-14 22:23 2025-05-14 22:23 Updated   2.6k Words  12 Mins  

第一章 自测&关键词回顾

视频: 蓝不过海呀

第一节 自测

  1. 将10, 25, 17, 6, 24 使用三种解决哈希冲突方式进行插入; ①哈希函数为: $H(key)=key%7$ ②状态因子为 $\frac{5}{7}$
  2. 分别计算它们的ASL”成功”与”失败”的长度
  3. 在开放寻址法中, “删除值时”需要注意什么?
  4. 在开放寻址法中, 删除值后, ASL成功和ASL失败的数值会如何变化

第二节 关键词回顾

1.1.1 解决哈希冲突的三种方式

|1175

1.1.2 平均查找长度$ASL_{success}$ 和$ASL_{fail}$

  • $ASL_{success}=找到哈希表中每个元素, 需要的查询次数 / 哈希表中元素个数$ (如果删除了, 会导致元素个数变化的哈, 通常会导致ASL成功增大, 也就是找到每个元素, 需要的距离增加)
  • $ASL_{fail}=所有可能的哈希位置(就是[0,MOD), 每个位置失败(从开始比较,到比较到空气)需要的比较次数总和 / MOD$
    |1200

1.1.3 装填因子

|725

1.1.4 删除置为-1的作用

第二章 手撕

2.1.1 开放寻址—线性探测法

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 7    // 数组长度 (装填因子=表中元素/表长N)
#define MOD 7  // H(key)=key%MOD
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))

typedef struct HashTable {
    int *hash;
    int *aslSuccess;  // 每个值的, 成功的拼接查找长度 [命名不严谨]
    int length;       // 关键字个数
} HashTable;

// 1.初始化Hash表
HashTable *initHashTable(int *input, int len);
// 2.向哈希表中插入元素
void insertVal(HashTable *hashTable, int x);

// 2-1.平方探测法
void quadraticInsert(HashTable *hashTable, int x);
int quadraticSearch(HashTable *hashTable, int x);

// 3.查找指定值x是否在哈希表中, 在返回下标, 不在返回-1
int search(HashTable *hashTable, int x);
// 4.删除制定值x, 返回下标, 如果目标删除值不在返回-1
int deleteVal(HashTable *hashTable, int x);
// 5.获取平均成功查找长度(不返回了)
void getASLSuccess(HashTable *hashTable);
// 6.获取平均失败查找长度(不返回了)
void getASLFail(HashTable *hashTable);

// [for test] 打印哈希表
void printHashTable(HashTable *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
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include "linear.h"

// 1.初始化Hash表
HashTable *initHashTable(int *input, int len) {
    HashTable *hashTable = (HashTable *)malloc(sizeof(HashTable));
    hashTable->hash = (int *)malloc(N * sizeof(int));
    hashTable->aslSuccess = (int *)malloc(N * sizeof(int));
    hashTable->length = len;

    memset(hashTable->hash, 0, N * sizeof(int));
    memset(hashTable->aslSuccess, 0, N * sizeof(int));

    // 插入初始值
    for (int i = 0; i < len; i++) {
        insertVal(hashTable, *(input + i));
        // quadraticInsert(hashTable, *(input + i));
    }

    return hashTable;
}
// 2.向哈希表中插入元素
void insertVal(HashTable *hashTable, int x) {
    int pos = x % MOD;
    int successCount = 1;                                         // 经过多少次才找到坑位
    while (hashTable->hash[pos] && hashTable->hash[pos] != -1) {  //! -1表示删除,可以插入新值
        pos = (pos + 1) % N;
        successCount++;
    }
    hashTable->hash[pos] = x;
    hashTable->aslSuccess[pos] = successCount;  // 这样分开写直观
}

// 2-1.平方探测法
void quadraticInsert(HashTable *hashTable, int x) {
    int step[] = {1, -1, 4, -4, 9, -9};
    int indexStep = 0;
    int initPos = x % MOD;  // ! 要在原始基础上变动

    int pos = initPos;
    int successCount = 1;  // 经过多少次才找到坑位
    while (hashTable->hash[pos] != 0 && hashTable->hash[pos] != -1) {
        pos = (initPos + step[indexStep++]) % N;
        successCount++;
    }
    hashTable->hash[pos] = x;
    hashTable->aslSuccess[pos] = successCount;
}
// 3-1
int quadraticSearch(HashTable *hashTable, int x) {
    int step[] = {1, -1, 4, -4, 9, -9};
    int indexStep = 0;
    int pos = x % MOD;
    while (hashTable->hash[pos] != x && hashTable->hash[pos] != -1 && hashTable->hash[pos] != 0) {
        pos = (pos + step[indexStep++]) % N;
    }
    return hashTable->hash[pos] == x ? pos : -1;
}

// 3.查找指定值x是否在哈希表中, 在返回下标, 不在返回-1
int search(HashTable *hashTable, int x) {
    int pos = x % MOD;
    //! 删除置为-1的意义在这里, 如果直接置为0,那这里就不会继续向后找了
    // 比如MOD=7, 7,14,21都映射到0位置,因为冲突,0:7; 1:14; 2:21
    // 现在把14删除了,如果置为0, 那找21的时候,碰到1位置的0,就停止寻找了
    // 但是如果置为-1, 寻找停止的条件为0, 那就会继续向后, 正确找到21.
    while (hashTable->hash[pos] != x && hashTable->hash[pos] != 0) {
        pos = (pos + 1) % N;
    }
    return hashTable->hash[pos] == x ? pos : -1;
}

// 4.删除指定值x, 返回下标, 如果目标删除值不在返回-1
int deleteVal(HashTable *hashTable, int x) {
    int pos = search(hashTable, x);
    if (pos == -1)  // 删除的值, 置为-1;
        return -1;
    hashTable->hash[pos] = -1;
    return pos;
}

// 5.获取平均成功查找长度
void getASLSuccess(HashTable *hashTable) {

    int sum = 0;
    int howManyPlace = 0;  //  因为有可能删除了, 删除后哈希表中存的就不再是 hashTable->length个了
    for (int i = 0; i < N; i++) {
        if (hashTable->hash[i] == 0 || hashTable->hash[i] == -1)
            continue;
        sum += hashTable->aslSuccess[i];
        howManyPlace++;
    }
    printf("%d/%d\n", sum, howManyPlace);
}

// 6.获取平均失败查找长度
void getASLFail(HashTable *hashTable) {
    int ASLFail[N];
    memset(ASLFail, 1, N);           // 和空气也比较也算一次
    int count = 1;                   // 什么情况count为1? case1:刚开始 case2:经过了"空坑位"
    for (int i = 0; i < MOD; i++) {  // !坑 因为查找不可能到MOD
        // 过空气归零
        if (hashTable->hash[i] == 0) {  //! 这里如果遇到-1, 你还是要继续查找的, 只有遇到0才停下来
            ASLFail[i] = 1;
            count = 1;  //! 归零
            continue;
        }
        // 重算逻辑
        if (count == 1) {
            int j = i;
            while (hashTable->hash[j] != 0) {
                count++;
                j = (j + 1) % N;
                // printf("%d\n", count);
            }
            ASLFail[i] = count;
            count--;
        }
        // 连续直接等与前一个-1(当然每次获取完-1, 下一个直接等就是-1 的值了)
        else {
            ASLFail[i] = count;
            count--;
        }
    }

    int sum = 0;
    for (int i = 0; i < MOD; i++) {
        sum += ASLFail[i];
    }
    printf("%d/%d\n", sum, MOD);
}

// [for test] 打印哈希表
void printHashTable(HashTable *hashTable) {
    for (int i = 0; i < N; i++)
        printf("%d\t", i);
    puts("");
    for (int i = 0; i < N; i++) {
        printf("%d\t", hashTable->hash[i]);
    }
    puts("");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "linear.h"

void test(void) {
    int input[] = {10, 25, 17, 6, 24};
    HashTable *hashTable = initHashTable(input, SIZE(input));
    printHashTable(hashTable);
    // deleteVal(hashTable, 25);
    // for (int i = 0; i < hashTable->length; i++) {
    //     printf("%d=>%d\n", input[i], search(hashTable, input[i]));
    // }

    getASLSuccess(hashTable);
    getASLFail(hashTable);
}

int main() {
    test();
    return 0;
}

2.1.2 开放寻址—平方探测法

偷个小懒, 真的不想写啦!!!!!! 好累呀!!!!!!!

2.1.3 拉链法

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
#include <stdio.h>
#include <stdlib.h>

#define N 7    // Hash表的长度
#define MOD 7  // Hash函数需要mod的值
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))

typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 单链表相关实现(有哨兵头, 哨兵头值域没有任何意义)
// 初始化单链表
Node *initLinkList(void);
// 插入(头插)
void insertLinkLIst(Node *link, int x);
// 删除(如果成功删除返回1,否则返回-1,表示hash表中没有该元素)
int deleteLinkList(Node *link, int x);
// 查找(如果在该单链表上找到x, 返回1, 找不到返回-1)
int searchLinkList(Node *link, int x);
// 遍历
void traverseLinkList(Node *link);

typedef struct HashTable {
    Node *place[N];  // 哈希表中每个"坑位"都是一个单链表 (存储的为哨兵头)
    int length;      // 哈希表中值的个数
} HashTable;

// 哈希表相关实现
// 1.初始化哈希表
HashTable *getHashTable(int *input, int len);
// 2.插入元素
void insertVal(HashTable *hashTable, int x);
// 3.查询元素(有返回元素下标, 没找到返回-1)
int searchVal(HashTable *hashTable, int x);
// 4.删除元素(有返回元素下标, 不存在返回-1)
int deleteVal(HashTable *hashTable, int x);
// 5.获取成功ASL的值(打印分数)
void getASLSuccess(HashTable *hashTable);
// 6.获取失败ASL的值(打印分数)
void getASLFail(HashTable *hashTable);
// [for test] 打印哈希表
void printHashTable(HashTable *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
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include "zipHash.h"

// 单链表相关实现
// 初始化单链表
Node *initLinkList(void) {
    Node *head = (Node *)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    return head;
}
// 插入(头插)
void insertLinkLIst(Node *link, int x) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = x;
    newNode->next = link->next;  // 头插法
    link->next = newNode;
}
// 删除
int deleteLinkList(Node *link, int x) {
    Node *pmove = link->next;
    Node *pre = link;
    while (pmove) {
        if (pmove->data == x) {
            pre->next = pmove->next;
            free(pmove);  // 释放
            pmove = NULL;
            return 1;
        }
        pre = pmove;
        pmove = pmove->next;
    }
    return -1;  // 该值不在该单链表中
}
// 查找(如果在该单链表上找到x, 返回1, 找不到返回0)
int searchLinkList(Node *link, int x) {
    link = link->next;
    while (link) {
        if (link->data == x)
            return 1;
        link = link->next;
    }
    return -1;  // 该值不在该单链表中
}
// 遍历
void traverseLinkList(Node *link) {
    link = link->next;
    while (link) {
        printf("%d->", link->data);
        link = link->next;
    }
    printf("NULL\n");
}

// 哈希表相关实现
// 1.初始化哈希表
HashTable *getHashTable(int *input, int len) {

    HashTable *hashTable = (HashTable *)malloc(sizeof(HashTable));
    hashTable->length = len;
    // 初始化每个坑位
    for (int i = 0; i < N; i++) {
        hashTable->place[i] = initLinkList();
    }
    // 插入初始化的值
    for (int i = 0; i < len; i++) {
        insertVal(hashTable, *(input + i));
    }
    return hashTable;
}
// 2.插入元素
void insertVal(HashTable *hashTable, int x) {
    int pos = x % MOD;
    insertLinkLIst(hashTable->place[pos], x);  // 向哈希表中, 第pos位置的单链表插入x值(头插)
}
// 3.查询元素(有返回元素下标, 没找到返回-1)
int searchVal(HashTable *hashTable, int x) {
    int pos = x % MOD;
    return searchLinkList(hashTable->place[pos], x) == 1 ? pos : -1;  // pos就是这个pos,找到就是有,否则就没有
}
// 4.删除元素(有返回元素下标, 不存在返回-1)
int deleteVal(HashTable *hashTable, int x) {
    int pos = x % MOD;
    return deleteLinkList(hashTable->place[pos], x) == 1 ? pos : -1;
}
// 5.获取成功ASL的值(打印分数)
void getASLSuccess(HashTable *hashTable) {
    int ASLSuccessSum = 0;
    for (int i = 0; i < N; i++) {
        Node *pmove = hashTable->place[i]->next;
        int count = 0;  // 比较NULL不算做一次比较(所以初始化为0)
        int level = 1;  // 层数
        while (pmove) {
            count = count + (count + 1);
            pmove = pmove->next;
        }
        printf("i:%d ->%d\n", i, count);
        ASLSuccessSum += count;
    }
    printf("ASL Success: %d/%d\n", ASLSuccessSum, hashTable->length);
}
// 6.获取失败ASL的值(打印分数)
void getASLFail(HashTable *hashTable) {
    // 计算每个单链表, 比较到NULL需要的次数, 注意与NULL比较不算一次
    int ASLFailSum = 0;
    for (int i = 0; i < MOD; i++) {  // !注意这里是MOD, 只能到MOD!!!
        Node *pmove = hashTable->place[i]->next;
        while (pmove) {
            ASLFailSum++;
            pmove = pmove->next;
        }
    }
    printf("ASL Fail: %d/%d\n", ASLFailSum, MOD);
}
// [for test] 打印哈希表
void printHashTable(HashTable *hashTable) {
    for (int i = 0; i < N; i++) {
        printf("%d: ", i);
        traverseLinkList(hashTable->place[i]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include "zipHash.h"

void test(void) {
    int input[] = {10, 25, 17, 6, 24};
    HashTable *hashTable = getHashTable(input, SIZE(input));
    printHashTable(hashTable);
    getASLSuccess(hashTable);
    getASLFail(hashTable);
}

int main() {
    test();
    return 0;
}

第三章 相关应用

第四章 上手真题

第五章 比赛怎么用

  • Title: 15.哈希表
  • Author: 明廷盛
  • Created at : 2025-05-13 21:58:59
  • Updated at : 2025-05-14 22:23:00
  • Link: https://blog.20040424.xyz/2025/05/13/🏫考研/第一部分 数据结构/15.哈希表/
  • License: All Rights Reserved © 明廷盛
On this page
15.哈希表
  1. 第一章 自测&关键词回顾
    1. 第一节 自测
    2. 第二节 关键词回顾
  2. 第二章 手撕
  3. 第三章 相关应用
  4. 第四章 上手真题
  5. 第五章 比赛怎么用