无序哈希集合

🧑‍💻 作者: 一可爱小白兔

📦 版本: 1.0.0

📄 字数(字): 0

⏳ 时长(min): 0

⏱️ 更新于: 2026-01-08

`std::unordered_set` 是 C++11 引入的无序哈希集合容器，它基于哈希表（hash table） 实现，用于高效地存储和查询不重复的元素。

基本特点

特性	说明
无序性	元素在容器中没有特定顺序（与 std::set 的有序不同）
唯一性	不允许重复元素（自动去重）
底层实现	哈希表（平均 O(1) 查找/插入/删除）
时间复杂度	平均：O(1)，最坏（哈希冲突严重）：O(n)
头文件	#include <unordered_set>

基本操作

函数	作用
insert(x)	插入元素 x
erase(x) / erase(it)	删除元素
find(x)	返回指向 x 的迭代器，未找到返回 end()
count(x)	返回 1（存在）或 0（不存在）
size()	返回元素个数
empty()	判断是否为空
clear()	清空所有元素
reserve(n)	预分配至少能容纳 n 个元素的桶（bucket），减少 rehash
load_factor()	当前负载因子（元素数 / 桶数）

1、创建无序哈希集合：

// 空集合
unordered_set<int> s1;

// 初始化列表（C++11）
unordered_set<string> s2 = { "apple", "banana", "cherry" };

// 从 vector 构造
vector<int> v = { 1, 2, 3, 2, 4 };
unordered_set<int> s3(v.begin(), v.end());          // 自动去重 → {1,2,3,4}

2、插入元素

unordered_set<int> s1;

s1.insert(5);

3、删除元素

unordered_set<int> s1 = {1, 2, 3, 4, 5};

s1.erase(5);
s1.erase(s1.begin());

4、查找元素

unordered_set<string> words = {"hello", "world"};

// 方法1：count() —— 存在返回1，否则0
if (words.count("hello")) {
    cout << "Found 'hello'\n";
}

// 方法2：find() —— 返回迭代器
auto it = words.find("world");
if (it != words.end()) {
    cout << "Found: " << *it << "\n";
}

应用

• 去重

• 快速查找

  • 两数之和

  • 判断存在重复元素

    bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int num : nums) {
        if (seen.count(num)) {  
            return true;
        }
        seen.insert(num);
      }
      return false;
    }

  时间复杂度：O(n) 空间复杂度：O(n)

  • 缺失的最小整数

    static int find_missing_min(vector<int> &nums) {
        // 用数组 nums 初始化 hashSet,并自动去重
        unordered_set<int> hashSet(nums.begin(), nums.end());
        // 初始化 missing 为 1
        int missing = 1;
        // 循环检查当前 missing 是否存在于集合中,如果存在就递增 missing,直到找到第一个不存在的正整数
        while (hashSet.count(missing)) {
            ++missing;
        }
        // 返回缺失的最小正整数
        return missing;
    }

  • 删除链表中绝对值重复的结点

   ListNode *deleteAbsDupNode(ListNode *head) {
        unordered_set<int> hashSet;
        // 定义p，q指针，初始时分别指向首结点和空
        ListNode *p = head->next, *q = nullptr;
        while (p) {
            // 如果当前结点的值的绝对值在哈希表中存在，则删除当前节点
            if (hashSet.count(abs(p->val)) && q != nullptr) {
                //(删除结点) 让p的前驱指针q指向当前结点p的下一个结点
                q->next = p->next;
            } else {
                hashSet.insert(abs(p->val));
                // 保存当前结点的指针作为下个结点的前驱指针
                q = p;
            }
            // 始终移动p指针
            p = p->next;
        }
        return head->next;
   }

• 统计唯一元素个数