面试题：C语言哈希表在多线程环境下的设计与实现

整体设计思路

哈希表结构设计：定义哈希表的基本结构，包括哈希桶数组、哈希函数以及链表节点结构。
同步机制选择：对于并发读写操作，选择读写锁（pthread_rwlock_t）。读操作并发执行，写操作独占访问，以此平衡性能和数据一致性。
锁粒度控制：对每个哈希桶设置一个读写锁，而不是对整个哈希表设置一把锁，这样可以提高并发性能。

关键代码片段

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

#define HASH_TABLE_SIZE 10

// 链表节点结构
typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

// 哈希表结构
typedef struct HashTable {
    Node* buckets[HASH_TABLE_SIZE];
    pthread_rwlock_t locks[HASH_TABLE_SIZE];
} HashTable;

// 初始化哈希表
void initHashTable(HashTable* hashTable) {
    for (int i = 0; i < HASH_TABLE_SIZE; ++i) {
        hashTable->buckets[i] = NULL;
        pthread_rwlock_init(&hashTable->locks[i], NULL);
    }
}

// 哈希函数
unsigned long hashFunction(int key) {
    return key % HASH_TABLE_SIZE;
}

// 插入键值对
void insert(HashTable* hashTable, int key, int value) {
    unsigned long index = hashFunction(key);
    pthread_rwlock_wrlock(&hashTable->locks[index]);

    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = hashTable->buckets[index];
    hashTable->buckets[index] = newNode;

    pthread_rwlock_unlock(&hashTable->locks[index]);
}

// 查询值
int get(HashTable* hashTable, int key) {
    unsigned long index = hashFunction(key);
    pthread_rwlock_rdlock(&hashTable->locks[index]);

    Node* current = hashTable->buckets[index];
    while (current != NULL) {
        if (current->key == key) {
            int value = current->value;
            pthread_rwlock_unlock(&hashTable->locks[index]);
            return value;
        }
        current = current->next;
    }

    pthread_rwlock_unlock(&hashTable->locks[index]);
    return -1; // 未找到
}

// 清理哈希表
void freeHashTable(HashTable* hashTable) {
    for (int i = 0; i < HASH_TABLE_SIZE; ++i) {
        pthread_rwlock_destroy(&hashTable->locks[i]);
        Node* current = hashTable->buckets[i];
        Node* next;
        while (current != NULL) {
            next = current->next;
            free(current);
            current = next;
        }
    }
}

总结

通过上述设计，我们利用读写锁和细粒度的锁控制，实现了一个线程安全的哈希表，在多线程环境下能有效平衡性能和数据一致性。插入和删除操作使用写锁，保证数据的一致性；查询操作使用读锁，允许多个线程同时进行读操作，提高并发性能。

星途面试题库

面试题：C语言哈希表在多线程环境下的设计与实现

知识考点

面试题答案

整体设计思路

关键代码片段

总结