哈希表

时间：2024-03-21 15:34:05

哈希表（hash table），又称散列表，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，向哈希表中输入一个键 key ，则可以在 ????(1) 时间内获取对应的值 value 。

除哈希表外，数组和链表也可以实现查询功能。

添加元素： 仅需将元素添加至数组（链表）的尾部即可，使用 ????(1) 时间。
查询元素： 由于数组（链表）是乱序的，因此需要遍历其中的所有元素，使用 ????(????) 时间。
删除元素： 需要先查询到元素，再从数组（链表）中删除，使用 ????(????) 时间。

在哈希表中进行增删查改的时间复杂度都是 ????(1)
在这里插入图片描述

哈希表常用操作

哈希表的常见操作包括：初始化、查询操作、添加键值对和删除键值对等。

/**
 * File: hash_map.cpp
 * Created Time: 2022-12-14
 * Author: msk397 (machangxinq@gmail.com)
 */

#include "../utils/common.hpp"

/* Driver Code */
int main() {
    /* 初始化哈希表 */
    unordered_map<int, string> map;

    /* 添加操作 */
    // 在哈希表中添加键值对 (key, value)
    map[12836] = "小哈";
    map[15937] = "小啰";
    map[16750] = "小算";
    map[13276] = "小法";
    map[10583] = "小鸭";
    cout << "\n添加完成后，哈希表为\nKey -> Value" << endl;
    printHashMap(map);

    /* 查询操作 */
    // 向哈希表中输入键 key ，得到值 value
    string name = map[15937];
    cout << "\n输入学号 15937 ，查询到姓名 " << name << endl;

    /* 删除操作 */
    // 在哈希表中删除键值对 (key, value)
    map.erase(10583);
    cout << "\n删除 10583 后，哈希表为\nKey -> Value" << endl;
    printHashMap(map);

    /* 遍历哈希表 */
    cout << "\n遍历键值对 Key->Value" << endl;
    for (auto kv : map) {
        cout << kv.first << " -> " << kv.second << endl;
    }
    cout << "\n使用迭代器遍历 Key->Value" << endl;
    for (auto iter = map.begin(); iter != map.end(); iter++) {
        cout << iter->first << "->" << iter->second << endl;
    }

    return 0;
}

哈希表有三种常用的遍历方式：遍历键值对、遍历键和遍历值。

/* 遍历哈希表 */
/* 遍历哈希表 */
cout << "\n遍历键值对 Key->Value" << endl;
for (auto kv : map) {
    cout << kv.first << " -> " << kv.second << endl;
}
cout << "\n使用迭代器遍历 Key->Value" << endl;
for (auto iter = map.begin(); iter != map.end(); iter++) {
    cout << iter->first << "->" << iter->second << endl;
}

哈希表简单实现

仅用一个数组来实现哈希表：在哈希表中，将数组中的每个空位称为桶（bucket），每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value 。

那么，如何基于 key 定位对应的桶呢？这是通过哈希函数（hash function）实现的。
哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有 key ，输出空间是所有桶（数组索引）。换句话说，输入一个 key ， 可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置。

输入一个 key ，哈希函数的计算过程分为以下两步：
1.通过某种哈希算法 hash() 计算得到哈希值；
2. 将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index 。

index = hash(key) % capacity

随后，就可以利用 index 在哈希表中访问对应的桶，从而获取 value 。

设数组长度 capacity = 100、哈希算法 hash(key) = key ，易得哈希函数为 key % 100，
在这里插入图片描述

以下代码实现了一个简单哈希表。其中，将 key 和 value 封装成一个类 Pair ，以表示键值对：

/**
 * File: array_hash_map.cpp
 * Created Time: 2022-12-14
 * Author: msk397 (machangxinq@gmail.com)
 */

#include "../utils/common.hpp"

/* 键值对 */
struct Pair {
  public:
    int key;
    string val;
    Pair(int key, string val) {
        this->key = key;
        this->val = val;
    }
};

/* 基于数组实现的哈希表 */
class ArrayHashMap {
  private:
    vector<Pair *> buckets;

  public:
    ArrayHashMap() {
        // 初始化数组，包含 100 个桶
        buckets = vector<Pair *>(100);
    }

    ~ArrayHashMap() {
        // 释放内存
        for (const auto &bucket : buckets) {
            delete bucket;
        }
        buckets.clear();
    }

    /* 哈希函数 */
    int hashFunc(int key) {
        int index = key % 100;
        return index;
    }

    /* 查询操作 */
    string get(int key) {
        int index = hashFunc(key);
        Pair *pair = buckets[index];
        if (pair == nullptr)
            return "";
        return pair->val;
    }

    /* 添加操作 */
    void put(int key, string val) {
        Pair *pair = new Pair(key, val);
        int index = hashFunc(key);
        buckets[index] = pair;
    }

    /* 删除操作 */
    void remove(int key) {
        int index = hashFunc(key);
        // 释放内存并置为 nullptr
        delete buckets[index];
        buckets[index] = nullptr;
    }

    /* 获取所有键值对 */
    vector<Pair *> pairSet() {
        vector<Pair *> pairSet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                pairSet.push_back(pair);
            }
        }
        return pairSet;
    }

    /* 获取所有键 */
    vector<int> keySet() {
        vector<int> keySet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                keySet.push_back(pair->key);
            }
        }
        return keySet;
    }

    /* 获取所有值 */
    vector<string> valueSet() {
        vector<string> valueSet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                valueSet.push_back(pair->val);
            }
        }
        return valueSet;
    }

    /* 打印哈希表 */
    void print() {
        for (Pair *kv : pairSet()) {
            cout << kv->key << " -> " << kv->val << endl;
        }
    }
};


/* Driver Code */
int main() {
    /* 初始化哈希表 */
    ArrayHashMap map = ArrayHashMap();

    /* 添加操作 */
    // 在哈希表中添加键值对 (key, value)
    map.put(12836, "小哈");
    map.put(15937, "小啰");
    map.put(16750, "小算");
    map.put(13276, "小法");
    map.put(10583, "小鸭");
    cout << "\n添加完成后，哈希表为\nKey -> Value" << endl;
    map.print();

    /* 查询操作 */
    // 向哈希表中输入键 key ，得到值 value
    string name = map.get(15937);
    cout << "\n输入学号 15937 ，查询到姓名 " << name << endl;

    /* 删除操作 */
    // 在哈希表中删除键值对 (key, value)
    map.remove(10583);
    cout << "\n删除 10583 后，哈希表为\nKey -> Value" << endl;
    map.print();

    /* 遍历哈希表 */
    cout << "\n遍历键值对 Key->Value" << endl;
    for (auto kv : map.pairSet()) {
        cout << kv->key << " -> " << kv->val << endl;
    }

    cout << "\n单独遍历键 Key" << endl;
    for (auto key : map.keySet()) {
        cout << key << endl;
    }

    cout << "\n单独遍历值 Value" << endl;
    for (auto val : map.valueSet()) {
        cout << val << endl;
    }

    return 0;
}

在这里插入图片描述

哈希冲突与扩容

从本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况

多个输入对应同一输出的情况称为哈希冲突 （hash collision）。
在这里插入图片描述
容易想到，哈希表容量 ???? 越大，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。因此，可以通过扩容哈希表来减少哈希冲突。

扩容前键值对 (136, A) 和 (236, D) 发生冲突，扩容后冲突消失：
在这里插入图片描述
类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时；
并且由于哈希表容量capacity 改变，需要通过哈希函数来重新计算所有键值对的存储位置，这进一步增加了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。

负载因子（load factor）是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。

相关文章