哈希表二次探测法c语言代码

哈希表是一种通过哈希函数将关键字映射到数组位置的数据结构，当发生碰撞（两个关键字经过哈希函数得到相同的索引）时，常见的解决方法之一就是二次探测法。这里是一个简单的哈希表（使用链地址法处理冲突）的二次探测法 C 语言实现：

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

typedef struct Node {
    int key;
    int value;
    struct Node* next;
} HashNode;

typedef struct HashTable {
    int size;
    HashNode** table;
} HashTable;

HashTable* createHashTable(int size) {
    HashTable* hash = (HashTable*)malloc(sizeof(HashTable));
    hash->size = size;
    hash->table = (HashNode**)calloc(size, sizeof(HashNode*));
    return hash;
}

int getHashValue(int key, int size) {
    return key % size; // 通常使用取模运算作为哈希函数
}

HashTableNode* search(HashTable* hash, int key) {
    int index = getHashValue(key, hash->size);
    HashNode* node = hash->table[index];
    
    while (node != NULL && node->key != key) {
        if (node->next == NULL) break;
        node = node->next;
        index = (index + 1) % hash->size; // 二次探测
    }
    
    return node;
}

void insert(HashTable* hash, int key, int value) {
    int index = getHashValue(key, hash->size);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = hash->table[index];

    if (hash->table[index] != NULL) {
        HashNode* current = hash->table[index];
        while (current->next != NULL && current->next->key != key) {
            current = current->next;
        }
        if (current->next != NULL) {
            newNode->next = current->next;
        } else {
            hash->table[index] = newNode;
        }
    } else {
        hash->table[index] = newNode;
    }
}

void display(HashTable* hash) {
    for (int i = 0; i < hash->size; i++) {
        HashNode* node = hash->table[i];
        while (node != NULL) {
            printf("%d -> %d, ", node->key, node->value);
            node = node->next;
        }
        printf("\n");
    }
}

int main() {
    HashTable* hash = createHashTable(10);
    insert(hash, 5, "One");
    insert(hash, 7, "Two");
    insert(hash, 9, "Three");

    display(hash);

    return 0;
}

这个程序首先创建了一个哈希表，然后插入一些键值对。`search` 函数用于查找给定键，如果找到则返回节点，如果没有则返回 `NULL`。`insert` 函数会处理哈希碰撞，使用二次探测法寻找下一个可用的位置。最后，`display` 函数用于展示整个哈希表的内容。