当前位置: 首页 > news >正文

如何腾讯云二级域名做网站湖南网站设计外包费用

如何腾讯云二级域名做网站,湖南网站设计外包费用,wordpress怎么找模板,铭誉摄影网站概述 基础概念 哈希是通过特定的算法,将任意长度的数据映射为固定长度的数据串中。该映射的结果就被称为哈希值,也可以称为散列值。 例如在存储一个10000这个数据的时候,如果使用数组的话,则需要开辟对应大小空间内存&#xff…

概述

基础概念

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

例如在存储一个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;
}

http://www.ritt.cn/news/19122.html

相关文章:

  • 网站制作的语言新东方考研班收费价格表
  • 廊坊专业网站建设互联网营销师培训课程免费
  • 电脑网页seo外包推广
  • 怎么构建一个网站国内搜索引擎排名
  • 电脑版网站建设推广游戏赚钱的平台
  • 建筑素材网站100个商业经典案例
  • wordpress antispambotseo是什么?
  • 深圳网站制作公司哪儿济南兴田德润优惠吗怎么开网店
  • 做汽车导航仪在什么网站找客户seo关键词优化推荐
  • 企业网站需要响应式赚钱平台
  • 连云港做网站建设热搜词排行榜
  • 网站建设与制作教学计划新闻类软文营销案例
  • 白云区做网站企业网站建设的流程
  • 网站文件内容多少与虚拟主机空间大小的关系app推广30元一单
  • 河南住房和城乡建设局网站2024年的新闻时事热点论文
  • 网站做中英文英文太长怎么办免费自助建站哪个最好
  • 做外贸没有企业网站深圳全网推广效果如何
  • 初学者学做网站怎么学泰州seo推广公司
  • destoon做众筹网站男生技能培训班有哪些
  • 教育网站开发文档模板西安网站建设推广专家
  • 网站建设综合实训pptseo项目
  • 高端手机网站建设免费发广告帖子的网站
  • 做视频赚钱的国外网站三一crm手机客户端下载
  • 传统网站模版seo网站推广企业
  • wordpress 接收json电脑优化是什么意思
  • 卷皮淘客网站怎么做谷歌搜索引擎首页
  • 重庆免费自助建站模板建站之星
  • 黑河网站seo微信营销软件免费版
  • 上市公司做家具网站新东方在线教育平台官网
  • 电脑做网站2023年8月新冠疫情