C++ 实现哈希表深度讲解 - 摩柯技术社区

哈希表基础概念

什么是哈希表

哈希表（Hash Table），也叫散列表，是一种能提供快速插入、删除和查找操作的数据结构。其核心思想是通过一个哈希函数（Hash Function）将键（Key）映射到一个特定的位置（索引），这个位置通常被称为槽（Slot）或桶（Bucket），从而快速定位到与该键相关联的值（Value）。例如，在一个学生成绩管理系统中，我们可以将学生的学号作为键，通过哈希函数计算出存储该学生成绩值的位置，这样就能快速根据学号找到对应的成绩。

哈希函数的重要性

哈希函数是哈希表实现的关键。一个好的哈希函数应具备以下特点：

高效性：计算哈希值的速度要快，以减少查找、插入和删除操作的时间开销。例如，简单的取模运算key % table_size就是一种快速的哈希计算方式。
均匀性：应尽可能将不同的键均匀地映射到哈希表的各个槽位上，减少哈希冲突的发生。比如，对于一组整数键，如果哈希函数总是将大部分键映射到哈希表的前半部分，就会导致前半部分槽位拥挤，而后半部分闲置，降低哈希表的性能。

哈希冲突及其解决方法

什么是哈希冲突：由于哈希函数的映射空间（哈希表的大小）通常远小于键的取值范围，所以会出现不同的键通过哈希函数计算得到相同的哈希值的情况，这就是哈希冲突。例如，有两个学生学号1001和2001，经过哈希函数计算后，都映射到了哈希表的第5个槽位。
解决哈希冲突的方法：
- 开放地址法：当发生冲突时，在哈希表中寻找下一个空闲的槽位来存储数据。常见的开放地址法有线性探测、二次探测和双重哈希等。
  - 线性探测：如果键key的哈希值对应的槽位已被占用，就依次检查下一个槽位（(hash(key)+1) % table_size），直到找到一个空闲槽位。例如，哈希表大小为10，键key1计算出的哈希值为3，但槽位3已被占用，就检查槽位4，若4也被占用，就检查5，以此类推。
  - 二次探测：探测的步长不再是固定的1，而是随着探测次数的增加以平方的形式增长。即第i次探测的位置为(hash(key)+i*i) % table_size。这样可以避免线性探测中可能出现的“聚集”问题，提高查找效率。
  - 双重哈希：使用两个哈希函数，当第一个哈希函数产生冲突时，用第二个哈希函数计算出一个步长，然后按照这个步长寻找空闲槽位。例如，step = hash2(key)，每次探测的位置为(hash1(key)+j * step) % table_size，其中j为探测次数。
- 链地址法（拉链法）：在每个槽位上维护一个链表，当发生冲突时，将冲突的元素插入到对应槽位的链表中。例如，哈希表的某个槽位对应的链表中可能存储了多个因哈希冲突而映射到该槽位的键值对。

C++ 实现哈希表

基于链地址法的哈希表实现

定义哈希表节点类：

template <typename Key, typename Value>
class HashNode {
public:
    Key key;
    Value value;
    HashNode* next;
    HashNode(const Key& k, const Value& v) : key(k), value(v), next(nullptr) {}
};

这里定义了一个模板类HashNode，用于表示哈希表中的节点。每个节点包含键key、值value以及指向下一个节点的指针next。

定义哈希表类：

template <typename Key, typename Value>
class HashTable {
private:
    HashNode<Key, Value>** table;
    int capacity;
    int size;
    unsigned long (*hashFunction)(const Key&);
public:
    HashTable(int cap = 10, unsigned long (*func)(const Key&) = nullptr);
    ~HashTable();
    void insert(const Key& key, const Value& value);
    Value* search(const Key& key);
    void remove(const Key& key);
};

HashTable类包含私有成员：一个指向哈希表节点指针数组的指针table，哈希表的容量capacity，当前存储元素的数量size，以及一个指向哈希函数的指针hashFunction。公有成员包括构造函数、析构函数、插入函数insert、查找函数search和删除函数remove。

构造函数实现：

template <typename Key, typename Value>
HashTable<Key, Value>::HashTable(int cap, unsigned long (*func)(const Key&))
    : capacity(cap), size(0), hashFunction(func) {
    if (hashFunction == nullptr) {
        hashFunction = [](const Key& key) {
            std::hash<Key> hasher;
            return hasher(key);
        };
    }
    table = new HashNode<Key, Value>*[capacity];
    for (int i = 0; i < capacity; ++i) {
        table[i] = nullptr;
    }
}

构造函数初始化哈希表的容量、大小和哈希函数。如果用户没有提供哈希函数，就使用标准库中的std::hash作为默认哈希函数。然后分配内存给哈希表节点指针数组，并将每个指针初始化为nullptr。

析构函数实现：

template <typename Key, typename Value>
HashTable<Key, Value>::~HashTable() {
    for (int i = 0; i < capacity; ++i) {
        HashNode<Key, Value>* node = table[i];
        while (node != nullptr) {
            HashNode<Key, Value>* temp = node;
            node = node->next;
            delete temp;
        }
        table[i] = nullptr;
    }
    delete[] table;
}

析构函数遍历哈希表的每个槽位，释放链表中的每个节点，然后释放哈希表节点指针数组。

插入函数实现：

template <typename Key, typename Value>
void HashTable<Key, Value>::insert(const Key& key, const Value& value) {
    unsigned long hashValue = hashFunction(key) % capacity;
    HashNode<Key, Value>* node = table[hashValue];
    if (node == nullptr) {
        table[hashValue] = new HashNode<Key, Value>(key, value);
        ++size;
        return;
    }
    while (node != nullptr) {
        if (node->key == key) {
            node->value = value;
            return;
        }
        if (node->next == nullptr) {
            break;
        }
        node = node->next;
    }
    node->next = new HashNode<Key, Value>(key, value);
    ++size;
}

插入函数首先计算键的哈希值，然后找到对应的槽位。如果槽位为空，就直接插入新节点。如果槽位已有节点，就遍历链表，若找到相同键的节点，则更新其值；否则在链表末尾插入新节点。

查找函数实现：

template <typename Key, typename Value>
Value* HashTable<Key, Value>::search(const Key& key) {
    unsigned long hashValue = hashFunction(key) % capacity;
    HashNode<Key, Value>* node = table[hashValue];
    while (node != nullptr) {
        if (node->key == key) {
            return &(node->value);
        }
        node = node->next;
    }
    return nullptr;
}

查找函数计算键的哈希值并找到对应的槽位，然后遍历链表，若找到相同键的节点，则返回其值的指针；否则返回nullptr。

删除函数实现：

template <typename Key, typename Value>
void HashTable<Key, Value>::remove(const Key& key) {
    unsigned long hashValue = hashFunction(key) % capacity;
    HashNode<Key, Value>* prev = nullptr;
    HashNode<Key, Value>* node = table[hashValue];
    while (node != nullptr && node->key != key) {
        prev = node;
        node = node->next;
    }
    if (node == nullptr) {
        return;
    }
    if (prev == nullptr) {
        table[hashValue] = node->next;
    } else {
        prev->next = node->next;
    }
    delete node;
    --size;
}

删除函数计算键的哈希值并找到对应的槽位，然后遍历链表，找到要删除的节点。如果该节点是链表头节点，就更新哈希表对应槽位的指针；否则调整前一个节点的指针，使其跳过要删除的节点，最后释放节点内存并更新哈希表大小。

基于开放地址法（线性探测）的哈希表实现

定义哈希表类：

template <typename Key, typename Value>
class OpenAddressHashTable {
private:
    std::pair<Key, Value>* table;
    int capacity;
    int size;
    unsigned long (*hashFunction)(const Key&);
    const static double loadFactor = 0.75;
public:
    OpenAddressHashTable(int cap = 10, unsigned long (*func)(const Key&) = nullptr);
    ~OpenAddressHashTable();
    void insert(const Key& key, const Value& value);
    Value* search(const Key& key);
    void remove(const Key& key);
    void rehash();
};

OpenAddressHashTable类包含私有成员：一个std::pair数组table用于存储键值对，哈希表的容量capacity，当前存储元素的数量size，指向哈希函数的指针hashFunction以及负载因子loadFactor。公有成员包括构造函数、析构函数、插入函数insert、查找函数search、删除函数remove和重新哈希函数rehash。

构造函数实现：

template <typename Key, typename Value>
OpenAddressHashTable<Key, Value>::OpenAddressHashTable(int cap, unsigned long (*func)(const Key&))
    : capacity(cap), size(0), hashFunction(func) {
    if (hashFunction == nullptr) {
        hashFunction = [](const Key& key) {
            std::hash<Key> hasher;
            return hasher(key);
        };
    }
    table = new std::pair<Key, Value>[capacity];
    for (int i = 0; i < capacity; ++i) {
        table[i].first = Key();
        table[i].second = Value();
    }
}

构造函数初始化哈希表的容量、大小和哈希函数，分配内存给table数组，并将每个元素初始化为默认值。

析构函数实现：

template <typename Key, typename Value>
OpenAddressHashTable<Key, Value>::~OpenAddressHashTable() {
    delete[] table;
}

析构函数释放table数组的内存。

插入函数实现：

template <typename Key, typename Value>
void OpenAddressHashTable<Key, Value>::insert(const Key& key, const Value& value) {
    if (static_cast<double>(size) / capacity >= loadFactor) {
        rehash();
    }
    unsigned long hashValue = hashFunction(key) % capacity;
    while (table[hashValue].first != Key()) {
        if (table[hashValue].first == key) {
            table[hashValue].second = value;
            return;
        }
        hashValue = (hashValue + 1) % capacity;
    }
    table[hashValue].first = key;
    table[hashValue].second = value;
    ++size;
}

插入函数首先检查负载因子，如果超过负载因子，就调用rehash函数进行重新哈希。然后计算键的哈希值，通过线性探测找到一个空闲槽位或相同键的槽位，进行插入或更新操作。

查找函数实现：

template <typename Key, typename Value>
Value* OpenAddressHashTable<Key, Value>::search(const Key& key) {
    unsigned long hashValue = hashFunction(key) % capacity;
    while (table[hashValue].first != Key()) {
        if (table[hashValue].first == key) {
            return &(table[hashValue].second);
        }
        hashValue = (hashValue + 1) % capacity;
    }
    return nullptr;
}

查找函数计算键的哈希值，通过线性探测查找键，若找到则返回对应值的指针，否则返回nullptr。

删除函数实现：

template <typename Key, typename Value>
void OpenAddressHashTable<Key, Value>::remove(const Key& key) {
    unsigned long hashValue = hashFunction(key) % capacity;
    while (table[hashValue].first != Key()) {
        if (table[hashValue].first == key) {
            table[hashValue].first = Key();
            table[hashValue].second = Value();
            --size;
            return;
        }
        hashValue = (hashValue + 1) % capacity;
    }
}

删除函数计算键的哈希值，通过线性探测找到要删除的键，将其对应位置的值设为默认值，并更新哈希表大小。

重新哈希函数实现：

template <typename Key, typename Value>
void OpenAddressHashTable<Key, Value>::rehash() {
    capacity *= 2;
    std::pair<Key, Value>* oldTable = table;
    table = new std::pair<Key, Value>[capacity];
    for (int i = 0; i < capacity; ++i) {
        table[i].first = Key();
        table[i].second = Value();
    }
    size = 0;
    for (int i = 0; i < capacity / 2; ++i) {
        if (oldTable[i].first != Key()) {
            insert(oldTable[i].first, oldTable[i].second);
        }
    }
    delete[] oldTable;
}

重新哈希函数将哈希表的容量翻倍，创建一个新的table数组，将旧表中的元素重新插入到新表中，最后释放旧表的内存。

哈希表性能分析

时间复杂度

理想情况下：如果哈希函数是完美的，即所有键均匀分布在哈希表中，没有哈希冲突，那么插入、删除和查找操作的时间复杂度均为 (O(1))。因为可以直接通过哈希函数计算出的索引找到对应的元素。
实际情况 - 链地址法：在平均情况下，假设哈希表的大小为 (n)，存储的元素个数为 (m)，负载因子 (\alpha = m/n)。插入、删除和查找操作在平均情况下的时间复杂度为 (O(1 + \alpha))。当负载因子较小时，链表长度较短，操作时间接近 (O(1))；当负载因子较大时，链表长度增加，操作时间会接近 (O(\alpha))，最坏情况下为 (O(m))，即链表退化为单链表，所有元素都冲突到同一个槽位。
实际情况 - 开放地址法：以线性探测为例，平均情况下插入和查找操作的时间复杂度为 (O(1 / (1 - \alpha)))，删除操作由于需要标记删除位置，复杂度类似插入和查找。随着负载因子 (\alpha) 接近 (1)，探测的次数会急剧增加，性能会显著下降。

空间复杂度

哈希表的空间复杂度主要取决于存储元素所占用的空间以及哈希表本身的额外空间开销。对于链地址法，除了存储元素的空间，还需要为每个链表节点分配额外的指针空间；对于开放地址法，需要额外考虑哈希表扩容时的空间浪费。总体来说，空间复杂度为 (O(m + n))，其中 (m) 是存储元素的数量，(n) 是哈希表的大小。

C++ 标准库中的哈希表

unordered_map 和 unordered_set

C++ 标准库提供了 unordered_map 和 unordered_set 这两个基于哈希表的数据结构。

unordered_map：它是一个关联容器，存储键值对，允许通过键快速查找对应的值。例如：

#include <iostream>
#include <unordered_map>
int main() {
    std::unordered_map<std::string, int> scores;
    scores["Alice"] = 85;
    scores["Bob"] = 90;
    auto it = scores.find("Alice");
    if (it != scores.end()) {
        std::cout << "Alice's score: " << it->second << std::endl;
    }
    return 0;
}

unordered_map 使用哈希表来实现快速查找，其内部的哈希函数和解决冲突的方法由标准库实现，用户只需要使用其接口进行操作。 2. unordered_set：它是一个无序容器，存储唯一元素，类似于集合的概念。例如：

#include <iostream>
#include <unordered_set>
int main() {
    std::unordered_set<int> numbers;
    numbers.insert(10);
    numbers.insert(20);
    auto it = numbers.find(10);
    if (it != numbers.end()) {
        std::cout << "10 is in the set" << std::endl;
    }
    return 0;
}

unordered_set 同样基于哈希表，通过哈希函数快速定位元素，实现高效的插入、查找和删除操作。

自定义哈希函数

在使用 unordered_map 和 unordered_set 时，如果要存储自定义类型，通常需要提供自定义的哈希函数。例如，假设有一个自定义的 Point 类：

#include <iostream>
#include <unordered_map>
#include <utility>
struct Point {
    int x;
    int y;
    Point(int a, int b) : x(a), y(b) {}
};
namespace std {
    template <>
    struct hash<Point> {
        std::size_t operator()(const Point& p) const {
            auto h1 = std::hash<int>{}(p.x);
            auto h2 = std::hash<int>{}(p.y);
            return h1 ^ h2;
        }
    };
}
int main() {
    std::unordered_map<Point, int> pointMap;
    Point p1(1, 2);
    pointMap[p1] = 100;
    auto it = pointMap.find(p1);
    if (it != pointMap.end()) {
        std::cout << "Value for point (1, 2): " << it->second << std::endl;
    }
    return 0;
}

这里为 Point 类在 std 命名空间中特化了 hash 模板，定义了适合 Point 类型的哈希函数，使得 unordered_map 可以正确地存储和查找 Point 类型的键。

哈希表的应用场景

缓存系统

在缓存系统中，哈希表常用于存储缓存数据。例如，网页缓存系统可以将网页的 URL 作为键，通过哈希函数快速定位到缓存的网页内容。当用户请求某个 URL 时，先在哈希表中查找对应的缓存内容，如果找到则直接返回，提高访问速度，减少服务器负载。

数据库索引

数据库中的索引机制可以利用哈希表来加速数据的查找。例如，在关系型数据库中，对于某一列（如主键）建立哈希索引，当执行查询操作时，通过对查询条件中的值计算哈希值，快速定位到存储该数据的物理位置，提高查询效率。

编译器符号表

编译器在编译过程中使用符号表来存储变量、函数等符号的信息。哈希表可以作为符号表的底层实现，通过将符号名作为键，快速查找和插入符号的相关信息，如类型、作用域等，有助于提高编译效率和错误检查。

密码存储

在密码存储系统中，为了安全地存储用户密码，通常会对密码进行哈希处理。将用户输入的密码通过哈希函数计算出哈希值存储在数据库中，当用户登录时，对输入的密码再次计算哈希值并与数据库中的哈希值进行比较，从而验证密码的正确性。由于哈希函数的单向性，即使数据库被泄露，攻击者也难以通过哈希值还原出原始密码。