用wex5可以做网站吗,网络营销策划目标,建设工程是指哪些内容,做ppt的网站 知乎哈希表的增删查改的效率很高#xff0c;是O#xff08;1#xff09;#xff0c;比搜索二叉树要快很多。那么他是怎么实现的呢#xff1f;他与计数排序有点相似就是通过映射的方式实现。不过在哈希表中不需要开这么的数据#xff0c;它只需要开一部分空间然后使用除留余数…哈希表的增删查改的效率很高是O1比搜索二叉树要快很多。那么他是怎么实现的呢他与计数排序有点相似就是通过映射的方式实现。不过在哈希表中不需要开这么的数据它只需要开一部分空间然后使用除留余数法去实现这个方法的缺点就是会导致哈希冲突很集中。并且哈希表是不能满的因为哈希表要控制他的负载因子负载因子 表中数据/表的大小 衡量哈希表满的程度。负载因子越大增删查改的效率越低。一般负载因子在0.7左右开始增容。但是负载因子越小浪费空间越多以下是代码实现 enum State{EMPTY, EXITS, DELETE,};templateclass Tstruct HashData{T _data;State _state;//用于查看下一个位置是是被删除还是本来就是空的};templateclass K, class T, class KOFVclass HashTable{typedef HashDataT HashData;public:bool Insert(const T d){//负载因子 表中数据/表的大小 衡量哈希表满的程度//负载因子越大增删查改的效率越低//一般负载因子在0.7左右开始增容//但是负载因子越小浪费空间越多KOFV kofv;if (_table.size() 0 || _num * 10 / _table.size() 7){//开新空间并且拷贝过去//重新映射//释放旧空间//int newcapacity _table.size() 0 ? 10 : _table.size() * 2;//vectorHashData newtable;//newtable.resize(newcapacity);//for (int i 0; i _table.size(); i)//{// int index kofv(_table[i]._data) % newtable.size();// if (newtable[i]._state EXITS)// {// while (_table[index]._state EXITS)// {// index;// if (index _table.size())// index 0;// }// }// newtable[index] _table[i];//}//_table.swap(newtable);HashTableK, T, KOFV newht;int newcapacity _table.size() 0 ? 10 : _table.size() * 2;newht._table.resize(newcapacity);for (int i 0; i _table.size(); i){if (_table[i]._state EXITS){newht.Insert(_table[i]._data);}}_table.swap(newht._table);}int index kofv(d) % _table.size();while (_table[index]._state EXITS){if (_table[index]._data kofv(d))return false;index;if (index _table.size())index 0;}_table[index]._data d;_table[index]._state EXITS;_num;return true;}HashData* Find(const K key){KOFV kofv;int index key % _table.size();//if (key kofv(_table[index]._data))//{// if (_table[index]._stata EXITS)// return _table[index];// else//DELETE// return nullptr;//}//else//{// index;// if (_table[index]._state EMPTY)// {// return nullptr;// }// else// {// {// index;// if (index _table.size())// index 0;// }// return _table[index];// }//}while (_table[index]._state ! EMPTY){if (kofv(_table[index]._data) key){if (_table[index]._state EXITS)return _table[index];elsereturn nullptr;}index;if (index _table.size())index 0;}return nullptr;}bool Erase(const K key){HashData* ret Find(key);if (ret){ret-_state DELETE;--_num;return true;}else{return false;}}private:vectorHashData _table;size_t _num 0;};templateclass Kstruct SetkeyOfv{const K operator()(const K key){return key;}};
