C语言实现哈希表查找: 优化查找效率

C语言实现高效哈希表查找

本文将带你学习如何使用C语言构建哈希表，并实现快速的人名查找功能。我们将重点关注如何优化查找效率，确保平均查找长度不超过指定值。

一、问题分析

假设我们需要在一个班级中快速查找学生姓名对应的学号。由于班级人数相对固定，我们可以利用哈希表这种数据结构来提高查找效率。

二、哈希表构建

我们需要设计一个哈希函数，将人名映射到哈希表中的特定位置。同时，还需要选择合适的冲突解决方法来处理哈希冲突（即不同的人名被映射到同一个位置的情况）。

三、C语言代码实现

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

#define TABLE_SIZE 10 // 哈希表大小
#define R 3 // 平均查找长度

typedef struct {
    char name[20];
    int id;
} Person;

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

int hash(char* name) {
    int sum = 0;
    for (int i = 0; i < strlen(name); i++) {
        sum += name[i];
    }
    return sum % TABLE_SIZE;
}

void insert(HashTable* table, Person person) {
    int index = hash(person.name);
    while (table->data[index].id != -1) {
        index = (index + 1) % TABLE_SIZE; // 线性探测法解决冲突
    }
    table->data[index] = person;
    table->size++;
}

int search(HashTable* table, char* name) {
    int index = hash(name);
    int count = 0;
    while (table->data[index].id != -1) {
        if (strcmp(table->data[index].name, name) == 0) {
            return index;
        }
        index = (index + 1) % TABLE_SIZE;
        count++;
        if (count > R) {
            return -1; // 超过平均查找长度，返回-1表示未找到
        }
    }
    return -1; // 未找到
}

int main() {
    HashTable table;
    table.size = 0;
    table.data = (Person*)malloc(sizeof(Person) * TABLE_SIZE);
    for (int i = 0; i < TABLE_SIZE; i++) {
        table.data[i].id = -1; // 初始化哈希表
    }

    // 添加一些人名到哈希表中
    insert(&table, (Person){'Alice', 1});
    insert(&table, (Person){'Bob', 2});
    insert(&table, (Person){'Charlie', 3});
    insert(&table, (Person){'David', 4});
    insert(&table, (Person){'Eve', 5});

    // 在哈希表中查找指定人名
    char name[20];
    printf('请输入要查找的人名：');
    scanf('%s', name);
    int index = search(&table, name);
    if (index != -1) {
        printf('找到了，该人的id是：%d\n', table.data[index].id);
    } else {
        printf('未找到该人\n');
    }

    free(table.data);
    return 0;
}

四、代码解读

我们使用 TABLE_SIZE 定义哈希表的大小，使用 R 定义平均查找长度。
Person 结构体表示单个学生的姓名和id信息。
HashTable 结构体表示哈希表，包含一个指向Person数组的指针和表的大小。
hash 函数计算人名的哈希值，这里使用简单的字符串ASCII码求和取模算法。
insert 函数将新的人名信息插入到哈希表中，使用线性探测法解决冲突。
search 函数在哈希表中查找指定人名，如果找到则返回其索引，否则返回-1。
main 函数中，我们初始化哈希表，插入示例数据，并演示如何进行查找操作。

五、总结

通过本文，你学习了如何使用C语言构建哈希表并实现快速的人名查找功能。我们还探讨了如何优化查找效率，确保平均查找长度不超过指定值。在实际应用中，你可以根据具体需求选择不同的哈希函数和冲突解决方法，以达到最佳性能。