C++——哈希表_c++哈希表

哈希表（Hash table），也被称为散列表，是一种常用的数据结构，用于实现键-值对的存储和检索。它通过将键映射到数组中的索引位置来实现快速的数据查找。

在 C++ 中，可以使用标准库中的 unordered_map 类来实现哈希表。unordered_map 是基于哈希表的关联容器，提供了高效的插入、查找和删除操作。

下面是一个示例代码，演示如何使用 unordered_map 实现哈希表：

#include <iostream>
#include <unordered_map>
 
int main() {
    std::unordered_map<std::string, int> hashTable;
 
    // 插入键-值对
    hashTable["Alice"] = 25;
    hashTable["Bob"] = 30;
    hashTable["Charlie"] = 35;
 
    // 访问键-值对
    std::cout << "Alice's age: " << hashTable["Alice"] << std::endl;
    std::cout << "Bob's age: " << hashTable["Bob"] << std::endl;
    std::cout << "Charlie's age: " << hashTable["Charlie"] << std::endl;
 
    // 检查键是否存在
    if (hashTable.find("Dave") != hashTable.end()) {
        std::cout << "Dave's age: " << hashTable["Dave"] << std::endl;
    } else {
        std::cout << "Dave is not in the hash table." << std::endl;
    }
 
    // 删除键-值对
    hashTable.erase("Bob");
 
    // 遍历哈希表
    for (const auto& pair : hashTable) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
 
    return 0;
}

下面是哈希表在  C++  中的一个经典例子：求解两个数组的交集。

假设有两个数组  nums1  和  nums2，求出它们的交集并返回，其中返回的交集元素要去重。

使用哈希表可以方便地解决这个问题。首先将  nums1  的所有元素存入哈希表中，然后遍历  nums2，把在哈希表中出现的元素加入到交集中，同时在哈希表中将该元素删除，避免元素重复计算。

实现代码如下：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
 
std::vector<int> intersect(std::vector<int>& nums1, std::vector<int>& nums2) {
  std::vector<int> v;
  std::unordered_map<int, int> m;
  for (auto& n : nums1) {
    m[n]++;
  }
  for (auto& n : nums2) {
    if (m[n] > 0) {
      v.push_back(n);
      m[n]--;
    }
  }
  return v;
}
 
int main() {
  std::vector<int> nums1 = {1, 2, 2, 1};
  std::vector<int> nums2 = {2, 2};
  std::vector<int> result = intersect(nums1, nums2);
  for (auto& n : result) {
    std::cout << n << " ";
  }
  std::cout << std::endl;
  return 0;
}