2037: 字符串比较，C语言HashMap的实现

解题思路:

1. 计算字符串的哈希值函数
   

2. 拉链法解决哈希冲突

注意事项:

参考代码:

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


// 哈希表结点
typedef struct map_node {
    char *str;                      // key 键
    int count;                      // value 值
    struct map_node *next;          // 拉链，解决哈希冲突的链表
} MapNode;

MapNode **g_map;                    // map 哈希表
int g_size;                         // map 大小
typedef unsigned long long ULL;     // hash 值类型

// 计算字符串的哈希值，并返回字符串长度
ULL getHash(const char *str, int *size) {
    ULL hash = 0;
    int i;
    for (i = 0; str[i]; i++) {
        hash = hash * 31 + str[i];
    }
    *size = i;
    return hash;
}

// 根据字符串和其哈希值在Map中查找结点
MapNode *findKey(const char *str, ULL hash) {
    MapNode *cur;
    cur = g_map[hash % g_size];
    while (cur) {
        if (strcmp(str, cur->str) == 0) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

// 释放Map
void freeMap() {
    int i;
    MapNode *cur, *node;
    for (i = 0; i < g_size; i++) {
        cur = g_map[i];
        while (cur) {
            node = cur;
            cur = cur->next;
            free(node->str);
            free(node);
        }
    }
    free(g_map);
    g_map = NULL;
}

int main() {
    MapNode *node;
    char str[1000];
    ULL hash;
    int i, str_len;

    // 输入 n
    scanf("%d", &g_size);
    // 初始化 Map
    g_map = (MapNode **) malloc(sizeof(MapNode *) * g_size);
    memset(g_map, 0, sizeof(MapNode *) * g_size);
    for (i = 0; i < g_size; i++) {
        // 输入字符串
        scanf("%s", str);
        // 计算哈希值
        hash = getHash(str, &str_len);
        // 查找结点
        node = findKey(str, hash);
        if (node != NULL) {
            node->count++;      // 更新结点的count值
        } else {
            node = (MapNode *) malloc(sizeof(MapNode));    // 创建一个新的结点指针
            node->str = (char *) malloc(sizeof(char) * (str_len + 1));      // 在堆上开辟一片连续空间用于存放字符串
            strcpy(node->str, str);         // 将栈上的字符串拷贝到堆上
            node->count = 1;
            node->next = node->next = g_map[hash % g_size];         // 拉链法解决哈希冲突
            g_map[hash % g_size] = node;
        }
    }
    // 输入待查找的字符串
    scanf("%s", str);
    hash = getHash(str, &str_len);
    node = findKey(str, hash);
    printf("%d\n", node == NULL ? 0 : node->count);
    freeMap();
    return 0;
}