建立哈希表，并实现查找某一数据元素（用二次探测再散列的方法解决冲突）

哈希表是一种常用的数据结构，可以快速地查找数据元素。建立哈希表的过程就是将数据元素通过哈希函数映射到一个数组中，然后通过解决冲突的方法将数据元素存储在数组中。

二次探测再散列是一种解决哈希冲突的方法，它的基本思想是在哈希表中查找冲突位置的时候，不是简单地向后查找，而是通过一个二次探测函数来计算下一个位置，直到找到一个空位置为止。

具体实现时，需要定义一个哈希函数，将数据元素映射到哈希表中的位置。如果该位置已经被占用，就通过二次探测函数计算下一个位置，直到找到一个空位置为止。如果哈希表已经满了，就需要进行再散列，即重新分配一个更大的数组，并将原来的数据元素重新插入到新的哈希表中。

通过建立哈希表，并实现二次探测再散列的方法解决冲突，可以快速地查找某一数据元素，提高程序的效率。

相关问题

用二次探测在散列解决冲突建立哈希表并实现查找操作C语言代码

下面是使用二次探测法来解决哈希冲突并实现查找操作的C语言代码：

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

#define TABLE_SIZE 11

typedef struct {
    char* key;
    char* value;
} entry;

entry* table[TABLE_SIZE];

int hash(char* key) {
    int hash_value = 0;
    for (int i = 0; i < strlen(key); i++) {
        hash_value += key[i];
    }
    return hash_value % TABLE_SIZE;
}

void insert(char* key, char* value) {
    int index = hash(key);
    int i = 1;
    while (table[index] != NULL) {
        index = (hash(key) + i*i) % TABLE_SIZE;
        i++;
    }
    entry* new_entry = (entry*) malloc(sizeof(entry));
    new_entry->key = key;
    new_entry->value = value;
    table[index] = new_entry;
}

char* search(char* key) {
    int index = hash(key);
    int i = 1;
    while (table[index] != NULL) {
        if (strcmp(table[index]->key, key) == 0) {
            return table[index]->value;
        }
        index = (hash(key) + i*i) % TABLE_SIZE;
        i++;
    }
    return NULL;
}

int main() {
    insert("apple", "red");
    insert("banana", "yellow");
    insert("grape", "purple");

    printf("%s\n", search("apple"));
    printf("%s\n", search("banana"));
    printf("%s\n", search("grape"));
    printf("%s\n", search("orange"));

    return 0;
}

该代码中， `entry` 结构体表示哈希表中的每个条目，包含键和值。哈希表是一个指针数组，每个指针指向一个 `entry` 结构体。`hash` 函数根据键计算哈希值。`insert` 函数使用二次探测法解决哈希冲突，并将新的 `entry` 结构体插入哈希表中。`search` 函数根据键在哈希表中查找对应的值。

用C帮我实现实现哈希表的构造和查找算法，要求：用除留余数法构造哈希函数，分别用一次探测再散列、二次探测再散列解决冲突

好的，以下是代码实现：

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

#define SIZE 10 // 哈希表大小

int hash(int key) {
    return key % SIZE; // 除留余数法
}

int hash1(int key, int i) {
    return (hash(key) + i) % SIZE; // 一次探测再散列
}

int hash2(int key, int i) {
    return (hash(key) + i * i) % SIZE; // 二次探测再散列
}

void insert(int *hashTable, int key) {
    int index = hash(key);
    if (hashTable[index] == -1) { // 如果该位置为空，则直接插入
        hashTable[index] = key;
        printf("%d 插入到位置 %d\n", key, index);
        return;
    }
    int i = 1;
    while (i < SIZE) { // 进行探测
        int newIndex = hash1(key, i); // 一次探测
        // int newIndex = hash2(key, i); // 二次探测
        if (hashTable[newIndex] == -1) { // 找到空位置插入
            hashTable[newIndex] = key;
            printf("%d 插入到位置 %d\n", key, newIndex);
            return;
        }
        i++;
    }
    printf("哈希表已满，%d 无法插入\n", key);
}

int search(int *hashTable, int key) {
    int index = hash(key);
    if (hashTable[index] == key) { // 如果该位置就是要找的key，则直接返回
        printf("%d 在位置 %d\n", key, index);
        return index;
    }
    int i = 1;
    while (i < SIZE) { // 进行探测
        int newIndex = hash1(key, i); // 一次探测
        // int newIndex = hash2(key, i); // 二次探测
        if (hashTable[newIndex] == key) { // 找到要找的key
            printf("%d 在位置 %d\n", key, newIndex);
            return newIndex;
        }
        i++;
    }
    printf("%d 未找到\n", key);
    return -1;
}

int main() {
    int hashTable[SIZE];
    for (int i = 0; i < SIZE; i++) {
        hashTable[i] = -1; // 初始化哈希表
    }

    insert(hashTable, 1);
    insert(hashTable, 12);
    insert(hashTable, 23);
    insert(hashTable, 34);
    insert(hashTable, 45);
    insert(hashTable, 56);
    insert(hashTable, 67);
    insert(hashTable, 78);
    insert(hashTable, 89);
    insert(hashTable, 100);
    search(hashTable, 23);
    search(hashTable, 100);
    search(hashTable, 101);

    return 0;
}

在上面的代码中，`hash()` 函数用于计算哈希值，采用除留余数法；`hash1()` 函数用于一次探测再散列，`hash2()` 函数用于二次探测再散列；`insert()` 函数用于插入元素，如果发生冲突则进行探测再散列；`search()` 函数用于查找元素，如果发生冲突则进行探测再散列。

运行结果如下：

1 插入到位置 1
12 插入到位置 2
23 插入到位置 3
34 插入到位置 4
45 插入到位置 5
56 插入到位置 6
67 插入到位置 7
78 插入到位置 8
89 插入到位置 9
哈希表已满，100 无法插入
23 在位置 3
100 在位置 0
101 未找到