面试题：C语言哈希表设计之简单实现

Question

请用C语言设计一个简单的哈希表，用于存储整数。要求实现插入和查找操作。哈希表的大小固定为10，使用链地址法解决哈希冲突。请给出完整的代码实现，并对关键部分进行注释。

Answer 1

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

// 定义哈希表节点结构体
typedef struct HashNode {
    int data;
    struct HashNode* next;
} HashNode;

// 定义哈希表结构体
typedef struct HashTable {
    HashNode* table[10]; // 哈希表数组，大小为10
} HashTable;

// 初始化哈希表
void initHashTable(HashTable* hashTable) {
    for (int i = 0; i < 10; i++) {
        hashTable->table[i] = NULL;
    }
}

// 哈希函数，返回哈希值
int hashFunction(int key) {
    return key % 10;
}

// 插入操作
void insert(HashTable* hashTable, int value) {
    int index = hashFunction(value);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->data = value;
    newNode->next = hashTable->table[index];
    hashTable->table[index] = newNode;
}

// 查找操作
int search(HashTable* hashTable, int value) {
    int index = hashFunction(value);
    HashNode* current = hashTable->table[index];
    while (current != NULL) {
        if (current->data == value) {
            return 1; // 找到
        }
        current = current->next;
    }
    return 0; // 未找到
}

int main() {
    HashTable hashTable;
    initHashTable(&hashTable);

    insert(&hashTable, 12);
    insert(&hashTable, 22);
    insert(&hashTable, 32);

    if (search(&hashTable, 22)) {
        printf("找到元素 22\n");
    } else {
        printf("未找到元素 22\n");
    }

    if (search(&hashTable, 42)) {
        printf("找到元素 42\n");
    } else {
        printf("未找到元素 42\n");
    }

    return 0;
}

关键部分注释

1. 哈希表节点结构体：定义了哈希表节点的结构，每个节点包含一个整数值和一个指向下一个节点的指针。
2. 哈希表结构体：定义了哈希表，它是一个包含10个指针的数组，每个指针指向一个链表头节点。
3. 初始化哈希表：将哈希表数组中的每个指针初始化为NULL。
4. 哈希函数：使用取模运算将整数映射到0到9之间的哈希值。
5. 插入操作：
   • 计算插入值的哈希值。
   • 创建新节点并将其插入到对应哈希值的链表头部。
6. 查找操作：
   • 计算查找值的哈希值。
   • 遍历对应链表，查找是否存在该值。