穿越数据迷宫：C++哈希表的奇幻旅程

在这里插入图片描述

文章目录

前言
- 📔一、unordered系列关联式容器
- - 📕1.1 `unordered` 容器概述
  - 📕1.2 哈希表在 `unordered` 容器中的实现原理
  - 📕1.3 `unordered` 容器的特点
- 📔二、`unordered_set ` 和 `unordered_map` 的基本操作
- - 📕2.1 `unordered_set` 的基本用法
  - - 📖1. 创建和初始化
    - 📖2. 插入元素
    - 📖3. 查找元素
    - 📖4. 删除元素
    - 📖5. 大小和清空
  - 📕2.2 `unordered_map` 的基本用法
  - - 📖1. 创建和初始化
    - 📖2. 插入元素
    - 📖3. 查找元素
    - 📖4. 删除元素
    - 📖5. 大小和清空
- 📔三、哈希表
- - 📕3.1 哈希表的基本原理
  - 📕3.2 哈希函数
  - 📕3.3 解决冲突的几种办法
  - - 📖1. 开放地址法（Open Addressing）
    - - 📄a. 线性探测（Linear Probing）
      - 📄b. 二次探测（Quadratic Probing）
      - 📄c. 双重哈希（Double Hashing）
    - 📖2. 拉链法（Chaining）
- 📔四、哈希表的模拟实现
- - 📕4.1 开放地址法（线性探测）
  - - 📖1. `DefaultHashFunc` 哈希函数类
    - 📖2. `HashData` 类
    - 📖3. `HashTable` 类
    - 📖4. 私有成员
  - 🏷️总结
  - 📕4.2 拉链法（哈希桶）
  - - 📖1. `HashNode` 类
    - 📖2. `HashTable` 类
    - - 📄成员变量
      - 📄构造函数和析构函数
      - 📄插入操作 `Insert`
      - 📄查找操作 `Find`
      - 📄删除操作 `Erase`
      - 📄打印操作 `Print`
    - 🏷️总结
结语

前言

在C++的世界中，哈希表是一种高效、独特的数据结构，被广泛应用于需要快速查找、插入、删除的场景。通过哈希函数将数据映射到表中，它不仅提高了操作效率，还在解决冲突时展现了精巧的设计。哈希表在算法的应用中尤为重要，无论是缓存、字典处理还是集合操作，都离不开它的身影。本篇博客将带你一步步深入理解哈希表的实现原理及其应用，让你在编码之路上更上一层楼。

📔一、unordered系列关联式容器

在 C++ 标准库中，unordered 系列容器（如 unordered_map 和 unordered_set）是一类基于哈希表实现的关联式容器。与传统的 map 和 set 容器不同，unordered 容器通过哈希函数实现了无序存储，能够在均摊 $O (1)$ 时间复杂度内完成插入、查找和删除操作。这使得 unordered 系列容器在处理需要快速查找的场景中非常高效。

📕1.1 `unordered` 容器概述

unordered 容器包含以下几种类型，主要用于不同类型的键值对或集合操作：

unordered_set：一个不包含重复元素的集合，存储的是唯一的键。
unordered_multiset：与 unordered_set 相似，但允许包含重复元素。
unordered_map：一个键值对的容器，每个键只能出现一次，键是唯一的。
unordered_multimap：一个键值对的容器，允许键重复。

与传统的有序容器（如 map 和 set）不同，unordered 容器中的元素没有特定的顺序。因此，unordered_map 和 unordered_set 更加适用于不关心元素顺序、仅关注快速访问的场景。

📕1.2 哈希表在 `unordered` 容器中的实现原理

unordered 容器的核心数据结构是哈希表，它利用哈希函数将键映射到表中的位置。在哈希表中，unordered 容器采用了一种**桶（bucket）**的机制来存储数据：

哈希函数：将键值映射到特定的哈希值，这个哈希值会决定键值对存储的位置（即桶）。
桶：哈希表中的每个位置称为一个桶，键值对根据哈希值分布在不同的桶中。
冲突处理：当多个键映射到同一个桶时，使用链表（或其他方法）来解决冲突。这种冲突解决方法通常称为拉链法。

📕1.3 `unordered` 容器的特点

均摊时间复杂度：在理想的情况下，插入、查找和删除的平均时间复杂度为 $O (1)$ 。
无序性：unordered 容器不维护元素的顺序，元素顺序与插入顺序无关。
哈希函数与相等比较器：可以指定自定义的哈希函数和比较器，适用于自定义类型和不同的哈希策略。

📔二、`unordered_set` 和 `unordered_map` 的基本操作

📕2.1 `unordered_set` 的基本用法

unordered_set 是一个集合，用于存储唯一的元素，元素的顺序是无序的。主要用在需要快速查找元素的场景中。

📖1. 创建和初始化

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> uset = {1, 2, 3, 4, 5};  // 初始化

    // 遍历输出元素
    for (const int& num : uset) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

📖2. 插入元素

使用 insert 方法插入元素。如果元素已存在，insert 不会插入重复元素。

uset.insert(6);   // 插入元素6
uset.insert(3);   // 3已存在，不插入

📖3. 查找元素

使用 find 方法查找元素，若找到则返回元素的迭代器，否则返回 end()。

if (uset.find(3) != uset.end()) {
    std::cout << "3 存在于集合中" << std::endl;
}

📖4. 删除元素

使用 erase 方法删除指定元素，可以传入元素值或迭代器。

uset.erase(4);  // 删除元素4

📖5. 大小和清空

size() 获取集合的大小。
clear() 清空集合中的所有元素。

std::cout << "集合大小: " << uset.size() << std::endl;
uset.clear();

📕2.2 `unordered_map` 的基本用法

unordered_map 是一种键值对关联容器，使用哈希表实现。每个键是唯一的，可以通过键快速访问对应的值。

📖1. 创建和初始化

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

int main() {
    std::unordered_map<std::string, int> umap = {{"apple", 3}, {"banana", 5}, {"orange", 2}};  // 初始化

    // 遍历键值对
    for (const auto& kv : umap) {
        std::cout << kv.first << " -> " << kv.second << std::endl;
    }
    return 0;
}

📖2. 插入元素

使用 insert 或 operator[] 插入键值对。operator[] 如果键不存在，会插入新键并初始化值为默认值。

umap["grape"] = 10;  // 插入或更新键为 "grape" 的值
umap.insert({"melon", 8});  // 插入键值对 {"melon", 8}

📖3. 查找元素

使用 find 方法查找元素，若找到则返回指向键值对的迭代器，否则返回 end()。

auto it = umap.find("banana");
if (it != umap.end()) {
    std::cout << "香蕉数量: " << it->second << std::endl;
}

📖4. 删除元素

使用 erase 方法删除指定键的元素。

umap.erase("orange");  // 删除键 "orange"

📖5. 大小和清空

size() 获取 unordered_map 的键值对数量。
clear() 清空所有元素。

std::cout << "键值对数量: " << umap.size() << std::endl;
umap.clear();

📔三、哈希表

哈希表是一种基于哈希函数的数据结构，用于快速存储和查找数据。它的核心思想是将键（Key）通过哈希函数转换为数组索引，从而实现快速的数据访问。哈希表被广泛用于字典、缓存、集合等需要高效查找的场景，是以上所介绍容器的底层结构。

📕3.1 哈希表的基本原理

哈希表包含以下几个核心概念：

哈希函数：将任意类型的键映射到数组中的一个索引位置。
桶（Bucket）：哈希表的每个索引位置称为一个桶，存储一个或多个元素。
冲突（Collision）：当不同的键被映射到相同的索引时发生冲突。
负载因子（Load Factor）：表示哈希表的填充程度，用公式 负载因子 = 元素个数 / 桶的数量 表示。负载因子过高会影响性能，通常哈希表会在负载因子达到一定值时扩容。

哈希表的操作，如插入、删除、查找，在理想情况下的时间复杂度为 $O (1)$ 。这是因为哈希表可以通过哈希函数将键快速映射到对应的存储位置。

📕3.2 哈希函数

哈希函数是哈希表性能的核心，其目的是将键均匀地分布在哈希表的桶中，减少冲突的发生。好的哈希函数具有以下特性：

均匀性：不同的键被分布在不同的桶中，避免过多的冲突。
快速计算：哈希函数的计算速度应尽可能快，以提高哈希表操作的整体效率。

在 C++ 中，标准库提供了许多内置类型的哈希函数，如 std::hash<int>、std::hash<std::string> 等。此外，用户也可以为自定义类型定义自己的哈希函数。

📕3.3 解决冲突的几种办法

📖1. 开放地址法（Open Addressing）

开放地址法是在哈希表中找一个新的空位来存储冲突元素。当发生冲突时，通过探测寻找下一个可用位置存放新元素。开放地址法常见的探测方式有：

📄a. 线性探测（Linear Probing）

在发生冲突时，线性探测通过固定步长（通常为 1）逐步查找下一个空位，直到找到可用位置。

公式：hash(key) + i，其中 i 是冲突次数。
优点：实现简单。
缺点：容易出现“聚集”现象，即相邻的桶很容易连续被填满，降低查找效率。

int linearProbing(int hashValue, int i, int tableSize) {
    return (hashValue + i) % tableSize;
}

📄b. 二次探测（Quadratic Probing）

二次探测通过平方增长的步长来查找下一个位置，避免线性探测的“聚集”问题。

公式：hash(key) + i^2。
优点：减少了聚集现象。
缺点：在高负载因子下，探测序列可能重复循环导致找不到空位。

int quadraticProbing(int hashValue, int i, int tableSize) {
    return (hashValue + i * i) % tableSize;
}

📄c. 双重哈希（Double Hashing）

双重哈希采用两个哈希函数，在发生冲突时，根据第二个哈希函数的值决定步长。

公式：hash1(key) + i * hash2(key)。
优点：能有效降低聚集现象，冲突处理更加均匀。
缺点：需要设计两个独立的哈希函数，且对负载因子要求较高。

int doubleHashing(int hashValue, int i, int tableSize, int hash2) {
    return (hashValue + i * hash2) % tableSize;
}

📖2. 拉链法（Chaining）

拉链法将每个哈希表位置（桶）设计为一个链表，所有被哈希到同一位置的元素都存储在该链表中。插入新元素时，将其添加到链表中，查找时则遍历该链表。

优点：
- 实现简单，链表支持动态扩展，不受哈希表容量影响。
- 插入、删除操作简单，尤其适合不定长数据结构（如链表、树等）。
缺点：
- 冲突严重时，链表可能变长，影响查找效率，最坏情况为 $O (n)$ 。
- 需要额外的链表存储空间。

📔四、哈希表的模拟实现

📕4.1 开放地址法（线性探测）

📖1. `DefaultHashFunc` 哈希函数类

DefaultHashFunc 是一个通用的哈希函数模板类，用于将键转换为哈希值。代码对整型和字符串类型分别进行了不同的哈希计算：

对于整型或其他非字符串类型，直接将键转换为 size_t 类型。
对于 string 类型，定义了一个专门的特化版本，使用一种常见的哈希算法，将字符串中的每个字符逐步加入到哈希值中，并乘以一个质数（131）来增加分布的均匀性。

template<class K>
class DefaultHashFunc {
public:
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};

template<>
class DefaultHashFunc<string> {
public:
    size_t operator()(const string& str) {
        size_t hash = 0;
        for (auto ch : str) {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};

📖2. `HashData` 类

HashData 类表示哈希表中的一个数据节点，包含一个键值对 _kv 和一个 STATE 状态 _state。STATE 枚举类定义了三个状态：

EXIST：表示该位置有数据。
EMPTY：表示该位置为空。
DELETE：表示该位置的数据已被删除。

这种状态管理方便在开放地址法中处理删除操作。

enum STATE {
	EXIST,
	EMPTY,
	DELETE
};

template<class K, class V>
class HashData {
public:
	pair<K, V> _kv;
	STATE _state = EMPTY;
};

📖3. `HashTable` 类

HashTable 是哈希表的主体类，支持以下操作：

构造函数：初始化哈希表容量，默认大小为 10。

public:
    HashTable() {
        _table.resize(10);
    }

插入操作 Insert：向哈希表插入一个键值对 kv。如果负载因子达到 0.7，进行扩容操作（即 resize）。
- 扩容操作：创建一个新的哈希表，将所有旧数据重新插入到新表中。这样可以重新计算哈希值，以确保数据均匀分布。
- 线性探测：若哈希值对应的桶已经存在数据，使用线性探测法查找下一个空闲位置，直到找到空位。

bool Insert(const pair<K, V>& kv) {
    // 扩容,扩容之后映射关系变了，需要重新映射
    if ((double)_n / _table.size() >= 0.7) {
        size_t  newSize = _table.size() * 2;
        // 遍历旧表，重新映射到新表
        HashTable<K, V, HashFunc> newHT;
        newHT._table.resize(newSize);

        for (size_t i = 0; i < _table.size(); ++i) {
            newHT.Insert(_table[i]._kv);
        }

        _table.swap(newHT._table);
    }

    // 线性探测
    // 起始位置，处理空间大小，是capacity还是size
    HashFunc hf;
    size_t hashi = hf(kv.first) % _table.size();
    while (_table[hashi]._state == EXIST) {
        ++hashi;
        hashi %= _table.size();
    }

    _table[hashi]._kv = kv;
    _table[hashi]._state = EXIST;
    ++_n;

    return true;
}

查找操作 Find：通过哈希函数定位键在哈希表中的位置，若发生冲突，则使用线性探测逐步查找直到找到匹配的键或遇到空位置。

HashData<const K, V>* Find(const K& key) {
	// 线性探测
	HashFunc hf;
	size_t hashi = hf(key) % _table.size();
	while (_table[hashi]._state != EMPTY) {
		if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) {
			return (HashData<const K, V>*) & _table[hashi];
		}

		++hashi;
		hashi %= _table.size();
	}

	return nullptr;
}

删除操作 Erase：先通过 Find 方法查找键的位置，如果找到则将该位置的状态标记为 DELETE，并减少元素计数 _n。

bool Erase(const K& key) {
	HashData<const K, V>* ret = Find(key);
	if (ret) {
		ret->_state = DELETE;
		--_n;
		return true;
	}

	return false;
}

📖4. 私有成员

_table：存储 HashData 的向量，作为哈希表的实际存储容器。
_n：存储有效数据的个数，用于计算负载因子并触发扩容操作。

private:
    vector<HashData<K, V>> _table;
    size_t _n = 0; // 存储有效数据的个数
};

🏷️总结

哈希函数：代码定义了默认的 DefaultHashFunc，支持不同类型的键。
开放地址法（线性探测）：处理冲突的方式，当发生哈希冲突时，逐步向后探测下一个空位。
扩容机制：当负载因子达到一定值时，动态扩展哈希表大小并重新分配数据，减少冲突。

📕4.2 拉链法（哈希桶）

这里我们继续沿用以上的DefaultHashFunc 哈希函数类。

📖1. `HashNode` 类

HashNode 类表示哈希表中的一个节点，包含一个键值对 _kv 和一个指向下一个节点的指针 _next。该类用于构成链表，以解决哈希冲突。

template<class K, class V>
class HashNode {
public:
    pair<K, V> _kv;
    HashNode<K, V>* _next;

    HashNode(const pair<K, V>& kv)
        : _kv(kv), _next(nullptr) {}
};

_kv：存储键值对。
_next：指向链表中的下一个节点。

📖2. `HashTable` 类

HashTable 使用拉链法来处理哈希冲突。每个桶存储一个链表的头节点，当多个键映射到相同的哈希位置时，通过链表存储多个节点。

📄成员变量

_table：std::vector 的每个位置存储一个链表头节点指针，表示一个桶。
_n：存储哈希表中当前有效数据的数量。

private:
    vector<Node*> _table; // 指针数组
    size_t _n = 0; // 存储了多少有效数据

📄构造函数和析构函数

构造函数：初始化哈希表大小为 10 个桶。
析构函数：遍历每个桶的链表并释放所有节点的内存。

HashTable() {
    _table.resize(10, nullptr);
}

~HashTable() {
    for (size_t i = 0; i < _table.size(); ++i) {
        Node* cur = _table[i];
        while (cur) {
            Node* next = cur->_next;
            delete cur;
            cur = next;
        }
        _table[i] = nullptr;
    }
}

📄插入操作 `Insert`

插入操作首先检查键是否已存在，若存在则返回 false，避免重复插入。若键不存在，执行以下步骤：

扩容：若负载因子达到 1，则将哈希表容量扩大一倍。
- 新建一个更大的表，并将旧表中的元素重新哈希并插入新表。
计算哈希值：根据哈希函数 HashFunc 计算哈希值。
插入到链表：将新节点插入到对应桶的链表头部（头插法），方便且高效。

bool Insert(const pair<K, V>& kv) {
    if (Find(kv.first)) {
        return false;
    }

    HashFunc hf;
    if (_n == _table.size()) {
        size_t newSize = _table.size() * 2;
        vector<Node*> newTable;
        newTable.resize(newSize, nullptr);

        for (size_t i = 0; i < _table.size(); ++i) {
            Node* cur = _table[i];
            while (cur) {
                Node* next = cur->_next;

                size_t hashi = hf(cur->_kv.first) % newSize;
                cur->_next = newTable[hashi];
                newTable[hashi] = cur;

                cur = next;
            }
            _table[i] = nullptr;
        }
        _table.swap(newTable);
    }

    size_t hashi = hf(kv.first) % _table.size();
    Node* newnode = new Node(kv);
    newnode->_next = _table[hashi];
    _table[hashi] = newnode;
    ++_n;

    return true;
}

📄查找操作 `Find`

查找操作使用哈希函数计算键的位置，遍历该位置的链表，查找对应键的节点。如果找到则返回节点指针，否则返回 nullptr。

Node* Find(const K& key) {
    HashFunc hf;
    size_t hashi = hf(key) % _table.size();
    Node* cur = _table[hashi];
    while (cur) {
        if (cur->_kv.first == key) {
            return cur;
        }
        cur = cur->_next;
    }
    return nullptr;
}

📄删除操作 `Erase`

删除操作与查找类似，通过哈希值定位到对应的链表，找到目标节点后将其从链表中移除。

如果要删除的节点是链表头节点，直接更新桶头指针。
否则，将该节点从链表中删除。

bool Erase(const K& key) {
    HashFunc hf;
    size_t hashi = hf(key) % _table.size();
    Node* prev = nullptr;
    Node* cur = _table[hashi];
    while (cur) {
        if (cur->_kv.first == key) {
            if (prev == nullptr) {
                _table[hashi] = cur->_next;
            } else {
                prev->_next = cur->_next;
            }
            --_n;
            delete cur;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}

📄打印操作 `Print`

打印哈希表中的内容，展示每个桶中的链表结构，用于观察哈希表的分布情况。

void Print() {
    for (size_t i = 0; i < _table.size(); ++i) {
        printf("[%d]->", i);
        Node* cur = _table[i];
        while (cur) {
            cout << cur->_kv.first << ":" << cur->_kv.second << "->";
            cur = cur->_next;
        }
        printf("NULL\n");
    }
    cout << endl;
}