如何腾讯云二级域名做网站湖南网站设计外包费用
概述
基础概念
哈希是通过特定的算法，将任意长度的数据映射为固定长度的数据串中。该映射的结果就被称为哈希值，也可以称为散列值。
例如在存储一个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;
}