哈希表二次探测C语言实现

哈希表是一种数据结构，它通过将键值对映射到一个固定大小的数组上，实现了快速的插入、查找和删除操作。在处理冲突（即两个键值对映射到了同一个索引）时，常见的二次探测策略有线性探测法（Linear Probing）和链地址法（Chaining）。这里以线性探测法为例，简单解释一下在C语言中的基本实现：

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

#define TABLE_SIZE 100

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

// 哈希函数，这里使用简单的取模运算
int hash(int key, int size) {
    return key % size;
}

// 线性探测哈希表
typedef struct HashTable {
    Entry table[TABLE_SIZE];
    int count; // 记录元素个数
} HashTable;

HashTable *createHashTable() {
    HashTable *ht = (HashTable*)malloc(sizeof(HashTable));
    ht->count = 0;
    return ht;
}

// 插入元素，如果发生冲突则线性探测
void insert(HashTable *ht, int key, int value) {
    int index = hash(key, TABLE_SIZE);
    while (ht->table[index].key != 0) { // 直至找到空位置
        if (ht->table[index].key == key) { // 如果找到相同的键，更新值
            ht->table[index].value = value;
            break;
        }
        index = (index + 1) % TABLE_SIZE; // 探测下一个位置
    }
    ht->table[index].key = key;
    ht->table[index].value = value;
    ht->count++;
}

// 查找元素
int search(HashTable *ht, int key) {
    int index = hash(key, TABLE_SIZE);
    while (ht->table[index].key != 0 && ht->table[index].key != key) {
        index = (index + 1) % TABLE_SIZE;
    }
    return ht->table[index].value;
}

// 其他操作类似...