深入理解哈希表：原理、实现与应用

创作时间:

作者:

@小白创作中心

深入理解哈希表：原理、实现与应用

引用

CSDN

https://blog.csdn.net/2302_77582029/article/details/146290961

引言

哈希表（Hash Table）是一种高效的数据结构，广泛应用于数据存储和查找场景。它通过哈希函数将键映射到值，支持快速的插入、删除和查找操作。本文将详细介绍哈希表的原理、实现方法、冲突解决策略以及实际应用场景，帮助读者深入理解这一重要数据结构。

1. 哈希表的定义与原理

1.1 定义

哈希表是一种通过哈希函数将键映射到值的数据结构。它由以下两部分组成：

哈希函数：将键转换为数组索引。
数组（桶）：存储键值对。

1.2 哈希函数

作用：将任意大小的数据映射到固定大小的值（通常是整数）。
理想特性：
均匀分布：哈希函数应尽可能均匀地将键分布到数组中，减少冲突。
高效计算：哈希函数的计算应尽可能快速。
常见哈希函数：
除法哈希：h(k) = k % m，其中m是数组大小。
乘法哈希：h(k) = floor(m * (k * A % 1))，其中A是一个常数。

1.3 冲突解决

由于哈希函数的输出范围有限，不同的键可能映射到相同的索引，这种现象称为冲突。常见的冲突解决方法包括：

链地址法：将冲突的键值对存储在链表中。
开放地址法：通过探测方法（如线性探测、二次探测）寻找空闲位置。

2. 哈希表的实现

以下是哈希表的C++实现代码，使用链地址法解决冲突。

2.1 哈希表结构定义

#include <iostream>
#include <list>
#include <vector>

class HashTable {
private:
    int size; // 哈希表的大小
    std::vector<std::list<std::pair<int, int>>> table; // 存储桶的数组

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

public:
    // 构造函数
    HashTable(int size) : size(size), table(size) {}

    // 插入键值对
    void insert(int key, int value) {
        int index = hashFunction(key);
        table[index].push_back({key, value});
    }

    // 查找键对应的值
    int search(int key) {
        int index = hashFunction(key);
        for (auto& pair : table[index]) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        return -1; // 未找到
    }

    // 删除键值对
    void remove(int key) {
        int index = hashFunction(key);
        table[index].remove_if([key](const std::pair<int, int>& pair) {
            return pair.first == key;
        });
    }
};

2.2 示例代码

int main() {
    HashTable ht(10);
    // 插入键值对
    ht.insert(1, 100);
    ht.insert(2, 200);
    ht.insert(11, 1100); // 冲突，键11和1映射到同一个索引

    // 查找键值对
    std::cout << "查找键 1: " << ht.search(1) << std::endl; // 输出: 100
    std::cout << "查找键 11: " << ht.search(11) << std::endl; // 输出: 1100

    // 删除键值对
    ht.remove(2);
    std::cout << "查找键 2: " << ht.search(2) << std::endl; // 输出: -1

    return 0;
}