哈希表实验C语言版实现

下面是“哈希表实验C语言版实现”的完整攻略。

一、前置知识

• C 语言基础
• 数据结构 - 哈希表

二、哈希表实现原理

哈希表是一种数据结构，是用来存储键值对的，通过计算每个键的哈希值，将键值对存储到一个数组中。哈希表中的每个键值对都根据一个哈希函数映射到一个位置，这个位置就是数据在数组里的下标。哈希表通常具有O(1)的查找时间。

哈希表需要以下几个关键要素：

• 哈希函数
• 数组桶(bucket)
• 冲突解决方法

哈希表实现的核心是哈希函数。哈希函数将键映射到整数，这个整数就是数据在数组里的下标。数组桶存储对应下标的键值对。当出现哈希冲突时，需要用一些方法来解决，比如链表。

三、C 语言版哈希表实现

1. 哈希函数

哈希函数将键映射到整数，可以用一些简单的算法来实现，比如模运算。

unsigned int hash(const char *key, int table_size) {
    unsigned int hashval = 0;
    while (*key != '\0') {
        hashval = *key + 31 * hashval;
        key++;
    }
    return hashval % table_size;
}

这个哈希函数将字符串转换为整数，然后对表大小取模。这样能确保计算出的哈希值不会超出表的范围。

2. 数组桶

在实现哈希表时需要一个数组来存储键值对。下面是数组结构体的定义：

typedef struct {
    char *key;
    int value;
} entry;

typedef struct {
    int size;
    int count;
    entry *entries;
} hashmap;

hashmap结构体中包含一个整数size，表示数组的大小，一个整数count，表示当前哈希表的大小。entries是一个指向entry结构体的指针数组，用来存储键值对。

3. 冲突解决方法

在哈希表中，有时候会出现两个键映射到同一个位置的情况，这就是哈希冲突。解决哈希冲突的方法有很多种，比如链表法和开放地址法。

在链表法中，每个数组下标都存储一个链表，如果出现哈希冲突，就将新的键值对加入链表的末尾。

typedef struct {
    char *key;
    int value;
    struct entry *next;
} entry;

typedef struct {
    int size;
    int count;
    entry **entries;
} hashmap;

在entry结构体中，还增加了一个指针next，用来指向下一个键值对。在hashmap结构体中，entries变成了一个指向指针的数组。

4. 完整代码示例

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

typedef struct {
    char *key;
    int value;
    struct entry *next;
} entry;

typedef struct {
    int size;
    int count;
    entry **entries;
} hashmap;

hashmap *create_hashmap(int size) {
    hashmap *map = malloc(sizeof(hashmap));
    map->size = size;
    map->count = 0;
    map->entries = calloc(size, sizeof(entry *));
    return map;
}

unsigned int hash(const char *key, int table_size) {
    unsigned int hashval = 0;
    while (*key != '\0') {
        hashval = *key + 31 * hashval;
        key++;
    }
    return hashval % table_size;
}

entry *create_entry(const char *key, int value) {
    entry *e = malloc(sizeof(entry));
    e->key = strdup(key);
    e->value = value;
    e->next = NULL;
    return e;
}

void insert(hashmap *map, const char *key, int value) {
    int index = hash(key, map->size);
    entry *entries = map->entries[index];
    if (entries == NULL) {
        map->entries[index] = create_entry(key, value);
        map->count++;
    } else {
        while (entries->next != NULL && strcmp(entries->key, key) != 0) {
            entries = entries->next;
        }
        if (strcmp(entries->key, key) == 0) {
            entries->value = value;
        } else {
            entries->next = create_entry(key, value);
            map->count++;
        }
    }
}

int get(hashmap *map, const char *key) {
    int index = hash(key, map->size);
    entry *entries = map->entries[index];
    while (entries != NULL && strcmp(entries->key, key) != 0) {
        entries = entries->next;
    }
    if (entries == NULL) {
        return -1;
    } else {
        return entries->value;
    }
}

void delete(hashmap *map, const char *key) {
    int index = hash(key, map->size);
    entry *entries = map->entries[index], *prev = NULL;
    while (entries != NULL && strcmp(entries->key, key) != 0) {
        prev = entries;
        entries = entries->next;
    }
    if (entries == NULL) {
        return;
    } else {
        if (prev == NULL) {
            map->entries[index] = entries->next;
        } else {
            prev->next = entries->next;
        }
        free(entries->key);
        free(entries);
        map->count--;
    }
}

void print_hashmap(hashmap *map) {
    for (int i = 0; i < map->size; i++) {
        entry *entries = map->entries[i];
        if (entries != NULL) {
            printf("Bucket %d: ", i);
            while (entries != NULL) {
                printf("(%s, %d) ", entries->key, entries->value);
                entries = entries->next;
            }
            printf("\n");
        }
    }
}

int main() {
    hashmap *map = create_hashmap(5);

    insert(map, "key1", 10);
    insert(map, "key2", 20);
    insert(map, "key3", 30);
    insert(map, "key4", 40);

    printf("key1: %d\n", get(map, "key1"));
    printf("key2: %d\n", get(map, "key2"));
    printf("key3: %d\n", get(map, "key3"));
    printf("key4: %d\n", get(map, "key4"));
    printf("key5: %d\n", get(map, "key5"));

    printf("\n");
    print_hashmap(map);

    delete(map, "key1");
    delete(map, "key3");

    printf("\n");
    print_hashmap(map);

    return 0;
}

上面的示例代码中，首先创建了一个大小为5的哈希表，然后插入了4个键值对。接下来，使用get函数获取了每个键的值，再尝试获取一个不存在的键。最后，调用了print_hashmap函数打印哈希表，然后分别删除key1和key3键值对，再次打印哈希表。