STL 哈希 学习总结

概述

基础概念

哈希是通过特定的算法，将任意长度的数据映射为固定长度的数据串中。该映射的结果就被称为哈希值，也可以称为散列值。

例如在存储一个10000这个数据的时候，如果使用数组的话，则需要开辟对应大小空间内存，其他位置又不一定存储数据，所以这样就会造成数据的浪费。那么此时如果将这个数除以一个特定的数字，然后再将其存储到除数的结果下标中去，这样就避免了空间的浪费。

哈希函数

• 概念：哈希函数是将输入的数据转换为固定长度的哈希值的函数，这个转换过程也就是哈希或者散列。
• 常用的哈希函数
  • 直接定址法
    • 取关键字的某个现行函数为散列地址：Hash(key) = A*Key + B
    • 需要事先知道关键字的分布状况
  • 除留余数法
    • 假设散列表中允许的地址数有M个，取一个不大于M的数字，但是必须是最接近或者等于M的质数作为除数
    • Hash(Key) = Key % p (p<=M) ，将关键码转换为哈希地址

哈希值

• 哈希值则是通过哈希函数计算得到的固定长度的数据串，通常表示为一个16进制数
• 哈希表的长度取决于具体的哈希函数

哈希应用场景

• 数据存储于检索
  • 哈希表：利用哈希表将存储的数值，映射到哈希表中对应的位置，从而实现快速的数据存取
• 数据验证
  • 校验和和消息摘要：通过计算数据的哈希值来验证数据的完整性
• 负载均衡
  • 分布式系统中，通过哈希函数将请求均匀的分配到服务器中，从而实现负载均衡

基础概念总结*

•  哈希表是一种数据结构，通过哈希函数将键映射到一个数组中的索引位置，从而实现快速查找、插入和删除操作。每一个键值都存储在在一个桶中，桶的索引则是由哈希函数计算而来
• 哈希函数负责将一个任意大小的数据转换为固定大小的整数，哈希值通常是桶数组的索引
• 哈希表的主要应用字典、数据存储、数据验证、负载均衡

时间复杂度分析*

• 查插删的平均时间复杂度都是O（1）
• 最坏情况是O（n），最坏的情况即是所有的键都被映射到同一个桶中

哈希函数设计原则

• 均匀性：输入均匀的分布到所有桶中，从而减少冲突
• 减少碰撞：避免产生相同的哈希数值，减少碰撞的产生

unordered_map | unordered_set

unordered_map

• 存储数据的关联容器，用于存储键值对，通过键值来快速寻找对应数值，底层是哈希表
• 每个元素是一个键值对，键是唯一的，但是值是可以重复的

unordered_set

• 同样是关联容器，用于存储唯一元素并快速查找，底层仍然是哈希表
• 集合中的元素是唯一的，不可以有重复的元素，所以可以使用在元素去重或者快速查找上

两者插入与删除的时间复杂度都是O（1）

哈希表数组初始值

 Linux系统测试

#include <unordered_map>
#include <iostream>
 
int main() {
    std::unordered_map<int, int> umap;
    std::cout << "Initial bucket count (libstdc++): " << umap.bucket_count() << std::endl;
    return 0;
}

 VS系统测试

 

#define _CRT_SECURE_NO_WARNINGS 1
#include <unordered_map>
#include <iostream>
 
int main() {
    std::unordered_map<int, int> umap;
    std::cout << "Initial bucket count (MSVC): " << umap.bucket_count() << std::endl;
    return 0;
}

 哈希表初始值原则质数的原因

• 减少冲突：质数作为哈希表的初始桶数量有助于减少哈希冲突，因为质数能更加均匀的分散哈希值，减少哈希函数的重复。
• 性能：较小的初始值，可以让哈希表在初期阶段节省内存保持高性能
• 拓展性：哈希表增长过程中，通常采用倍增的方式，从而保证负载因子在合理的范围内
• 平衡负载因子：负载因子是哈希表元素数量与桶数量的比值。初始桶数量设置一个较小的数值，可以保持较低的负载因子

负载因子0.75的原因

• 查找效率
  • 降低冲突效率：保证25%的桶是空闲的，减少哈希冲突的概率
  • 查找高效：此时的查找时间接近于O（1），因为负载因子如果过高的话，冲突增加，导致查找时间增加。如果负载因子过低，虽然冲突减少，但是会浪费大量内存
• 平衡内存和性能
  • 保证查找效率的同时，让哈希表不浪费太多的内存空间
  • 避免频繁拓展 

 

哈希冲突

 哈希冲突指的是两个不同的数据，通过同一个哈希函数映射后，产生了相同的哈希值，从而在存储位置上产生了冲突。

解决方法

开放地址法

线性探测：顺序检查下一个位置，直到找一个空闲的位置。（-1表示该位置没有存储数据）

二次探测：采用二次方步长避免线性探测中的集聚性问题。 

 双重散列：使用第二个哈希函数计算步长，从而避免数据冲突

 

链地址法

每个哈希表的槽中，都存储一个链表指针，所有哈希到同一位置的元素，全部都插入该链表中。 

二次哈希

当哈希表达到一定的负载因子时，创建一个更大的哈希表，并使用新的哈希函数重新计算所有元素的数值，然后存储到新的哈希表中。 

细节问题

动态拓展和缩减

• 拓展：哈希表负载因子超过设置阈值时，需要拓展哈希表，创建一个更大的桶数组，并重新计算所有元素的哈希值分配到新的桶中
• 缩减：低于阈值的时候，调整哈希表大小，从而保证高效的查找性能

性能优化：选择初始桶的数量以及合理的负载因子，从而减少冲突和内存浪费

void rehash() {
    std::vector<std::list<PairType>> new_buckets(buckets.size() * 2);
    for (const auto& bucket : buckets) {
        for (const auto& pair : bucket) {
            size_t new_index = std::hash<KeyType>()(pair.first) % new_buckets.size();
            new_buckets[new_index].push_back(pair);
        }
    }
    buckets.swap(new_buckets);
}

哈希表的实际应用场景

数据库：哈希表用于实现索引，从而加速数据的索引

缓冲系统中：快速查找缓存数据

编译器：哈希表用于符号表管理、快速查找变量以及函数信息 

 实现简单哈希表（插入删除与查找）

#include <iostream>
#include <vector>
#include <list>
 
template <typename KeyType, typename ValueType>
class SimpleHashTable {
public:
    using PairType = std::pair<KeyType, ValueType>;
 
    SimpleHashTable(size_t bucket_count) : buckets(bucket_count) {}
 
    void insert(const KeyType& key, const ValueType& value) {
        size_t index = hashFunction(key);
        for (auto& pair : buckets[index]) {
            if (pair.first == key) {
                pair.second = value;  // 更新现有值
                return;
            }
        }
        buckets[index].emplace_back(key, value);  // 插入新值
    }
 
    bool remove(const KeyType& key) {
        size_t index = hashFunction(key);
        for (auto it = buckets[index].begin(); it != buckets[index].end(); ++it) {
            if (it->first == key) {
                buckets[index].erase(it);
                return true;
            }
        }
        return false;
    }
 
    bool find(const KeyType& key, ValueType& value) const {
        size_t index = hashFunction(key);
        for (const auto& pair : buckets[index]) {
            if (pair.first == key) {
                value = pair.second;
                return true;
            }
        }
        return false;
    }
 
private:
    size_t hashFunction(const KeyType& key) const {
        return std::hash<KeyType>()(key) % buckets.size();
    }
 
    std::vector<std::list<PairType>> buckets;
};
 
int main() {
    SimpleHashTable<int, std::string> table(10);
    table.insert(1, "one");
    table.insert(2, "two");
    table.insert(11, "eleven");
 
    std::string value;
    if (table.find(2, value)) {
        std::cout << "Found: " << value << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
 
    table.remove(2);
    if (table.find(2, value)) {
        std::cout << "Found: " << value << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
 
    return 0;
}