企业官网建设流程全解析

1.简介在Java中分为HashMap和TreeMapHashSet和TreeSetC是map和unordered_mapset和unordered_set一般哈希表的效率更优秀一些通过下面代码测性能确实如此查找1.暴力查找O(N)2.二分性能O(logN)要求数据有序O(NlogN)可随机访问且在头部和中间位置插入代价O(N)3.AVL红黑树unordered系列顾名思义遍历出来是无序的没有rbegin迭代器是单向迭代器哈希亦称散列存储的值与位置建立一个映射关系比如计数排序建立大小为(max-min)的数组每个num位置是num-min存储的是count出现次数问题是如果元素过于分散空间极度浪费这说的是哈希的直接定值法一般用于范围小比如确认字符串中每个字符出现的次数最多26个字母为了优化提出除留余数法N%mm是数组大小每个num的存储位置是num%m问题是可能出现哈希碰撞多个key映射同一个位置一般采用拉链法也称哈希桶来解决2.效率测试#includeiostream#includevector#includeunordered_map#includeunordered_set#includeset#includectimeusingnamespacestd;intmain(){constintN1000000;vectorintv;unordered_setintus;setints;srand(time(0));for(inti0;iN;i){v.push_back(rand());//v.push_back(rand()i);//v.push_back(i);}size_t begin1clock();for(constinte:v)us.insert(e);size_t end1clock();coutunordered_set insert: end1-begin1endl;size_t begin2clock();for(constinte:v)s.insert(e);size_t end2clock();coutset insert: end2-begin2endl;coutunordered_set size: us.size()endl;coutset size: s.size()endl;size_t begin3clock();for(constinte:v)us.find(e);size_t end3clock();coutunordered_set find: end3-begin3endl;size_t begin4clock();for(constinte:v)s.find(e);size_t end4clock();coutset find: end4-begin4endl;size_t begin5clock();for(constinte:v)us.erase(e);size_t end5clock();coutunordered_set erase: end5-begin5endl;size_t begin6clock();for(constinte:v)s.erase(e);size_t end6clock();coutset erase: end6-begin6endl;return0;}3.简单实现3.1 闭散列-线性探测解决哈希冲突闭散列和开散列闭散列在当前空间找下一个位置除留余数法hash表删除/插入/查找简单实现基于闭散列的开放定址法线性探测负载因子越大冲突概率越大空间利用率越高负载因子越小冲突概率越小空间利用率越低哈希表不能满了再扩容一般负载因子(有效数据个数/总大小)在0.7~0.8之间0.75最好就扩容#pragmaonceenumSTATE{EMPTY,DELETE,EXIST};namespacediy{templateclassK,classVstructHashData{pairK,V_kv;STATE _stateEMPTY;};templateclassKstructDefaultHashFunc{size_toperator()(constKkey){returnsize_t(key);//负数的key也一并处理了}};templatestructDefaultHashFuncstring{//模板的特化size_toperator()(conststringkey){size_t hashi0;for(constcharch:key)hashihashi*131ch;//字符串-整型比较常用因此也有很多方法不论哪种方法其实不同字符串都有可能映射为相同的值选择合适的方法尽可能降低这种概率returnhashi;}};structHashFunc{//需要在类实例化时显示传参size_toperator()(conststringstr){returnstr[0];}};//仿函数指定判断关系考虑使用仿函数1.优先级队列用于比较 2.红黑树封装map用于获取key//3.hash实现用来获取key如果是string或自定义类型转为整数方便后续处理相当于两层映射string-整型-下标templateclassK,classV,classHashFuncDefaultHashFuncKclassHashTable{public:boolInsert(constpairK,Vkv){//if ((double)_n / (double)_table.size() 0.7) {if(_n*10/_table.size()7){//扩容size_t newSize_table.size()*2;HashTableK,V,HashFuncnewHT;newHT._table.resize(newSize);for(inti0;i_table.size();i){//扩容后映射关系变了重新映射原来冲突扩容后可能不冲突原来不冲突扩容后可能冲突if(_table[i]._stateEXIST)newHT.Insert(_table[i]._kv);}_table.swap(newHT._table);}HashFunc hf;size_t hashihf(kv.first)%_table.size();while(_table[hashi]._stateEXIST){hashi;hashi%_table.size();}_table[hashi]._kvkv;_table[hashi]._stateEXIST;_n;returntrue;}HashDataconstK,V*Find(constKkey){HashFunc hf;size_t hashihf(key)%_table.size();while(_table[hashi]._state!EMPTY){if(_table[hashi]._stateEXIST_table[hashi]._kv.firstkey)return(HashDataconstK,V*)_table[hashi];hashi;hashi%_table.size();}returnnullptr;}boolErase(constKkey){HashDataconstK,V*retFind(key);if(ret){ret-_stateDELETE;_n--;returntrue;}returnfalse;}HashTable(){_table.resize(10);}private:vectorHashDataK,V_table;size_t _n0;};}3.2 开散列拉链法#pragmaoncetemplateclassKstructDefaultHashFunc{size_toperator()(constKkey){returnsize_t(key);//处理key为负}};template//模版特化处理key为string不能直接取模需要string-整型structDefaultHashFuncstring{size_toperator()(conststringkey){size_t hash0;for(constcharch:key)hashhash*131ch;returnhash;}};//也可以为string单独定义一个类//但是类实例化第三个参数必须显式传参open_address::HashTablestring, string,open_address::StringHashFunc ht;//包括内部用到的 HashTableK, V, HashFunc newHT; 也必须显式传参//模版特化可以不用显式传参因为用的是缺省参数structStringHashFunc{size_toperator()(conststringkey){size_t hash0;for(constcharch:key)hashch;returnhash;}};namespaceopen_address{enumSTATE{EMPTY,DELETE,EXIST};templateclassK,classVstructHashData{pairK,V_kv;STATE _stateEMPTY;/*HashData(const pairK,V kv) :_kv(kv) {}*/};templateclassK,classV,classHashFuncDefaultHashFuncKclassHashTable{public:HashFunc hf;//查HashDataK,V*Find(constKkey){size_t hashihf(key)%_table.size();while(_table[hashi]._state!EMPTY){if(_table[hashi]._stateEXIST_table[hashi]._kv.firstkey)return_table[hashi];hashi;hashi%_table.size();}returnnullptr;}//增boolInsert(constpairK,Vkv){if(Find(kv.first))returnfalse;if(_n*10/_table.size()7){size_t newsize_table.size()*2;HashTableK,V,HashFuncnewHT;newHT._table.resize(newsize);for(size_t i0;i_table.size();i){if(_table[i]._stateEXIST)newHT.Insert(_table[i]._kv);}_table.swap(newHT._table);}size_t hashihf(kv.first)%_table.size();while(_table[hashi]._stateEXIST){//处理冲突hashi;hashi%_table.size();}_table[hashi]._kvkv;_table[hashi]._stateEXIST;_n;returntrue;}//删boolErase(constKkey){HashDataK,V*retFind(key);if(ret){ret-_stateDELETE;_n--;returntrue;}returnfalse;}HashTable(){_table.resize(10);}private:vectorHashDataK,V_table;size_t _n;};}namespacehash_bucket{templateclassK,classVstructHashNode{pairK,V_kv;HashNodeK,V*_next;HashNode(constpairK,Vkv):_kv(kv),_next(nullptr){}};templateclassK,classV,classHashFuncDefaultHashFuncKclassHashTable{typedefHashNodeK,VNode;HashFunc hf;public:Node*Find(constKkey){size_t hashihf(key)%_table.size();Node*cur_table[hashi];while(cur){if(cur-_kv.firstkey)returncur;curcur-_next;}returnnullptr;}//增boolInsert(constpairK,Vkv){//查已经有了就不插入了if(Find(kv.first))returnfalse;//扩容if(_n_table.size()){size_t newSize_table.size()*2;vectorNode*newTable(newSize,nullptr);//不能直接复用Insert逻辑因为Insert逻辑是开辟空间那么就需要开辟空间、释放旧空间完全没必要只需要改变链接关系即可for(size_t i0;i_table.size();i){Node*cur_table[i];while(cur){Node*nextcur-_next;size_t hashihf(cur-_kv.first)%_table.size();cur-_nextnewTable[hashi];newTable[hashi]cur;curnext;}_table[i]nullptr;}_table.swap(newTable);}size_t hashihf(kv.first)%_table.size();Node*newnodenewNode(kv);newnode-_next_table[hashi];_table[hashi]newnode;_n;returntrue;}boolErase(constKkey){//直接找然后删除行不通因为不知道前驱size_t hashihf(key)%_table.size();Node*cur_table[hashi],*prevnullptr;while(cur){//找到了if(cur-_kv.firstkey){if(prevnullptr)//头删_table[hashi]cur-_next;elseprev-_nextcur-_next;deletecur;_n--;returntrue;}//往后遍历curcur-_next;}//没找到returnfalse;}//赋值拷贝HashTable(constHashTableK,Vht){size_t htsizeht._table.size();_table.resize(htsize,nullptr);for(size_t i0;ihtsize;i){Node*curht._table[i];while(cur){Node*newnodenewNode(cur-_kv);newnode-_next_table[i];_table[i]newnode;curcur-_next;}}_nht._n;}HashTableK,Voperator(constHashTableK,Vht){HashTableK,Vtmp(ht);returntmp;}//析构逻辑_table是vector会先调用vector存储对象的析构之后析构vector但指针是内置类型不做处理因此需要深度析构~HashTable(){for(size_t i0;i_table.size();i){Node*cur_table[i];while(cur){Node*nextcur-_next;deletecur;curnext;}_table[i]nullptr;}_n0;}HashTable(){_table.resize(10,nullptr);}private:vectorNode*_table;size_t _n0;};}