网页设计兼职网站优化的文章

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

网页设计兼职,网站优化的文章,网站被攻击怎么让百度重新蜘蛛自动抓,和网站建设相关的行业前言#xff1a; 在C11及以后的标准中#xff0c;unordered容器是标准模板库#xff08;STL#xff09;的一部分#xff0c;提供了高效的数据结构选项#xff0c;适用于需要快速查找和插入操作的场景。 unordered通常与关联容器一起使用#xff0c;特别是unordered_map和…前言 在C11及以后的标准中unordered容器是标准模板库STL的一部分提供了高效的数据结构选项适用于需要快速查找和插入操作的场景。 unordered通常与关联容器一起使用特别是unordered_map和unordered_set。这些容器提供了基于哈希表的实现它们提供了与map和set相似的接口但在查找、插入和删除操作上通常具有更高的性能尤其是在处理大量数据时。 unordered_map是一个关联容器它存储键值对并根据键的哈希值进行排序以实现快速的查找操作。unordered_set则存储唯一的元素并使用哈希表来管理这些元素以便快速检查一个元素是否存在于集合中。 unordered_map的接口说明 注 unordered_map和unordered_set接口相似就只介绍一个接口。 unordered_map的接口说明 函数声明功能介绍unordered_map构造不同格式的unordered_map对象 unordered_map的容量 函数声明功能介绍bool empty()const检测unordered_map是否为空size_t size() const获取unordered_map的有效元素个数 unordered_map的迭代器 函数声明功能介绍begin返回unordered_map第一个元素的迭代器end返回unordered_map最后一个元素下一个位置的迭代器cbegin返回unordered_map第一个元素的const迭代器cend返回unordered_map最后一个元素下一个位置的const迭代器 unordered_map的元素访问 函数声明功能介绍operator[]返回与key对应的value没有一个默认值 unordered_map的查询 函数声明功能介绍iterator find(const K key)返回key在哈希桶中的位置size_t count(const K key)返回哈希桶中关键码为key的键值对的个数 unordered_map的修改操作 函数声明功能介绍insert向容器中插入键值对erase删除容器中的键值对void clear()清空容器中有效元素个数void swap(unordered_map)交换两个容器中的元素 unordered_map的桶操作 函数声明功能介绍size_t bucket_count()const返回哈希桶中桶的总个数size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数size_t bucket(const K key)返回元素key所在的桶号 哈希 哈希Hash是一种将任意大小的数据映射为固定大小值的函数通常用于数据的快速查找和存储。哈希表Hash Table是基于哈希函数的一种数据结构它通过计算关键字的哈希值来直接访问存储位置从而实现常数时间复杂度的查找性能。 在这里面的经过一系列的处理得到的结果就映射到对应的位置方便查找加快了查找的速度。但是也会引发一系列的问题哈希冲突。 哈希函数 向上面的通过一系列的计算的过程就是哈希函数有点类似于数学上的函数一个数经过对应关系会得到两者的映射的关系。 常见的哈希函数 直接定址法这种方法通过一个简单的线性函数计算哈希地址公式为 Hash(Key) A * Key B。这种方法简单且分布均匀但需要提前知道键值的分布情况。除留余数法这是一种常用的哈希函数通过取关键字除以一个质数后的余数作为哈希地址公式为 Hash(Key) Key % p其中 p 是一个不大于哈希表大小且最接近或等于哈希表大小的质数。乘法取余法这种方法通过将关键字乘以一个固定的数通常是一个接近2的数然后取结果的整数部分并进行取模运算来计算哈希地址。这种方法适用于处理字符串等非整数类型的键值。平方取中法这种方法适用于不清楚键值分布的情况通过计算关键字平方后的中间几位数作为哈希地址。折叠法折叠法将键值分割成几部分然后将这些部分叠加求和并取后几位作为散列地址适用于键值位数较多的情况。标准库中的std::hashC标准库提供了std::hash模板它为内置数据类型和一些标准库类型提供了默认的哈希函数实现。对于自定义类型可以通过特化std::hash模板来提供自定义的哈希函数。 哈希冲突 哈希冲突是指不同的输入值通过哈希函数计算得到了相同的哈希值的现象。 在哈希表等数据结构中哈希冲突是不可避免的因为哈希函数的输出范围通常远小于可能的输入值范围。 解决方法 开放定址法闭散列当发生冲突时会在哈希表中寻找下一个空位置来存放新元素。常见的开放定址法有线性探测和二次探测。线性探测是从冲突位置开始依次向后查找空位置二次探测则是通过更复杂的数学公式来确定下一个探测位置。再哈希法使用一个或多个备用哈希函数来处理冲突将冲突的元素重新映射到哈希表的其他位置。链地址法开散列在哈希表的每个存储位置不是存储元素本身而是存储一个指向元素的指针冲突的元素会被添加到一个链表中。这种方法可以很好地处理大量冲突但可能会导致链表过长影响性能。建立公共溢出区为所有可能的哈希冲突预留一个或多个区域冲突的元素被存储在这些区域中。 注降低哈希冲突是提高效率的一个很好的方法 简单哈希 在数组里面存储结构体定义哈希要有存在的状态定义了枚举 templateclass K,class V struct Hashdata {pairK, V _kv;state _state EMPTY; }; enum state {EXIST,EMPTY,DELETE };Hash结构 两个模板参数K V结构最后是存储hash的取值针对整形、浮点型、字符串。进行仿函数的重写 templateclass K,class V,class HashFunc DefaulthashfuncK class Hash { public:private:vectorHashdataK, V _table;size_t _n 0; };仿函数 在函数的内容的不确定的时候进行返回。针对string字符串的直接进行特模板化。针对26字母有不同的组合要进行字符串的哈希化处理目的是针对哈希冲突 本次采用 BKDR算法参考字符串哈希算法 templateclass K struct Defaulthashfunc {size_t operator()(const K key){return (size_t)key;} };template struct Defaulthashfuncstring {size_t operator()(const string str){size_t hash 0;for (auto e : str){hash * 131;hash e;}return hash;} };插入 将hash表直接扩容进行哈希计算进行哈希扩容 不建议直接将哈希表填写满不利于哈数的查找将哈希的负载因子已经存储的数据比总空间的大小设置到0.7到0.8之间即可。扩容 重新定义哈希表扩容后进行数据的重新插入进行交换进行哈希的冲突的解决 bool insert(const pairK, V kv){size_t hashi 0;HashFunc hf;hashi hf(kv.first) % _table.size();if ((_n * 10 / _table.size()) 7){size_t newsize _table.size() * 2;HashK, V, HashFunc newhash;newhash._table.resize(newsize);for (int i 0; i _table.size(); i){if (_table[i]._state EXIST){newhash.insert(_table[i]._kv);}}_table.swap(newhash._table);}//线性探测while (_table[hashi]._state EXIST){hashi;hashi % _table.size();}_table[hashi]._kv kv;_table[hashi]._state EXIST;_n;return true;}开放定址法闭散列 发生冲突会在哈希表的另外一个空位置寻找。 //线性探测 while (_table[hashi]._state EXIST) {hashi;hashi % _table.size(); }_table[hashi]._kv kv; _table[hashi]._state EXIST; _n;return true; }查找、删除 查找 返回结构体的指针利于后面的额删除 Hashdataconst K, V* find(const K key) {HashFunc hf;size_t hashi hf(key) % _table.size();while (_table[hashi]._state ! EMPTY){if (_table[hashi]._state EXIST _table[hashi]._kv.first key){return (Hashdataconst K,V) _table[hashi];}hashi;hashi % _table.size();}return nullptr; } 删除 在删除的时候直接进行状态的修改 bool erase(const K key) {Hashdataconst K, V ret find(key);if (ret){ret-_state DELETE;–_n;return true;}return false;}