哈希表原理与实战应用 | 极客日志

C++算法

哈希表原理与实战应用

哈希表通过键值映射实现 O(1) 查找，常用于统计频次和去重。本文通过五道 C++ 经典算法题演示了 unordered_map、数组模拟哈希及排序等多种技巧。涵盖两数之和、变位词分组、邻近重复元素等场景，帮助读者掌握哈希表在实际编码中的灵活运用与性能权衡。

1739658202发布于 2026/3/23更新于 2026/4/251 浏览

哈希表原理与实战应用

哈希表（Hash Table）是数据结构中常用的一种，主要用于快速统计数据频次、查重以及实现 O(1) 级别的查找。在 C++ 标准库中，我们可以利用 unordered_map、unordered_set 或者直接用数组模拟哈希表来实现这些功能。

下面通过几道经典例题来演示具体用法，看看在实际编码中如何灵活运用。

1. 两数之和

这道题要求找到两个数的下标，使它们的和等于目标值。核心思路是利用哈希表记录已遍历数字的下标，边遍历边检查补数是否存在。

文章配图

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hash;
        for(int i=0; i<nums.size(); i++){
            int x = target - nums[i];
            if(hash.count(x)) return {hash[x], i};
            hash[nums[i]] = i;
        }
        return {-1,-1};
    }
};

这里要注意，先查后存。如果先存再查，可能会匹配到当前元素自身（虽然本题通常假设解唯一）。

2. 变位词判断

判断两个字符串是否互为变位词，本质是字符频次统计。由于只涉及小写字母，可以用定长数组代替哈希表优化空间。

文章配图

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        int n=s1.size(), m=s2.size();
        if(n!=m) return false;
        int hash[26]={0};
        for(int i=0; i<n; i++){
            hash[s1[i]-'a']++;
        }
        for(int i=0; i<n; i++){
            hash[s2[i]-'a']--;
            if(hash[s2[i]-'a']<0) return false;
        }
        return true;
    }
};

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
};

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        for(int i=0; i<nums.size(); i++){
            if(hash.count(nums[i])){
                if(i-hash[nums[i]]<=k) return true;
            }
            hash[nums[i]] = i;
        }
        return false;
    }
};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> hash;
        for(auto& e : strs){
            string ret=e;
            sort(ret.begin(),ret.end());
            hash[ret].push_back(e);
        }
        vector<vector<string>> a;
        for(auto& [x,y] : hash){
            a.push_back(y);
        }
        return a;
    }
};