哈希表

哈希表|散列表

• 将任意类型的值映射为整形值（下标）
• 任意——>哈希函数——>整型
• 哈希表=哈希函数+冲突处理方法
• 冲突处理方法：开放定值法、再哈希|散列、拉链法、建立公共溢出区
• 开放定值法：
• 再哈希：使用多个哈希函数建立哈希表
• 拉链法：建立链表
• 建立公共溢出区 ：

字符串查找

冲突处理方法

• 拉链法：采用链表

哈希函数

• BKDRhash哈希函数

int BKDRHash(char *str) {
    int seed = 31, hash = 0;//也可以乘以31、131、1313、13131、131313..
    for (int i = 0; str[i]; i++) {
        hash = hash * seed + str[i];
    }
    return hash & 0x7fffffff;
}

测试

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 哈希表|散列表 
/*
将任意类型的值映射为整形值（下标）

任意——>哈希函数——>整型

哈希表=哈希函数+冲突处理方法
冲突处理方法：开放定值法、再哈希|散列、拉链法、建立公共溢出区
开放定值法： 
再哈希：使用多个哈希函数建立哈希表 
拉链法：建立链表  
建立公共溢出区 ： 
*/ 
//结构定义 

typedef struct Node {
    char *str;
    struct Node *next;
} Node;

typedef struct HashTable {
    Node **data;
    int size;
} HashTable;

Node *getNewNode(char *str, Node *head) { //封装字符串str 
    Node *node = (Node *)malloc(sizeof(Node));
    node->next = head; //头插法插入节点 
    node->str = strdup(str);//深拷贝得释放空间 
    return node; //返回头节点指针 
}

HashTable *init(int n) { //hash表初始化 
    HashTable *hash = (HashTable *)malloc(sizeof(HashTable));
    hash->size = n << 1; //保证0.5利用率 
    //使用calloc自动初始化内存空间为0，malloc申请的空间不干净 
    hash->data = (Node **)calloc(hash->size, sizeof(Node));
    return hash;
}

int BKDRHash(char *str) {
    int seed = 131313, hash = 0;
    for (int i = 0; str[i]; i++) {
        hash = hash * seed + str[i];
    }
    return hash & 0x7fffffff; 保证hash在int范围内
}

int insert(char *object, HashTable *hash) {
    int seed = BKDRHash(object);
    int ind = seed % hash->size;
    //将待插入对象封装为一个节点 
    hash->data[ind] = getNewNode(object, hash->data[ind]);
    return 1;
}

int search(char *object, HashTable *hash) {
    if (hash == NULL) return 0;
    int seed = BKDRHash(object);
    int ind = seed % hash->size;
    Node *p = hash->data[ind];
    while (p) {
        if (strcmp(p->str, object) == 0) return 1;
        p = p->next;
    }
    return 0;
}

void clear_Node(Node *head) {
    if (head == NULL) return ;
    Node *p = head, *q;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    return ;
}

void clear(HashTable *h) {
    if (h == NULL) return ;
    for (int i = 0; i < h->size; i++) {
        clear_Node(h->data[i]);
    }
    free(h);
    return ;
}

int main() {
    #define n 20
    HashTable *h = init(n);
    for (int i = 0; i < n; i++) {
        char ch[n + 2] = {0};
        int op;
        scanf("%d%s", &op, ch);
        switch (op) {
            case 0 : {
                printf("%s\n", insert(ch, h) ? "插入成功" : "插入失败");
            } break;
            case 1 : {
                printf("%s\n", search(ch, h) ? "查找成功" : "查找失败");
            } break;
        }
    }
    #undef n
    clear(h);
    return 0;
}