面试题：C语言中哈希表的冲突解决方法

常见哈希冲突解决方法

开放定址法：当发生冲突时，通过某种探测序列在哈希表中寻找下一个空闲位置。常见的探测方式有线性探测（每次探测间隔为1）、二次探测（探测间隔为 $i^2$，$i$ 从1开始）等。
链地址法：将所有哈希值相同的元素用链表连接起来，这样哈希表的每个位置就存储一个链表头指针，发生冲突时将元素插入到对应链表中。

用C语言代码实现链地址法

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

// 定义链表节点
typedef struct Node {
    int key;
    struct Node* next;
} Node;

// 定义哈希表
typedef struct HashTable {
    Node* *table;
    int size;
} HashTable;

// 创建新节点
Node* createNode(int key) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = NULL;
    return newNode;
}

// 初始化哈希表
HashTable* createHashTable(int size) {
    HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));
    hashTable->size = size;
    hashTable->table = (Node**)malloc(size * sizeof(Node*));
    for (int i = 0; i < size; i++) {
        hashTable->table[i] = NULL;
    }
    return hashTable;
}

// 哈希函数
int hashFunction(int key, int size) {
    return key % size;
}

// 插入元素到哈希表
void insert(HashTable* hashTable, int key) {
    int index = hashFunction(key, hashTable->size);
    Node* newNode = createNode(key);
    if (hashTable->table[index] == NULL) {
        hashTable->table[index] = newNode;
    } else {
        Node* current = hashTable->table[index];
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

// 查找元素
int search(HashTable* hashTable, int key) {
    int index = hashFunction(key, hashTable->size);
    Node* current = hashTable->table[index];
    while (current != NULL) {
        if (current->key == key) {
            return 1;
        }
        current = current->next;
    }
    return 0;
}

// 释放哈希表内存
void freeHashTable(HashTable* hashTable) {
    for (int i = 0; i < hashTable->size; i++) {
        Node* current = hashTable->table[i];
        Node* next;
        while (current != NULL) {
            next = current->next;
            free(current);
            current = next;
        }
    }
    free(hashTable->table);
    free(hashTable);
}

int main() {
    HashTable* hashTable = createHashTable(10);
    insert(hashTable, 12);
    insert(hashTable, 22);
    insert(hashTable, 32);

    if (search(hashTable, 22)) {
        printf("Element 22 found\n");
    } else {
        printf("Element 22 not found\n");
    }

    freeHashTable(hashTable);
    return 0;
}

星途面试题库

面试题：C语言中哈希表的冲突解决方法

知识考点

面试题答案

常见哈希冲突解决方法

用C语言代码实现链地址法