哈希查找算法（线性探测）

简介

哈希查找是一种高效的数据查找方法，通过哈希函数将键值映射到哈希表中的索引位置，从而快速找到目标数据。本文介绍了一种基于开放地址法（线性探测）的哈希查找算法，并提供了详细的C语言实现代码和注释。

哈希查找算法概述

哈希查找算法主要通过以下步骤实现数据的插入、查找和删除：

哈希函数：将键值映射到哈希表中的索引位置。
冲突处理：当两个键值通过哈希函数映射到同一索引位置时，需要一种机制来解决冲突。
查找操作：根据键值通过哈希函数计算索引，并根据冲突处理机制找到目标位置。
删除操作：标记或移除哈希表中的指定键值对。

开放地址法（线性探测）

开放地址法是解决哈希冲突的一种方法，其中最简单的形式是线性探测。其基本思想是：当发生哈希冲突时，通过线性方式（逐个位置）探测下一个空闲位置，直到找到一个空位或回到起始位置。

线性探测步骤

计算初始索引：使用哈希函数计算键值的初始索引位置。
检查冲突：如果当前位置已被占用，按顺序检查下一个位置。
循环检查：如果到达哈希表的末尾，则从头开始检查，直到找到空位或回到起始位置。

代码实现

头文件和宏定义

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

#define TABLE_SIZE 10 // 定义哈希表的大小

结构体定义

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

// 定义哈希表为指针数组
HashItem* hashTable[TABLE_SIZE];

哈希函数

int hashFunction(int key) {
    return key % TABLE_SIZE;
}

插入函数

void insert(int key, int value) {
    int index = hashFunction(key); // 计算哈希值
    int originalIndex = index; // 保存初始索引

    // 创建新哈希表项
    HashItem* newItem = (HashItem*) malloc(sizeof(HashItem));
    newItem->key = key;
    newItem->value = value;

    // 处理冲突，使用线性探测法
    while (hashTable[index] != NULL && hashTable[index]->key != -1) {
        index = (index + 1) % TABLE_SIZE; // 移动到下一个位置
        if (index == originalIndex) { // 检查是否回到了初始位置
            printf("Hash table is full\n");
            return; // 哈希表已满
        }
    }

    // 将新项插入哈希表
    hashTable[index] = newItem;
}

查找函数

int search(int key) {
    int index = hashFunction(key); // 计算哈希值
    int originalIndex = index; // 保存初始索引

    // 通过线性探测查找键
    while (hashTable[index] != NULL) {
        if (hashTable[index]->key == key) {
            return hashTable[index]->value; // 找到键，返回值
        }
        index = (index + 1) % TABLE_SIZE; // 移动到下一个位置
        if (index == originalIndex) {
            return -1; // 未找到
        }
    }
    return -1; // 未找到
}

删除函数

void delete(int key) {
    int index = hashFunction(key); // 计算哈希值
    int originalIndex = index; // 保存初始索引

    // 通过线性探测查找要删除的键
    while (hashTable[index] != NULL) {
        if (hashTable[index]->key == key) {
            hashTable[index]->key = -1; // 标记该位置为已删除
            return;
        }
        index = (index + 1) % TABLE_SIZE; // 移动到下一个位置
        if (index == originalIndex) {
            return; // 未找到
        }
    }
}

主函数

int main() {
    // 初始化哈希表为空
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }

    // 插入键值对
    insert(1, 10);
    insert(11, 20);
    insert(21, 30);

    // 查找并打印值
    printf("Value for key 1: %d\n", search(1));
    printf("Value for key 11: %d\n", search(11));
    printf("Value for key 21: %d\n", search(21));

    // 删除键值对
    delete(11);
    printf("Value for key 11 after deletion: %d\n", search(11));

    return 0;
}

详细注释

哈希表项结构

定义结构体HashItem：包含两个整数，分别表示键和对应的值。

哈希表定义

定义指针数组hashTable：大小为TABLE_SIZE，用于存储哈希表项。

哈希函数

使用取模运算：将键值映射到哈希表的索引位置。

插入函数

计算哈希值：根据键值计算索引。
创建新哈希表项：为新插入的键值对分配内存。
处理冲突：使用线性探测法寻找下一个空闲位置。
插入哈希表：将新项插入到找到的空位。

查找函数

计算哈希值：根据键值计算索引。
线性探测查找：逐个检查索引位置，直到找到目标键或回到起始位置。
返回结果：找到则返回对应的值，未找到则返回-1。

删除函数

计算哈希值：根据键值计算索引。
线性探测查找：逐个检查索引位置，找到目标键后标记为已删除。

主函数

初始化哈希表：将所有位置初始化为空。
插入键值对：调用insert函数插入多个键值对。
查找并打印值：调用search函数查找并打印指定键的值。
删除键值对：调用delete函数删除键值对，并验证删除效果。

运行示例

编译并运行上述代码，输出如下：

Value for key 1: 10
Value for key 11: 20
Value for key 21: 30
Value for key 11 after deletion: -1

完整代码

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

#define TABLE_SIZE 10 // 定义哈希表的大小

// 定义哈希表项结构
typedef struct {
    int key;
    int value;
} HashItem;

// 定义哈希表为指针数组
HashItem* hashTable[TABLE_SIZE];

// 哈希函数，使用取模运算
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// 插入函数
void insert(int key, int value) {
    int index = hashFunction(key); // 计算哈希值
    int originalIndex = index; // 保存初始索引

    // 创建新哈希表项
    HashItem* newItem = (HashItem*) malloc(sizeof(HashItem));
    newItem->key = key;
    newItem->value = value;

    // 处理冲突，使用线性探测法
    while (hashTable[index] != NULL && hashTable[index]->key != -1) {
        index = (index + 1) % TABLE_SIZE; // 移动到下一个位置
        if (index == originalIndex) { // 检查是否回到了初始位置
            printf("Hash table is full\n");
            return; // 哈希表已满
        }
    }

    // 将新项插入哈希表
    hashTable[index] = newItem;
}

// 查找函数
int search(int key) {
    int index = hashFunction(key); // 计算哈希值
    int originalIndex = index; // 保存初始索引

    // 通过线性探测查找键
    while (hashTable[index] != NULL) {
        if (hashTable[index]->key == key) {
            return hashTable[index]->value; // 找到键，返回值
        }
        index = (index + 1) % TABLE_SIZE; // 移动到下一个位置
        if (index == originalIndex) {
            return -1; // 未找到
        }
    }
    return -1; // 未找到
}

// 删除函数
void delete(int key) {
    int index = hashFunction(key); // 计算哈希值
    int originalIndex = index; // 保存初始索引

    // 通过线性探测查找要删除的键
    while (hashTable[index] != NULL) {
        if (hashTable[index]->key == key) {
            hashTable[index]->key = -1; // 标记该位置为已删除
            return;
        }
        index = (index + 1) % TABLE_SIZE; // 移动到下一个位置
        if (index == originalIndex) {
            return; // 未找到
        }
    }
}

int main() {
    // 初始化哈希表为空
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }

    // 插入键值对
    insert(1, 10);
    insert(11, 20);
    insert(21, 30);

    // 查找并打印值
    printf("Value for key 1: %d\n", search(1));
    printf("Value for key 11: %d\n", search(11));
    printf("Value for key 21: %d\n", search(21));

    // 删除键值对
    delete(11);
    printf("Value for key 11 after deletion: %d\n", search(11));

    return 0;
}

代码解释：

哈希函数：使用取模运算key % TABLE_SIZE来计算哈希值。
插入函数：如果发生冲突，使用线性探测法，即逐个检查下一个位置，直到找到空位。
查找函数：通过线性探测找到目标键对应的值。
删除函数：将目标键标记为-1，表示该位置被删除。

这段代码演示了如何使用开放地址法来实现一个简单的哈希表，不使用链表来处理冲突。

哈希查找算法（线性探测）

简介​

哈希查找算法概述​

开放地址法（线性探测）​

线性探测步骤​

代码实现​

头文件和宏定义​

结构体定义​

哈希函数​

插入函数​

查找函数​

删除函数​

主函数​

详细注释​

哈希表项结构​

哈希表定义​

哈希函数​

插入函数​

查找函数​

删除函数​

主函数​

运行示例​

完整代码​

代码解释：​

简介

哈希查找算法概述

开放地址法（线性探测）

线性探测步骤

代码实现

头文件和宏定义

结构体定义

哈希函数

插入函数

查找函数

删除函数

主函数

详细注释

哈希表项结构

哈希表定义

哈希函数

插入函数

查找函数

删除函数

主函数

运行示例

完整代码

代码解释：