C 語言手撕一個 HashMap

hashmap 之鏈地址法

1、定義哈希表 及 哈希桶 結構體

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

// 定義哈希桶的節點結構體
typedef struct Node {
    char* key;
    int value;
    struct Node* next;
} Node;

// 定義哈希表結構體
typedef struct HashMap {
    int size;
    Node** buckets;
} HashMap;

2、創建指定大小的哈希表

// 創建指定大小的哈希表
HashMap* createHashMap(int size) {
    HashMap* map = (HashMap*)malloc(sizeof(HashMap));
    map->size = size;
    map->buckets = (Node**)calloc(size, sizeof(Node*));
    return map;
}

3、哈希函數

// 哈希函數
int hash(HashMap* map, char* key) {
    int sum = 0;
    for (int i = 0; i < strlen(key); i++) {
        sum += key[i];
    }
    return sum % map->size;
}

4、HashMap put 操作

void put(HashMap* map, char* key, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->value = value;
    newNode->next = NULL;

    int index = hash(map, key);
    Node* curr = map->buckets[index];

    if (curr == NULL) {
        map->buckets[index] = newNode;
    } else {
        while (curr->next != NULL) {
            curr = curr->next;
        }
        curr->next = newNode;
    }
}

5、HashMap get 操作

// 從哈希表中獲取指定鍵的值
int get(HashMap* map, char* key) {
    int index = hash(map, key);
    Node* curr = map->buckets[index];

    while (curr != NULL) {
        if (strcmp(curr->key, key) == 0) {
            return curr->value;
        }
        curr = curr->next;
    }

    return -1;  // 如果沒有找到，返回 -1
}

6、釋放內存

// 釋放哈希表的內存
void freeHashMap(HashMap* map) {
    for (int i = 0; i < map->size; i++) {
        Node* curr = map->buckets[i];
        while (curr != NULL) {
            Node* temp = curr;
            curr = curr->next;
            free(temp->key);
            free(temp);
        }
    }
    free(map->buckets);
    free(map);
}

7、main 方法測試

int main() {
    HashMap* map = createHashMap(10);
char a[] = "apple",b[] = "banana",o[] = "orange",w[] = "watermelon";
    put(map, a, 1);
    put(map, b, 2);
    put(map, o, 3);

    printf("Value of 'apple': %d\n", get(map, a));
    printf("Value of 'banana': %d\n", get(map, b));
    printf("Value of 'orange': %d\n", get(map, o));
    printf("Value of 'watermelon': %d\n", get(map, w));
    freeHashMap(map);

    return 0;
}

運行結果：

result

該 HashMap 使用了鏈地址法來處理衝突，即在哈希桶中的每個位置存儲一個鏈表，哈希衝突時將鍵值對添加到鏈表的末尾。

createHashMap 函數創建了一個指定大小的哈希表，put 函數向哈希表中插入鍵值對，get 函數從哈希表中獲取指定鍵的值，freeHashMap 函數用於釋放哈希表的內存。在 main 函數中我們可以看到如何使用這個 HashMap 來存儲和獲取鍵值對的方式。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/RxQJaRH9Q-oLEQHSiK_tqw

猜你喜歡