。

哈希是一种直接映射的方式#xff0c;所以查找的效率很快…前言

前面我们学习了unordered_map和unordered_set容器比较了他们和map、set的查找效率我们发现他们的效率比map、set高进而我们研究他们的底层是由哈希实现。

哈希是一种直接映射的方式所以查找的效率很快。

与学习红黑树和map、set的思路一样我们现在学完了unordered_map和unordered_set本章将模拟实现底层结构来封装该容器

作者建议在阅读本章前可以先去看一下前面的红黑树封装map和set——红黑树封装map和set

这两篇文章都重在强调泛型编程的思想上一篇由于是初认识作者讲解的会更详细一点~

一如何复用一个哈希桶

2、operator*和operator-及operator!和operator的模拟实现

3、operator

我们学习过知道unordered_map和unordered_set容器存放的结点并不一样为了让它得到复用我们就需要对哈希桶进行改造将哈希桶改造的更加泛型一点既符合Key模型也符合Key_Value模型。

所以我们这里还是和封装map和set时一样无论是Key还是Key_Value都用一个类型T来接收这里高维度的泛型哈希表中实现还是用的是Kye_Value模型K是不能省略的同样的查找和删除要用故我们可以引出两个容器各自模板参数类型。

我们给每个容器配一个仿函数各传不同的仿函数拿到想要的不同的数据

3、改造哈希桶

哈希函数我们可以自由选择并传仿函数在各自容器的封装中实现用于比较时我们可以取出各自容器想要的数据

//K

4294967291};//获取比prime大那一个素数size_t

0;for

GetNextPrime(_tables.size());if

(newSize

newTable;newTable.resize(newSize,

nullptr);//遍历旧表for

newTable[hashi];newTable[hashi]

cur;cur

nullptr;}newTable.swap(_tables);}}size_t

hashi

_tables.size();//头插到对应的桶即可Node*

newnode

_tables[hashi];//找到指定的桶之后顺着单链表挨个找while

(cur){if

通过查STL官方库我们也发现其提供了一个取素数的函数所以我们也提供了一个直接拷贝过来

在扩容时加了一条判断语句是为了防止素数值太大过分扩容容易直接把空间(堆)干崩了

以第一个桶中第一个不为空的结点为整个哈希桶的开始结点以空结点为哈希桶的结束结点

2、operator*和operator-及operator!和operator的模拟实现

3、operator

这里要在哈希桶的类外面访问其私有成员我们要搞一个友元类迭代器类是哈希桶类的朋友这样就可以访问了

判断一个桶中的数据是否遍历完如果所在的桶没有遍历完在该桶中返回下一个结点指针如果所在的桶遍历完了进入下一个桶判断下一个桶是否为空非空返回桶中第一个节点空的话就遍历一个桶后置和之前一眼老套路不赘述

unordered_map和unordered_set是不支持反向迭代器的从底层结构我们也能很好的理解单链表找不了前驱所以不支持实现迭代器的operator-

最后注意一点我们需要知道哈希桶大小所以不仅要传结点地址还要传一个哈希桶这样才能知道其大小除此由于哈希桶改造在后面所以我们要在前面声明一下

#includevector

_next(nullptr){}};templateclass

class

HashTable;//哈希桶的迭代器templateclass

class

{};//编译器的原则是向上查找定义必须在前面否则必须先声明HashTableK,

KeyOfT,

_node-_next;}else//当前桶已经走完了要走下一个桶{KeyOfT

kot;HashFunc

_pht-_tables.size();hashi;//找下一个不为空的桶

hashi

_pht-_tables[hashi];break;}}//没有找到不为空的桶用nullptr去做end标识if

(hashi

4294967291};//获取比prime大那一个素数size_t

0;for

GetNextPrime(_tables.size());if

(newSize

newTable;newTable.resize(newSize,

nullptr);//遍历旧表for

newTable[hashi];newTable[hashi]

cur;cur

nullptr;}newTable.swap(_tables);}}size_t

hashi

_tables.size();//头插到对应的桶即可Node*

newnode

_tables[hashi];//找到指定的桶之后顺着单链表挨个找while

(cur){if

false;}private://指针数组vectorNode*

_tables;size_t

有了上面的哈希桶的改装我们这里的对map和set的封装就显得很得心应手了。

#include

ret.first-second;}private:Bucket::HashTableK,

pairK,

test_map(){unordered_mapstring,

string

dict;dict.insert(make_pair(sort,

排序));dict.insert(make_pair(left,

左边));dict.insert(make_pair(left,

上面;dict[string]

]我们知道其原理之后模拟实现就非常方便直接调用插入函数控制好参数和返回值即可。

#include

_ht.Erase(key);}private:Bucket::HashTableK,

SetKeyOfT,

s;s.insert(2);s.insert(3);s.insert(1);s.insert(2);s.insert(5);s.insert(12);unordered_setint::iterator

s.begin();//auto