哈希

在计算机科学中，我们经常需要在大量数据中快速查找特定的元素。传统的线性搜索方法需要遍历整个数据结构，时间复杂度为O(n)。即使使用二分查找这样的优化算法，也需要O(log n)的时间，并且要求数据预先排序。

哈希表（Hash Table），也称为哈希映射（Hash Map），是一种能够实现平均O(1)时间复杂度的查找、插入和删除操作的数据结构。它通过将键（Key）映射到数组索引来实现直接寻址，从而避免了线性搜索的开销。 这种高效的查找机制使得哈希表成为处理键值对映射问题的首选数据结构。

在C++标准库中，哈希表的实现对应着std::unordered_map（用于存储键值对）和std::unordered_set（用于存储唯一的键）。与基于红黑树的std::map相比，哈希表在不需要保持元素有序性的场景下，能够提供更优的性能表现。

哈希函数

哈希表的核心机制在于哈希函数（Hash Function），它将任意类型的键映射到一个固定范围的整数值，这个整数值作为数组的索引，用于直接定位存储位置。

其中$h$是哈希函数，$m$是哈希表的大小（桶的数量）。哈希函数将键空间映射到桶索引空间，使得我们能够通过计算直接获得存储位置，而不需要遍历整个数据结构。

一个设计良好的哈希函数需要满足以下三个关键性质：

• 确定性：对于相同的输入键，哈希函数必须始终产生相同的输出值。这是哈希表能够正确工作的基础，任何不确定性都会导致查找失败。
• 高效性：哈希函数的计算必须足够快速，通常要求时间复杂度为O(1)或O(k)，其中k是键的长度。复杂的哈希函数会抵消哈希表在查找方面的性能优势。
• 均匀性：哈希函数应该将键尽可能均匀地分布到各个桶中，避免出现大量键映射到少数几个桶的情况。不均匀的分布会导致某些桶中的冲突链过长，严重影响查找性能。

让我们来看一个简单的字符串哈希函数实现。这个函数通过累加每个字符的ASCII码值来计算哈希值。

|
// 一个不太好的哈希函数示例
unsigned int badHash(const std::string& key) {
    unsigned int hashValue = 0;
    for (char c : key) {
        hashValue += c; // 将每个字符的ASCII码值加起来
    }
    return hashValue;
}

这个函数虽然计算简单快速，但存在一个严重的缺陷：它忽略了字符在字符串中的位置信息。例如，字符串"cat"和"act"会产生相同的哈希值，因为它们包含相同的字符，只是顺序不同。这种哈希函数会导致大量冲突，严重影响哈希表的性能。

一个更好的解决方案是使用多项式滚动哈希（Polynomial Rolling Hash），它通过引入位置权重来区分不同顺序的字符：

|
// 多项式滚动哈希函数
unsigned int goodHash(const std::string& key) {
    unsigned int hashValue = 0;
    unsigned int prime = 31; // 使用质数作为乘数
    for (char c : key) {
        // 将当前哈希值乘以质数，再加上新字符的值
        // 这使得字符的位置信息被编码到哈希值中
        hashValue = hashValue * prime + c;
    }

这个哈希函数通过将每个字符的值与它在字符串中的位置权重（质数的幂次）相乘，使得不同顺序的字符组合产生不同的哈希值。选择质数作为乘数可以更好地保证哈希值的均匀分布，减少冲突的概率。

哈希冲突

由于哈希表的桶数量是有限的，而可能的键值是无限的（或者远大于桶的数量），根据鸽巢原理（Pigeonhole Principle），必然存在多个不同的键映射到同一个桶索引的情况。这种现象称为哈希冲突（Hash Collision）。

哈希冲突是哈希表设计中必须解决的核心问题。即使使用设计良好的哈希函数，冲突也是不可避免的。处理冲突的策略直接影响哈希表的性能表现，因此选择合适的冲突解决方法至关重要。

链地址法

链地址法（Separate Chaining） 是解决哈希冲突最直观、最常用的方法。其基本思想是：每个桶不再直接存储单个键值对，而是维护一个链表（或其他动态数据结构），所有映射到该桶的键值对都存储在这个链表中。

当发生冲突时，新的键值对会被添加到对应桶的链表末尾。查找操作首先通过哈希函数定位到相应的桶，然后在该桶的链表中进行线性搜索。只要哈希函数设计合理，每个桶中的链表长度会保持在一个较小的范围内，从而保证查找操作的平均时间复杂度接近O(1)。

链地址法的优势在于实现简单，且能够处理任意数量的冲突。只要哈希函数分布均匀，每个桶中的链表长度会保持在O(α)级别，其中α是负载因子（元素数量与桶数量的比值），从而保证良好的平均性能。 下面是一个使用链地址法实现的简单哈希表：

|
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <utility> // for std::pair
 
// 使用链地址法解决冲突的哈希表实现
template <typename K, typename V>
class HashTable {
private:
    // 底层存储：vector的每个元素是一个存储键值对的链表
    std::vector<std::list<std::pair<K, V>>> table;
    size_t

开放地址法

开放地址法（Open Addressing） 采用不同的冲突解决策略：每个桶只能存储一个键值对，当发生冲突时，按照预定的探查序列（Probe Sequence）在哈希表中寻找下一个可用的桶。

最简单的探查方法是线性探查（Linear Probing）：如果桶$h(k)$已被占用，则依次尝试桶$h(k)+1$、$h(k)+2$、...，直到找到一个空桶。探查序列可以表示为：

其中$h(k)$是初始哈希值，$i$是探查次数，$m$是哈希表大小。

开放地址法的优势在于所有数据都直接存储在数组中，没有额外的指针开销，对CPU缓存更友好。然而，线性探查存在主聚集（Primary Clustering） 问题：当多个键的哈希值相近时，它们会形成连续的占用区域，导致后续插入这些区域的键需要更长的探查路径，严重影响性能。为了缓解这个问题，可以使用二次探查（Quadratic Probing）或双重哈希（Double Hashing）等更复杂的探查方法。

再哈希

随着哈希表中元素数量的增加，无论是链地址法还是开放地址法，都会面临性能下降的问题。对于链地址法，冲突链会变得越来越长；对于开放地址法，负载因子（Load Factor）会逐渐增大，导致查找空桶变得困难。

再哈希（Rehashing） 是解决这一问题的机制：当负载因子超过某个阈值（通常为0.75）时，哈希表会进行扩容操作。再哈希的过程包括：

首先，分配一个更大的存储空间，新容量通常是原容量的两倍（或选择一个接近的质数，以保持哈希函数的有效性）。然后，遍历原哈希表中的所有键值对，使用新的容量重新计算每个键的哈希值，并将它们插入到新的哈希表中。最后，释放原哈希表的存储空间。

再哈希操作的时间复杂度为O(n)，其中n是哈希表中的元素数量。虽然单次再哈希的代价较高，但由于再哈希操作不是频繁发生的，通过摊还分析（Amortized Analysis） 可以证明，将再哈希的成本分摊到所有插入操作上，平均每次操作的时间复杂度仍然接近O(1)。这与std::vector的动态扩容机制类似，都是通过牺牲单次操作的性能来保证整体性能的稳定性。

C++中的哈希表：std::unordered_map

在实际开发中，我们通常不需要手动实现哈希表。C++标准库提供了std::unordered_map（用于存储键值对）和std::unordered_set（用于存储唯一的键），它们都是基于哈希表实现的关联容器。

这些容器通常采用链地址法处理冲突，并自动执行再哈希操作以维持良好的性能。当应用场景不需要保持元素的排序特性时，std::unordered_map通常比基于红黑树的std::map具有更好的性能表现，因为哈希表的平均时间复杂度为O(1)，而红黑树的操作复杂度为O(log n)。需要注意的是，std::unordered_map不保证元素的遍历顺序，如果需要有序性，应使用std::map。

|
#include <iostream>
#include <string>
#include <unordered_map>
 
void useUnorderedMap() {
    // 创建一个unordered_map，键是string，值是int
    std::unordered_map<std::string, int> word_counts;
 
    // 像普通数组一样插入或更新元素
    word_counts["hello"] = 1;
    word_counts["world"] = 2;
    word_counts["hello"]++; // "hello"现在的值是2
 
    // 查找元素

小练习

4. 哈希冲突处理练习

假设我们有一个大小为10的哈希表（桶编号0-9），哈希函数为 h(key) = key % 10。依次插入以下整数键：12, 42, 33, 5, 25, 35。

请分析：

• 如果使用链地址法，请画出最终哈希表的结构，并指出哪个桶中的冲突链最长
• 如果使用开放地址法（线性探查），请画出最终数组的状态，并计算插入键35时需要的探查次数

|
#include <iostream>
#include <vector>
#include <unordered_map>
#include <sstream>
using namespace std;
 
// 辅助函数：打印数组
string arrayToString(const vector<int>& arr)
{
    if (arr.empty()) return "[]";
    stringstream ss;
    ss << "[";
    for

5. 哈希函数设计原理练习

在多项式滚动哈希函数中，为什么我们通常选择质数（如31）作为乘数，而不是偶数（如32）？考虑字符集为英文字母的情况，分析使用偶数作为乘数会导致什么问题。

|
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <sstream>
using namespace std;
 
// 使用质数31的哈希函数
int hashWithPrime31(const string& s)
{
    int hash = 0;
    for (char c : s)
    {
        hash = hash 

6. 实现哈希表删除操作练习

完善下面的哈希表实现，添加Remove方法。该方法应该能够删除指定的键，如果键存在则删除并返回true，否则返回false。

要求：使用链地址法处理冲突，实现删除操作。

|
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
 
template<typename K, typename V>
class MyHashTable
{
private:
    struct KeyValuePair
    {
        K key;
        V value;
        
        KeyValuePair(const K& k

7. 查找第一个重复元素练习

给定一个整数数组，使用Dictionary或HashSet找到第一个出现两次的数字。

例如，在数组[2, 5, 1, 2, 3, 5, 1, 2, 4]中，第一个重复的数字是2。

要求：返回第一个重复的数字，如果不存在重复则返回null。

|
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
using namespace std;
 
// 辅助函数：打印数组
string arrayToString(const vector<int>& arr)
{
    if (arr.empty()) return "[]";
    stringstream ss;
    ss <<

说明：

• 链地址法：
  • 桶[2]：12, 42（冲突链长度2）
  • 桶[5]：5, 25, 35（冲突链长度3，最长）
  • 使用链表存储冲突的元素，实现简单
• 开放地址法（线性探查）：
  • 插入35时，h(35) = 5，但索引5已被占用
  • 探查索引6，被25占用
  • 探查索引7，为空，插入35
  • 探查次数：2次
• 两种方法的比较：
  • 链地址法：实现简单，不需要考虑负载因子
  • 开放地址法：空间利用率高，但需要处理删除标记

说明：

• 质数31的优势：
  • 质数与大多数数字互质，能更好地分散键值
  • 减少哈希冲突，提高哈希表性能
  • 在多项式滚动哈希中，质数能更好地混合字符的贡献
• 偶数32的问题：
  • 32 = 2^5，是2的幂次
  • 当哈希表大小为2的幂次时，高位信息会丢失
  • 例如：h(key) = key % 32 只使用低5位，高位被忽略
  • 这会导致更多冲突，特别是对于相似的键
• 实际应用：
  • Java的String.hashCode()使用31
  • Python的字符串哈希也使用质数
  • 选择质数是为了在哈希表大小变化时保持较好的分布

说明：

• Remove方法的实现步骤：
  1. 计算哈希索引：int index = GetHashIndex(key)
  2. 找到对应的链表：var bucket = table[index]
  3. 在链表中查找并删除元素：遍历链表，找到匹配的键后删除
  4. 返回结果：如果找到并删除返回true，否则返回false
• 时间复杂度：
  • 平均情况：O(1)
  • 最坏情况：O(n)，当所有元素都冲突到同一个桶时
• 关键点：
  • 使用链地址法处理冲突
  • 在链表中查找匹配的键
  • 使用RemoveAt方法删除元素

说明：

• 算法思路：
  • 使用HashSet记录已经见过的数字
  • 遍历数组，对于每个数字：
    • 如果已经在集合中，说明是第一个重复的，返回该数字
    • 否则，将数字添加到集合中
• 时间复杂度：O(n)，需要遍历数组一次
• 空间复杂度：O(n)，最坏情况下需要存储所有不同的数字
• HashSet vs Dictionary：
  • HashSet：只存储键，适合只需要判断存在性的场景
  • Dictionary：存储键值对，适合需要记录额外信息（如出现次数）的场景
• 关键点：
  • HashSet.Contains() 和 HashSet.Add() 的平均时间复杂度都是 O(1)
  • 这保证了整体算法的时间复杂度为 O(n)