探索哈希表：C++中的实现与操作详解【Map、Set、数据结构】

探索哈希表：C++中的实现与操作详解

---

介绍

哈希表（Hash Table）是一种常见的数据结构，它提供了一种高效的键值对存储方式，能够快速进行插入、删除和查找操作。在这篇博客中，我们将详细介绍哈希表的概念、在C++中的实现方式以及常见操作的示例。我们还会讨论 unordered_set，一种用于集合操作的哈希表，常用于需要去重的场景。

什么是哈希表？

哈希表是一种通过哈希函数将键映射到存储桶（Bucket）或槽（Slot）中的数据结构。其核心思想是使用哈希函数将键转换为数组的索引，从而能够在常数时间内（平均情况下）进行查找、插入和删除操作。

哈希表的基本概念

1. 哈希函数：将输入的键转换为数组的索引。
2. 存储桶：数组中的位置，每个存储桶可以存储一个或多个键值对。
3. 冲突处理：当两个不同的键被哈希到相同的索引时，需要解决冲突。常见的冲突处理方法有链地址法（Chaining）和开放地址法（Open Addressing）。

在C++中实现哈希表

在C++中，我们可以使用STL库中的unordered_map来实现哈希表。unordered_map是一个关联容器，提供了哈希表的所有基本操作。下面是一个简单的示例：

示例代码

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // 创建一个unordered_map
    std::unordered_map<std::string, int> hashTable;

    // 插入键值对
    hashTable["apple"] = 1;
    hashTable["banana"] = 2;
    hashTable["orange"] = 3;

    // 查找键值对
    std::string key = "banana";
    if (hashTable.find(key) != hashTable.end()) {
        std::cout << key << " found with value " << hashTable[key] << std::endl;
    } else {
        std::cout << key << " not found" << std::endl;
    }

    // 删除键值对
    hashTable.erase("orange");

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

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

详细实现与操作

1. 创建哈希表

   • 使用std::unordered_map可以很方便地创建一个哈希表。键和值的类型可以根据需要进行指定。

   std::unordered_map<std::string, int> hashTable;
   1

2. 插入键值对

   • 可以使用下标操作符或insert方法来插入键值对。

   hashTable["apple"] = 1;
   hashTable["banana"] = 2;
   hashTable.insert({"orange", 3});
   1
   2
   3

3. 查找键值对

   • 使用find方法可以查找键是否存在于哈希表中，返回一个迭代器。如果键存在，迭代器指向键值对；否则，迭代器指向end。

   std::string key = "banana";
   if (hashTable.find(key) != hashTable.end()) {
       std::cout << key << " found with value " << hashTable[key] << std::endl;
   } else {
       std::cout << key << " not found" << std::endl;
   }
   1
   2
   3
   4
   5
   6

4. 删除键值对

   • 使用erase方法可以删除指定键的键值对。

   hashTable.erase("orange");
   1

5. 遍历哈希表

   • 可以使用范围循环或迭代器遍历哈希表中的所有键值对。

   for (const auto& pair : hashTable) {
       std::cout << pair.first << ": " << pair.second << std::endl;
   }
   1
   2
   3

unordered_set的讲解与使用场景

unordered_set是什么？

unordered_set 是 C++ 标准模板库（STL）中的一种集合容器，它基于哈希表实现，用于存储不重复的元素。与 unordered_map 类似，unordered_set 提供了快速的插入、删除和查找操作。

unordered_set的典型使用场景

unordered_set 最常用于需要去重的场景。例如，我们有一个包含重复元素的数组，需要快速去重并保留唯一元素。在这种情况下，unordered_set 是一个理想的选择。

示例代码

#include <iostream>
#include <unordered_set>
#include <vector>

int main() {
    // 创建一个unordered_set
    std::unordered_set<int> hashSet;

    // 插入元素
    hashSet.insert(1);
    hashSet.insert(2);
    hashSet.insert(3);
    hashSet.insert(2); // 插入重复元素

    // 查找元素
    int key = 2;
    if (hashSet.find(key) != hashSet.end()) {
        std::cout << key << " found in the set" << std::endl;
    } else {
        std::cout << key << " not found in the set" << std::endl;
    }

    // 删除元素
    hashSet.erase(2);

    // 遍历哈希集合
    for (const auto& elem : hashSet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 使用unordered_set去重
    std::vector<int> nums = {1, 2, 3, 4, 5, 1, 2, 3};
    std::unordered_set<int> uniqueNums(nums.begin(), nums.end());

    // 输出去重后的结果
    for (const auto& elem : uniqueNums) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

详细实现与操作

1. 创建哈希集合

   • 使用 std::unordered_set 可以方便地创建一个集合，用于存储不重复的元素。

   std::unordered_set<int> hashSet;
   1

2. 插入元素

   • 可以使用 insert 方法来插入元素。重复的元素不会被插入到集合中。

   hashSet.insert(1);
   hashSet.insert(2);
   hashSet.insert(3);
   hashSet.insert(2); // 插入重复元素
   1
   2
   3
   4

3. 查找元素

   • 使用 find 方法可以查找元素是否存在于集合中，返回一个迭代器。如果元素存在，迭代器指向元素；否则，迭代器指向 end。

   int key = 2;
   if (hashSet.find(key) != hashSet.end()) {
       std::cout << key << " found in the set" << std::endl;
   } else {
       std::cout << key << " not found in the set" << std::endl;
   }
   1
   2
   3
   4
   5
   6

4. 删除元素

   • 使用 erase 方法可以删除指定的元素。

   hashSet.erase(2);
   1

5. 遍历哈希集合

   • 可以使用范围循环或迭代器遍历集合中的所有元素。

   for (const auto& elem : hashSet) {
       std::cout << elem << " ";
   }
   std::cout << std::endl;
   1
   2
   3
   4

6. 使用 unordered_set 去重

   • 可以将一个包含重复元素的数组转换为 unordered_set，从而实现去重。

   std::vector<int> nums = {1, 2, 3, 4, 5, 1, 2, 3};
   std::unordered_set<int> uniqueNums(nums.begin(), nums.end());
   
   // 输出去重后的结果
   for (const auto& elem : uniqueNums) {
       std::cout << elem << " ";
   }
   std::cout << std::endl;
   1
   2
   3
   4
   5
   6
   7
   8

总结

哈希表是一种高效的数据结构，广泛应用于需要快速查找、插入和删除操作的场景中。在C++中，std::unordered_map 和 std::unordered_set 提供了便捷的哈希表实现。通过本文的介绍和示例代码，我们了解了哈希表的基本概念及其在C++中的实现和常见操作。希望这些内容能帮助你更好地理解和使用哈希表。