网站备案管理办法,设计师可以在哪些网站接单,网络广告营销的好处,要建设一个网站目录
一、哈希的概念与方法
1、哈希概念
2、常用的两个哈希函数
二、闭散列的实现
1、基本结构#xff1a;
2、两种增容思路 和 插入
闭散列的增容#xff1a;
哈希表的插入#xff1a;
3、查找
4、删除 三、开散列的实现
1、基本结构
2、仿函数Hash
3、迭代器…
目录
一、哈希的概念与方法
1、哈希概念
2、常用的两个哈希函数
二、闭散列的实现
1、基本结构
2、两种增容思路 和 插入
闭散列的增容
哈希表的插入
3、查找
4、删除 三、开散列的实现
1、基本结构
2、仿函数Hash
3、迭代器实现
4、增容和插入
5、查找
6、删除
7、Clear和析构函数
四、哈希表模拟实现unordered_set和unordered_map 看这篇文章之前你需要对哈希表有一定了解本文主讲代码实现
一、哈希的概念与方法
1、哈希概念 哈希表和数组区别哈希表是在数组的基础上按 映射关系放的 比如我们身份证号就是个映射关系比如看身份证号的前几位就能知道你是哪个省的后几位就能看出你的生日 注 哈希映射方式的算法 哈希表使用哈希建立的数据结构 2、常用的两个哈希函数
注由于除留余数法是目前很好的哈希函数本文讲解用的全是除留余数法故不用直接定址法 1. 直接定址法 --( 常用 ) 取关键字的某个线性函数为散列地址 Hash Key A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况 面试题 字符串中第一个只出现一次字符 2. 除留余数法 --( 常用 ) 设散列表中允许的 地址数为 m 取一个不大于 m 但最接近或者等于 m 的质数 p 作为除数 按照哈希函数 Hash(key) key% p(pm), 将关键码转换成哈希地址 直接定址法是是 没有哈希冲突的每个值都映射了一个唯一位置但为什么要引入除留余数法因为若数据分布不均匀那么我们给每个值映射一个位置可能会造成巨大的空间浪费。而除留余数法不再是给每个值映射一个位置是在限定大小的空间中将我们的值映射进去。 index key % 空间大小。 除留余数法带来的问题不同的值可能会映射到相同位置上去导致哈希冲突。哈希冲突越多整体而言效率越低。 除留余数法的使用: 如何解决哈希冲突呢 解决哈希冲突两种常见的方法是闭散列和开散列 1、闭散列——开放定址法当前位置冲突了则按规则再给你找个位置 a、线性探测 b、二次探测 2、开散列——拉链法哈希桶重点 二、闭散列的实现
先用哈希表的查找来引出基本结构的设计 可见删除会影响查找可不可以这样考虑直接遍历整个表查找一下有没有21不行哈希表就是为了效率而生的你这么搞效率就是ON了哈希表就没意义了。
注哈希表的代码在HashTable.h中实现 1、基本结构 这里的哈希表实现完全可以写为KV模型的但是我们这里是为了模拟实现unordered_set与unordered_map故我们用KT K就是按照关键字K来查找等unordered_set对于T会传入K而unordered_map对于T会传入pairK,V故用T来表示对两种结构的通用而KeyOfT表示要取出的数据是K类型的因为我们后续的比较都是用K类型的来直接比较所以我们要取出T中的K这一点利用仿函数来实现(因为两种结构所传入的T不同) 哈希表中存放两个变量为什么要用vector首要原因是哈希表的本质就是数组而vector符合是动态数组这一点其次是方便vector是自定义类型它支持的resize等操作在我们实现哈希表过程中非常好用并且它的析构也不用我们管 enum State
{EMPTY, //空EXIST, //存在DELETE //删除
};templateclass T
struct HashData
{T _data;State _state; //代表数据状态HashData():_state(EMPTY),_data(0){}
};templateclass K, class T, class KeyOfT
class HashTable
{typedef HashDataT HashData;
private:vectorHashData _tables; //哈希数组size_t _num 0; //表中存了多少个有效个数不等于容量
}; 代码中HashTable不写构造函数是因为_num初始给0了而vector是自定义类型它本身就有构造函数所以没必要写构造函数 2、两种增容思路 和 插入
闭散列的增容 负载因子衡量哈希表满的程度哈希表不敢让表太满表一满那对于哈希表插入等操作的效率是非常低的所以引入负载因子 增容分两种思路
1、传统思路 a、开2倍大小的新表b、遍历旧表的数据重新计算在新表中位置c、释放旧表 增容不能直接将旧表中的数据拷贝到新表中就完事了而应该重新映射若不重新映射由于表的大小会变旧表中的数据到新表中的数据会改变故要重新映射 2、简便思路 创建一个新的哈希表利用哈希表已实现的Insert操作直接把原哈希表中每个数据插入到新哈希表中注意临界条件如果是初次增容只会resize开辟空间详细操作见代码 哈希表的插入 当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有 空位置那么可以把 key 存放到冲突位置中的 “ 下一个 ” 空位置中去。那如何寻找下一个空位置呢怎么找利用线性探测和二次探测怎么插入就要找空位置或者是被删除过的位置这一点闭散列使用enum枚举状态做到的 规则 a、线性探测挨着往后找直到找到空位置b、二次探测按 i^2跳跃着往后找直到找到空位置 线性探测 我们先计算出该数据映射到的位置如果映射的位置已有数据则继续挨着往后找直到找到一个空位置EMPTY或一个被删除过的位置DELETE我们一定能找到一个位置的因为闭散列的数组我们引入了负载因子我们不可能让数组满了的。 其次要注意闭散列是一个数组结构走到尾部还没找到一个位置就要回数组头部去找针对此操作代码可以用以下两种写法(index代表位置): //法一、
if (index _tables.capacity())
{index 0;
}
//法二、
index % _tables.capacity(); 二次探测 线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位 置的方式就是挨着往后逐个去找会导致一片一片的冲突因此二次探测为了避免该问题其让冲突的数据相对分散了不会导致连片冲突效率更高 代码如下
bool Insert(const T data)
{KeyOfT koft;//1、增容第一次插入或者负载因子0.7就要增容if (_tables.capacity() 0 || _num * 10 / _tables.capacity() 7){//A、增容——传统思路//vectorHashData newtables;//size_t newcapacity _tables.capacity() 0 ? 10 : _tables.capacity() * 2;//newtables.resize(newcapacity);//开空间自动初始化为0把旧空间数据拷贝到新空间中//for (size_t i 0; i _tables.capacity(); i)//{// if (_tables[i]._state EXIST)// {// size_t index koft(_tables[i]._data) % newtables.capacity();// while (newtables[index]._state EXIST)// {// index;// if (index newtables.capacity())// {// index 0;//走到尾了就要返回头找位置// }// }// newtables[index] _tables[i];// }//}//_tables.swap(newtables);//B、增容——简便思路HashTableK, T, KeyOfT newht;size_t newcapacity _tables.capacity() 0 ? 10 : _tables.capacity() * 2;newht._tables.resize(newcapacity);for (size_t i 0; i _tables.capacity(); i){if (_tables[i]._state EXIST){newht.Insert(_tables[i]._data);//把原哈希表中每个数据利用Insert都插入到新哈希表中}}_tables.swap(newht._tables);//交换两者的vector}//1、线性探测//size_t index koft(data) % _tables.capacity();//计算出要映射的位置//while (_tables[index]._state EXIST)//{// if (koft(_tables[index]._data) koft(data))// {// return false;//如果存在相同的数据// }// index;// if (index _tables.capacity())// {// index 0;// }//}//2、二次探测size_t start koft(data) % _tables.capacity();size_t index start;int i 1;while (_tables[index]._state EXIST){if (koft(_tables[index]._data) koft(data)){return false;}index start i * i;i;index % _tables.capacity();}//插入数据_tables[index]._data data;_tables[index]._state EXIST;//用状态表示该位置已有数据_num; //有效数据个数return true;
}
问题解释和知识回顾理解代码 1、vector的resize resize会开空间初始化而初始化什么值你不传他就会默认用这个类型的默认值比如你vector中存的是int那就默认初始化为0你vector中存的是指针默认初始化为nullptr你vector中存的是string默认初始化为空串 2、 增容完这个操作什么意思符合现代写法 1、交换的是vector那_tables不就是增容完的vector吗那我后续操作还可以用_tables 2、newht的_tables就被换得了原vector的空间而newht是个局部变量出作用域就销毁正好把我原vector的空间释放了 3、 KeyOfT koft; 这是什么KeyOfT是模板参数而它是为了取unordered_set和unordered_map中的key值的本质上是利用仿函数实现了这一点故你定义一个仿函数对象koft利用koft调用仿函数operator()即可取出T类型数据中K类型的key值 4、 _num * 10 / _tables.capacity() 7 判断负载因子为什么要这么写因为整数相除不能得到0.7其实转为double也是个方法但是不推荐直接*10不就行了嘛 3、查找 查找操作开头就已解释过 HashData* Find(const K key)
{KeyOfT koft;size_t index key % _tables.capacity();while(_tables[index]._state ! EMPTY){//只要是存在和删除状态就要持续往下找if (koft(_tables[index]._data) key){if (_tables[index]._state EXIST)return _tables[index];//值相等且为存在状态elsereturn nullptr;//值相等但为删除状态说明被删除了}index;//没找到继续往后找index % _tables.capacity();}return nullptr;
} 4、删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素 会影响其他元素的搜索 。比如删除元素 4 如果直接删除掉 44查找起来可能会受影响。因此 线性探测采用标记的伪删除法来删除一个元素 。 bool Erase(const K key){HashData* ret Find(key);if (ret){ret-_state DELETE;//用状态代表删除状态--_num; //--有效元素个数return true;}else{return false;}}测试开散列代码
templateclass K
struct SetKeyOfT
{const K operator()(const K key){return key;}
};void TestCloseHash()
{CLOSEHASH::HashTableint, int, SetKeyOfTint ht;ht.Insert(2);ht.Insert(4);ht.Insert(14);ht.Insert(24);ht.Insert(26);ht.Insert(16);ht.Erase(14);ht.Erase(2);CLOSEHASH::HashDataint* data ht.Find(4);
}用线性探测测试代码 用二次探测测试代码 因为闭散列没有开散列好所以这里闭散列简单实现下即可对于更进一步的迭代器、和实现unordered_set和unordered_map等等操作我们都是用开散列实现开散列才是重中之重 三、开散列的实现 开散列法又叫链地址法 ( 开链法 ) 首先对关键码集合用散列函数计算散列地址具有相同地 址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链 接起来各链表的头结点存储在哈希表中 。 这里的开散列就像个数组和链表的融合体但开散列本质还是个数组 1、基本结构 templateclass T
struct HashNode
{T _data;HashNodeT* _next;HashNode(const T data):_data(data), _next(nullptr){}
};
templateclass K, class T, class KeyOfT, class Hash
class HashTable
{typedef HashNodeT Node;private:vectorNode* _tables; //使用vector一定要包含std库不然使用不了size_t _num 0; //有效元素的个数不是容量
}; 细品(_tables)表是一个指针数组是这个数组中存了第一个节点的地址 2、仿函数Hash 为什么模板参数多了个Hash? 它是个仿函数他可以针对string、自定义类型等不能取模的类型让他们能支持取模运算因为对于开散列也涉及取模运算它要求数据的映射位置 若用string类型就无法取模,如果key的类型是一个结构体呢是不是也不能取模也就是进来的key不一定能取模 因为string不支持直接取模故再写一个仿函数_Hash然后内部使用_Hash即可用仿函数来支持取模运算默认情况下使用_HashK但遇到string我们需显式地传_HashString 那么_HashString的思路是什么拿字符串的第一个字母的ASCII码取模可以吗不好因为若这些字符串的第一个字母相同就容易产生冲突故我们把所有字母ASCII码值加起来因为哈希表是取模后映射位置都用ASCII码来计算就会有对应的映射位置 那怎么使用这个仿函数呢 在HashTable中写个HashFunc直接把数据转换成能取模的因为这个操作需要频繁使用 size_t HashFunc(const K key)
{Hash hash;return hash(key);//利用仿函数把key值转为整形
} 存在的问题 因为不同的字符串相加后可能是相同的那放在同一位置会引起哈希冲突故要把字符串转成整形等用字符串哈希算法来算比如出色的BKDR Hash算法字符串每次乘以131即可则字符串算出来的值就不那么容易冲突了也可以乘以31,1313,13131,131313..但是无论如何一定会有可能发生冲突因为字符串在不限定长度的情况下是无限长的我们要做的就是降低冲突概率 应用BKDR后就会发现不冲突了它大大的降低冲突性 那对于结构体想取模怎么办比如一个人的信息是一个结构体那我们就可以找人的信息中有代表项的东西比如人的电话号码是个字符串就能唯一的代表人。用身份证也行。那如果这个人不能用电话号码和身份证等我们用名字作为代表项码不好名字相同的人很多很容易产生冲突故我们可以用名字另一个代表项比如名字家乡地址作为代表项算出映射位置 注: 因为string类型会经常去做key我们干脆让string作为默认的仿函数一个模板类型要对一个参数作特殊处理就要用到模板特化这下即使不传参数也能处理好string类型的哈希表使用就是在于它变成默认支持的了 templateclass K
struct _Hash
{const K operator()(const K key){return key;//可以取模的直接返回即可}
};//特化
template
struct _Hashstring
{size_t operator()(const string key){//运用BKDR Hash算法size_t hash 0;for (size_t i 0; i key.size(); i){hash * 131; //BKDRhash key[i];//字符串中每个字母ASCII码值相加}return hash;}
};templateclass K, class T, class KeyOfT, class Hash _HashK
class HashTable 注意:上面模板参数class Hash _HashK表示默认会调用_HashK那这个默认一个是string可以默认调用另一个就是能正常取模的类型可以正常调用也就是你调用HashTable时不传这个Hash参数就可以帮你自动调用这个默认的你若不用模板特化的话string类型的是不会帮你默认调用的但我们说了我们的哈希表是为了给unordered_set和unordered_map使用的也就是上层使用的你下层哈希表的实现就不用写为class Hash _HashK了这一点在模拟实现unordered_set和unordered_map时它们俩会写的也就是模拟实现时这里HashTable的参数只会写为class Hash即可 如果我不想在创建对象时还要传仿函数说的是取模的仿函数但是对于string还能正常调用到它的仿函数那就可以用模板特化一个模板类型要对一个参数作特殊处理就要用到模板特化当K是string类型的时候就会调用_Hash的模板特化正常处理string取模问题 但是再来一个类型你也可以写成模板特化但它变成默认的模板参数前提应该是这个类型在某个场景下会被频繁使用但如果不是频繁使用的就没必要整成默认的直接单独写一个仿函数显示传参数即可 3、迭代器实现 关于闭散列的哈希表的迭代器就和list迭代器的思路相仿建议先把list的迭代器的模拟实现看明白不过在此基础上还要额外考虑 这里最需要说明的是operator其他的操作容易理解 哈希桶的迭代器operator思路 迭代器不需要按照插入顺序迭代底层实现也没有考虑但是我们可以思考一下如果按插入的顺序迭代遍历要如何实现 为了我们能找到下一个桶若我们使用vector但我就一个迭代器怎么用vector呢 我怎么知道我在哪个桶呢可以再计算下此时的映射位置即可以通过桶中的值计算我是哪个桶。 如果这里直接传vector那HashFunc就调用不到了所以干脆给个哈希表并且是哈希表指针就能用HashFunc 总结 利用哈希表也就是在迭代器中再创建个哈希表对象的指针利用哈希表找下一个桶因为我哈希表里面有vector啊vector里面存的是头指针利用这个头指针不就能找到下一个桶了 注哈希表迭代器不支持--操作因为它是单向迭代器也就是没有rbegin和rend等等 //前置声明为了让哈希表的迭代器能用哈希表
templateclass K, class T, class KeyOfT, class Hash
class HashTable; templateclass K, class T, class KeyOfT, class Hash
struct __HashTableIterator
{typedef __HashTableIteratorK, T, KeyOfT, Hash Self;typedef HashTableK, T, KeyOfT, Hash HT;typedef HashNodeT Node;Node* _node;//迭代器中存的是节点指针HT* _pht;//对象的指针__HashTableIterator(Node* node, HT* pht):_node(node),_pht(pht){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}Self operator(){if (_node-_next){//如果还能在一个桶中就直接在一个桶中往后走单链表_node _node-_next;}else{// 如果一个桶走完了要往下找到下一个桶继续遍历KeyOfT koft;//先计算我当前是在哪个桶size_t i _pht-HashFunc(koft(_node-_data)) % _pht-_tables.capacity();i;//下一个桶for (; i _pht-_tables.capacity(); i){ //找不为空的桶Node* cur _pht-_tables[i];if (cur){ //如果这个桶不为空_node cur;return *this;//迭代器返回的是迭代器本身}}_node nullptr;//如果没有找到有数据的桶则指针置为空,与end()相符return *this;}}bool operator!(const Self s){return _node ! s._node;}
};
哈希表中的begin()和end()实现 typedef __HashTableIteratorK, T, KeyOfT, Hash iterator;//begin()返回第一个不为空的桶的第一个节点iterator begin(){for (size_t i 0; i _tables.capacity(); i){if (_tables[i]){return iterator(_tables[i], this);//找到了则构造匿名对象返回}}return end();//每个桶中都没找到则返回end()}iterator end(){return iterator(nullptr, this);}4、增容和插入 增容就涉及重新映射元素位置的问题那我们就取出原哈希表中每个桶中的元素然后重新计算它在新表中的映射位置那放到新表中有冲突的元素怎么办头插即可和插入的思路一样或者说增容的思路就包含了插入的思路。我们会一个一个桶往后走那每一个桶都是一个单链表遍历这个单链表用while不断计算桶中每个元素在新表中的映射位置遍历桶我们相当于遍历_tables 插入的关键是这个冲突的值是尾插还是头插到对应位置呢按理说冲突的数据的顺序是无所谓的故头插尾插都可以也就是达到的效果一样但是尾插还要先找到尾再插入故这里用头插实现 假设表容量capacity为10 pairiterator, bool Insert(const T data)
{KeyOfT koft;//1、判断是否增容if (_tables.capacity() _num){ //开散列的实现平衡因子为1就增容且第一次插入也会增容size_t newcapacity _tables.capacity() 0 ? 10 : _tables.capacity() * 2;vectorNode* newtables;newtables.resize(newcapacity, nullptr);//给新的vector开新空间初始化//重新计算旧表的数据在新表中的映射位置for (size_t i 0; i _tables.capacity(); i){ //如果是第一次的增容不会进for循环的故不用担忧表的初始数据是否为nullptr//哈希表中每一个桶都是一个单链表故考察单链表的头插Node* cur _tables[i];while (cur){Node* next cur-_next;size_t index HashFunc(koft(cur-_data)) % newtables.capacity();//重新计算映射位置//头插cur-_next newtables[index];newtables[index] cur;cur next;}_tables[i] nullptr;//映射到新表后置为空}_tables.swap(newtables);//新旧表的vector交换}size_t index HashFunc(koft(data)) % _tables.capacity();//计算新的映射位置//1、先查找这个元素是否在哈希表中Node* cur _tables[index];//知道映射位置就能确定是哪个桶while (cur){if (koft(cur-_data) koft(data))return make_pair(iterator(cur, this), false);//找到相同数据则插入失败elsecur cur-_next;}//2、头插到这个桶中Node* newnode new Node(data);//开辟新节点//头插newnode-_next _tables[index];_tables[index] newnode;_num;//哈希表中有效元素个数return make_pair(iterator(newnode, this), false);
}1、Insert的返回值底层实现就是pairiterator, bool 插入数据 若要插入的数据已存在于哈希表中则返回已存在的数据的位置并返回false即代码中的make_pair(iterator(newnode, this), false)这里用的是iterator的构造函数因为构造函数初始化列表有一个哈希表指针而this就是我本身的哈希表指针( HashTableK, T, KeyOfT, Hash*类型的) 若要插入的数据不存在于哈希表中则返回这个要插入数据的位置并返回true即代码中的make_pair(iterator(cur, this), true); 5、查找
Node* Find(const K key)
{KeyOfT koft;size_t index HashFunc(key) % _tables.capacity();//先计算映射位置Node* cur _tables[index];while (cur){if (koft(cur-_data) key)return cur;elsecur cur-_next;}return nullptr;//走遍桶都没找到则返回空
} 6、删除 开散列的删除就相当于单链表的删除故要找前一个节点而删除的前一步是找到你要删除的数据在不在 bool Erase(const K key)
{assert(_tables.capacity() 0);//有空间才能删KeyOfT koft;size_t index HashFunc(key) % _tables.capacity();Node* cur _tables[index];Node* prev nullptr;//记录cur的前一位置while (cur){if (koft(cur-_data) key){if (prev nullptr){ //如果是头删_tables[index] cur-_next;}else{prev-_next cur-_next;}delete cur;--_num;return true;}else{prev cur;cur cur-_next;}}return false;//要删除数据根本不存在
} 7、Clear和析构函数 虽然哈希表不用我们写构造函数但是因为哈希表中每个节点都是动态开辟的故我们要释放下每个节点遍历每个桶每个桶都是单链表即考察单链表的节点释放 ~HashTable(){Clear();//vector不用我们释放因为它是自定义类型哈希表要清理时vector也会自动清理}void Clear(){for (size_t i 0; i _tables.capacity(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;//清空完数据后置为nullptr}}遗留的问题 当大量的数据冲突这些哈希冲突的数据就会挂在同一个链式桶中 查找时效率就会降低所以开散列-哈希桶也是要控制哈希冲突的。如何控制呢通过控制负载因子不过这里就把空间利用率提高一些负载因子也可以高一些一般开散列把负载因子控制到1会比较好一些 四、哈希表模拟实现unordered_set和unordered_map 对于unordered_set和unordered_map第二个模板参数是个通过哈希来比较的我们实现的是把这个参数放在第四个模板参数万一我的unordered_set的模板参数K是个结构体类型我不能直接取模就直接完蛋了所以要传一个仿函数给哈希表 总结这个默认的模板参数是利用上层模拟实现用的你哈希表的底层实现就写为class Hash即可我上层使用的时候会直接传给你 MyUnordered_set.h中实现unordered_set的
#pragma once
#includeHashTable.h
using namespace OPENHASH;namespace mz
{using OPENHASH::_Hash;templateclass K, class Hash _HashKclass unordered_set{struct SetKOfT{const K operator()(const K k){return k;}};public://加typename是告诉编译器这是个类型你先让我过等实例化了再去找//因为模板没实例化它是不接受你用模板里面的一个类型故要用typename typedef typename HashTableK, K, SetKOfT, Hash::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool insert(const K k){return _ht.Insert(k);}private:HashTableK, K, SetKOfT, Hash _ht;};void test_unordered_set(){unordered_setint s;s.insert(1);s.insert(5);s.insert(4);s.insert(2);unordered_setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;}
} MyUnordered_map.h中实现unordered_map的
#pragma once
#includeHashTable.h
using namespace OPENHASH;namespace mz
{using OPENHASH::_Hash;templateclass K, class V, class Hash _HashK//一般模板参数都是由上一层来控制的class unordered_map{struct MapKOfT {const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename HashTableK, pairK,V, MapKOfT, Hash::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool insert(const pairK, V kv){return _ht.Insert(kv);}V operator[](const K key){//unordered_map的operator[]是给key值返回v的引用//底层实现用的是哈希表的Insert来实现在介绍使用时讲过这点pairiterator, bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;}private:HashTableK, pairK, V, MapKOfT, Hash _ht;//底层是个哈希表};void test_unordered_map(){unordered_mapstring, string dict;dict.insert(make_pair(factual, 真实的));dict.insert(make_pair(fringe, 侵犯));dict.insert(make_pair(intermittent, 间歇的));dict[prerequisite] 先决条件;dict[reduce to] 处于;//unordered_mapstring, string::iterator it dict.begin();auto it dict.begin();while (it ! dict.end()){cout it-first : it-second endl;it;}cout endl;}
} 遗留的问题 很明显我们实现的unordered_map和unordered_set排出来的数据并不是有序的但std库里面会自动排序的 思路再建立一个链表存储数据尾插迭代器遍历时遍历链表就可以保持遍历有序那么主要问题是 遍历时保持插入的顺序这样结构会复杂但迭代器会变简单定义两个指针一个next指针用来挂桶另一个prev指针用来遍历 这个知识了解思路即可 进一步改进 如果表的大小是一个素数冲突率会有一定的降低素数是只能被1和本身所整除的那怎么保证是个素数呢我们可以提供一个素数表数字后面加ul表示无符号的长整形即unsigned long这个素数表从头到尾基本上每个数据都是前一个的2倍而最大的数接近整数最大值【注这个表是STL中的其经过研究具有一定的优越性】 怎么用这个表 在开辟表大小时调用这个素数表从头遍历这个素数表找到比我当前要开辟的大小大的即可 完整源码
http://t.csdnimg.cn/XTY7Y
