哈希表(Hash Table)是计算机中一种 高效的查找数据结构,它能够在 O(1) 平均时间复杂度 内进行插入、删除和查找操作。哈希表在许多算法和数据结构中都有应用,例如 LRU缓存、计数问题、映射关系存储 等。


1. 哈希表的基本概念

(1)哈希表的定义

哈希表(Hash Table)是一种 键值对(key-value)存储结构,它通过哈希函数将键(Key)映射到一个索引位置,并存储相应的值(Value)。

在 C++ 中,常用的哈希表实现:

  • unordered_map<Key, Value>(无序映射)
  • unordered_set<Key>(无序集合)

(2)哈希函数(Hash Function)

哈希函数的作用是将键转换成数组索引,从而实现 O(1) 时间复杂度 进行存取。
常见的哈希函数:

  • 直接取模:index = key % table_size
  • 乘法哈希法
  • 一致性哈希(应用于分布式系统)

示例(简单哈希函数取模):

int hashFunction(int key, int table_size) {
    return key % table_size;
}

2. C++ STL 中的哈希表

(1)unordered_map(哈希映射)

用于存储键值对,支持 O(1) 平均查找/插入/删除。

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<string, int> scores;
    
    // 插入元素
    scores["Alice"] = 90;
    scores["Bob"] = 85;

    // 查找元素
    if (scores.count("Alice")) {
        cout << "Alice's score: " << scores["Alice"] << endl;
    }

    // 遍历哈希表
    for (auto& pair : scores) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

常见操作:

方法作用
map[key] = value;插入键值对
map.count(key);判断 key 是否存在
map.erase(key);删除 key
map.find(key);查找 key,返回迭代器

(2)unordered_set(哈希集合)

  • 只存储唯一元素
  • 没有 key-value 结构,只有 key
  • 适用于 去重、快速查找
#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    unordered_set<int> numbers = {1, 2, 3, 4, 5};

    // 插入元素
    numbers.insert(10);

    // 查找元素
    if (numbers.count(3)) {
        cout << "3 存在" << endl;
    }

    // 遍历哈希集合
    for (int num : numbers) {
        cout << num << " ";
    }

    return 0;
}

常见操作:

方法作用
set.insert(value);插入元素
set.count(value);判断元素是否存在
set.erase(value);删除元素
set.find(value);查找元素,返回迭代器

3. 哈希冲突(Hash Collision)

哈希表有可能出现两个不同的键被映射到相同的索引,这称为 哈希冲突。

(1)解决方法

  • 拉链法(Chaining):每个哈希桶存储一个链表,冲突元素存入链表中
  • 开放地址法(Open Addressing):如果索引冲突,则寻找下一个空闲位置存储

4. 哈希表的时间复杂度

操作平均时间复杂度最坏时间复杂度(哈希冲突严重)
插入 insert()O(1)O(n)
删除 erase()O(1)O(n)
查找 find()O(1)O(n)

5. 哈希表的实际应用

(1)两数之和(Two Sum)

利用 unordered_map 进行 O(n) 优化:

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.count(complement)) {
            return {map[complement], i};
        }
        map[nums[i]] = i;
    }
    return {};
}

(2)找出数组中的唯一元素

用 unordered_set 进行去重:

vector<int> removeDuplicates(vector<int>& nums) {
    unordered_set<int> unique(nums.begin(), nums.end());
    return vector<int>(unique.begin(), unique.end());
}

(3)字符串频率统计

unordered_map<char, int> countFrequency(string s) {
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }
    return freq;
}

总结

知识点说明
哈希表的核心思想通过哈希函数将 key 映射到数组索引,支持 O(1) 查找
unordered_map存储 key-value 对,适用于计数、映射关系
unordered_set只存 key,用于去重和快速查找
哈希冲突解决方法拉链法、开放地址法
哈希表的应用两数之和、频率统计、去重等

更多推荐