c语言哈希表(散列表)概念原理以及代码实现

哈希表是一种数据结构，用于实现关联数组（Associative Array）或映射（Map）这样的抽象数据类型。它通过将关键字映射到表中的位置来实现快速的数据检索。

概念原理：

1. 哈希函数（Hash Function）： 哈希表的核心是哈希函数，它将关键字映射到表中的索引。理想情况下，哈希函数应该是高效的，并且能够将关键字均匀地分散到表的不同位置。

2. 数组（Array）： 哈希表通常基于数组实现。每个数组元素称为槽（Bucket），存储一个键值对。

3. 冲突处理： 由于可能存在不同的关键字映射到相同的索引位置（冲突），哈希表需要采取措施来解决这个问题。常见的冲突解决方法包括链地址法（Chaining）和开放寻址法（Open Addressing）。

代码实现（以开放寻址法为例）：

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

#define TABLE_SIZE 10

typedef struct {
    int key;
    int value;
} KeyValuePair;

typedef struct {
    KeyValuePair* table[TABLE_SIZE];
} HashMap;

// 哈希函数
int hash(int key) {
    return key % TABLE_SIZE;
}

// 插入键值对
void insert(HashMap* map, int key, int value) {
    int index = hash(key);

    while (map->table[index] != NULL) {
        index = (index + 1) % TABLE_SIZE; // 开放寻址法中的线性探测
    }

    KeyValuePair* pair = (KeyValuePair*)malloc(sizeof(KeyValuePair));
    pair->key = key;
    pair->value = value;

    map->table[index] = pair;
}

// 查找键对应的值
int get(HashMap* map, int key) {
    int index = hash(key);

    while (map->table[index] != NULL) {
        if (map->table[index]->key == key) {
            return map->table[index]->value;
        }

        index = (index + 1) % TABLE_SIZE;
    }

    return -1; // 未找到
}

int main() {
    HashMap map;
    
    // 插入键值对
    insert(&map, 1, 10);
    insert(&map, 2, 20);
    insert(&map, 11, 30);

    // 查找键对应的值
    printf("Value for key 1: %d\\n", get(&map, 1));
    printf("Value for key 2: %d\\n", get(&map, 2));
    printf("Value for key 11: %d\\n", get(&map, 11));

    return 0;
}

这是一个简单的使用开放寻址法解决冲突的哈希表实现。