15.哈希表

第一章自测&关键词回顾

视频: 蓝不过海呀

第一节自测

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

第二节关键词回顾

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

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

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

1.1.3 装填因子

1.1.4 删除置为-1的作用

第二章手撕

2.1.1 开放寻址—线性探测法

#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);

#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("");
}

#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 拉链法

#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);

#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]);
    }
}

#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;
}

居然能找到这来, 真是厉害~

15.哈希表

第一章自测&关键词回顾

第一节自测

第二节关键词回顾

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

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

1.1.3 装填因子

1.1.4 删除置为-1的作用

第二章手撕

2.1.1 开放寻址—线性探测法

2.1.2 开放寻址—平方探测法

2.1.3 拉链法

第三章相关应用

第四章上手真题

第五章比赛怎么用

居然能找到这来, 真是厉害~

15.哈希表

第一章 自测&关键词回顾

第一节 自测

第二节 关键词回顾

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

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

1.1.3 装填因子

1.1.4 删除置为-1的作用

第二章 手撕

2.1.1 开放寻址—线性探测法

2.1.2 开放寻址—平方探测法

2.1.3 拉链法

第三章 相关应用

第四章 上手真题

第五章 比赛怎么用

第一章自测&关键词回顾

第一节自测

第二节关键词回顾

第二章手撕

第三章相关应用

第四章上手真题

第五章比赛怎么用