C++哈希表之线性探测法怎么实现

哈希表（Hash Table）是一种高效的数据结构，用于存储键值对。它通过哈希函数将键映射到数组的索引位置，从而实现快速的查找、插入和删除操作。然而，哈希表可能会遇到哈希冲突的问题，即不同的键映射到同一个索引位置。为了解决这个问题，常用的方法之一是线性探测法（Linear Probing）。

本文将介绍如何在C++中实现基于线性探测法的哈希表，并详细解释其工作原理和实现步骤。

1. 哈希表与线性探测法简介

1.1 哈希表

哈希表的核心思想是通过哈希函数将键映射到数组的索引位置。理想情况下，哈希函数应该将键均匀地分布到数组中，以减少冲突的发生。

1.2 线性探测法

线性探测法是一种解决哈希冲突的开放寻址法。当发生冲突时（即目标位置已被占用），线性探测法会顺序检查下一个位置，直到找到一个空闲的位置为止。

例如： - 假设哈希函数为 hash(key) = key % size。 - 如果 hash(key) 的位置已被占用，则检查 (hash(key) + 1) % size，依此类推。

2. C++实现线性探测法哈希表

2.1 数据结构设计

我们需要设计一个哈希表类，包含以下成员： - 一个数组用于存储键值对。 - 一个标志数组用于标记每个位置是否被占用。 - 哈希表的大小（容量）。

#include <iostream>
#include <vector>

class HashTable {
private:
    int size; // 哈希表的大小
    std::vector<int> keys; // 存储键
    std::vector<int> values; // 存储值
    std::vector<bool> occupied; // 标记位置是否被占用

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

public:
    // 构造函数
    HashTable(int tableSize) : size(tableSize) {
        keys.resize(size, -1); // 初始化为-1表示空
        values.resize(size, -1);
        occupied.resize(size, false);
    }

    // 插入键值对
    void insert(int key, int value);

    // 查找键对应的值
    int search(int key);

    // 删除键值对
    void remove(int key);

    // 打印哈希表
    void print();
};

2.2 插入操作

插入操作的核心是找到合适的位置存储键值对。如果目标位置已被占用，则使用线性探测法查找下一个空闲位置。

void HashTable::insert(int key, int value) {
    int index = hashFunction(key);

    // 线性探测
    while (occupied[index]) {
        if (keys[index] == key) {
            // 如果键已存在，更新值
            values[index] = value;
            return;
        }
        index = (index + 1) % size; // 检查下一个位置
    }

    // 找到空闲位置，插入键值对
    keys[index] = key;
    values[index] = value;
    occupied[index] = true;
}

2.3 查找操作

查找操作通过哈希函数定位键的位置，如果目标位置被占用且键不匹配，则继续线性探测。

int HashTable::search(int key) {
    int index = hashFunction(key);

    // 线性探测
    while (occupied[index]) {
        if (keys[index] == key) {
            return values[index]; // 找到键，返回值
        }
        index = (index + 1) % size; // 检查下一个位置
    }

    return -1; // 未找到键
}

2.4 删除操作

删除操作需要将键值对标记为删除状态，同时保持哈希表的连续性。

void HashTable::remove(int key) {
    int index = hashFunction(key);

    // 线性探测
    while (occupied[index]) {
        if (keys[index] == key) {
            // 找到键，标记为删除
            keys[index] = -1;
            values[index] = -1;
            occupied[index] = false;
            return;
        }
        index = (index + 1) % size; // 检查下一个位置
    }
}

2.5 打印哈希表

为了方便调试，我们可以实现一个打印函数，显示哈希表的当前状态。

void HashTable::print() {
    for (int i = 0; i < size; i++) {
        if (occupied[i]) {
            std::cout << "Index " << i << ": Key = " << keys[i] << ", Value = " << values[i] << std::endl;
        } else {
            std::cout << "Index " << i << ": Empty" << std::endl;
        }
    }
}

3. 测试哈希表

以下是一个简单的测试示例：

int main() {
    HashTable ht(10);

    ht.insert(5, 100);
    ht.insert(15, 200);
    ht.insert(25, 300);

    ht.print();

    std::cout << "Search key 15: " << ht.search(15) << std::endl;

    ht.remove(15);
    ht.print();

    return 0;
}

输出结果：

Index 0: Empty
Index 1: Empty
Index 2: Empty
Index 3: Empty
Index 4: Empty
Index 5: Key = 5, Value = 100
Index 6: Key = 15, Value = 200
Index 7: Key = 25, Value = 300
Index 8: Empty
Index 9: Empty
Search key 15: 200
Index 0: Empty
Index 1: Empty
Index 2: Empty
Index 3: Empty
Index 4: Empty
Index 5: Key = 5, Value = 100
Index 6: Empty
Index 7: Key = 25, Value = 300
Index 8: Empty
Index 9: Empty

4. 总结

线性探测法是一种简单且高效的哈希冲突解决方法。通过顺序检查下一个位置，它可以快速找到空闲位置存储数据。然而，线性探测法可能会导致聚集问题，即连续的位置被占用，从而降低查找效率。在实际应用中，可以通过调整哈希函数或使用其他冲突解决方法（如链地址法）来优化性能。

本文提供了一个基于C++的线性探测法哈希表实现，适合初学者学习和理解哈希表的基本原理。希望对你有所帮助！