在C98中STL提供了底层为红黑树结构的一系列关联式容器在查询时效率可达到log_2

N即最差情况下需要比较红黑树的高度次当树中的节点非常多时查询效率也不理想。

最好

的查询是进行很少的比较次数就能够将元素找到因此在C11中STL又提供了4个unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是

其底层结构不同。

因为unordered_set与unordered_map使用方式类似我们着重见介绍unordered_mapunordered_set见文档。

unordered_map(文档)

value键值对的关联式容器其允许通过keys快速的索引到与其对应的value。

在unordered_map中键值通常用于惟一地标识元素而映射值是一个对象其内容与此键关联。

键和映射值的类型可能不同。

在内部,unordered_map没有对kye,

为了能在常数范围内找到key所对应的valueunordered_map将相同哈希值的键值对放在相同的桶中。

unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代方面效率较低。

unordered_map实现了直接访问操作符(operator[])它允许使用key作为参数直接访value。

unordered_map是单向迭代器

unordered_map容量相关

(返回与key对应的value没有一个默认值)注意该函数中实际调用哈希桶的插入操作用参数key与V()构造一个默认值往底层哈希桶中插入如果key不在哈希桶中插入成功返回V()插入失败说明key已经在哈希桶中将key对应的value返回。

iterator

us;us.insert(4);us.insert(2);us.insert(1);us.insert(5);us.insert(6);/*us.insert(6);us.insert(6);*///可以去重

us.begin();while

v;v.reserve(n);srand(time(0));for

(size_t

从运行结果可以看出unordered_set容器增删查的效率比set快

相关OJ题

重复n次的元素两个数组的交集I两个数组的交集II存在重复元素两句话中不常见的单词

底层结构

unordered系列的关联式容器之所以效率比较高是因为其底层使用了哈希结构。

哈希是一种映射的对应关系将存储的数据根存储的位置使用哈希函数建立出的映射关系方便我们进行查找。

在查找字符串中只出现过一次的字符中就可以创建一个256的int数组去统计次数因为字符总共只有256种这里就建立了字符(char)与字符的值(int)的映射关系直接定址法映射只跟关键字直接相关或者间接相关。

1259100000088888823存起来方便查找,怎么存?(不使用搜索树)

如果每个值直接进行映射那么我们要创建一个100w大小的数组空间浪费十分严重。

基于这个原因哈希引申出一些映射的方式进行补救。

除留余数法(最常用)

不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

现在我们要存11就会发生冲突了这种冲突叫做哈希冲突。

(不同的值映射到了相同的位置)哈希通过映射关系进行查找效率非常高但是哈希最大的问题就是如何解决哈希冲突这里就引入了很多种方法来解决哈希冲突。

哈希冲突解决

闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有

线性探测(从发生冲突的位置开始依次向后探测直到找到下一个空位置为止)

key

通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素

采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素,可能会影响其他元素的搜索。

比如删除元素4如果直接删除掉44查找起来可能会受影响。

因此线性探测采用标记的伪删除法来删除一个元素。

enum

false;*///闭散列哈希表不能满了再增容//因为如果哈希表快满了的时候插入数据冲突的概率很大效率会很低//快接近满的时候就增容//因此提出负载因子的概念表中数据个数比上表的大小//一般情况下负载因子越小冲突的概率特低效率越高//但是控制的太小会导致大量的空间浪费以空间换时间/*if

_tables.size()

2;newht._tables.resize(newsize);for

(auto

EXITS){newht.Insert(data._data);}}_tables.swap(newht._tables);}size_t

index

ht;ht.Insert(4);ht.Insert(14);ht.Insert(24);ht.Insert(5);ht.Insert(15);ht.Insert(25);ht.Insert(6);ht.Insert(16);

线性探测的思路就是如果我的位置被占用了我就挨着往后去占别人的位置可能会导致一片一片的冲突洪水效应。

线性探测优点实现非常简单线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。

如何缓解呢

二次探测

开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地

址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链

开散列实现

data):_next(nullptr),_data(data){}T

_data;HashNodeT*

HashTablestring,string,SetOfTstring

ht;

//HashTablestring,string,SetOfTstring,_HashString

ht;

public:~HashTable(){Clear();}void

Clear(){for

newtables;newtables.resize(newsize);for

(int

newtables[index];newtables[index]

cur;cur

nullptr;}_tables.swap(newtables);}//计算在表中的映射位置size_t

index

HashFunc(koft(data))%_tables.size();Node*

cur

_tables[index];//查找这个值在不在表中while

(cur){if

针对单个桶一个桶链的长度超过一定值就将挂链表改为挂红黑树。

(Java

HashMap就是当桶长度超过8就改成挂红黑树)针对整体控制负载因子

仿函数Hash将对应的key转成可以取余的整型默认的仿函数直接返回key因为有些类型的key直接就可以取余如果是其他自定义类型我们就自己构造一个哈希函数作为仿函数传入Hash模板中。

(常见字符串哈希算法)

开散列与闭散列比较

应用链地址法处理溢出需要增设链接指针似乎增加了存储开销。

事实上由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子a

0.7而表项所占空间又比指针大的多所以使用链地址法反而比开地址法节省存储空间。

unordered_set与unordered_map的模拟实现

模板参数列表的改造增加迭代器操作增加通过key获取value操作

#pragma

data):_next(nullptr),_data(data){}T

_data;HashNodeT*

两者如果相互依赖就需要对其中一个进行前置声明templateclass

class

(_node-_next){//当前桶还有数据走到下一个节点_node

koft;Hash

hash;//如果一个桶走完了找到下一个桶继续遍历size_t

index

hash(koft(_node-_data))%_pht-_tables.size();index;/*for

index

(_node)break;elseindex;}if(index_pht-_tables.size())_node

nullptr;}return

Iterator(_tables[i],this);}}return

end();}Iterator

Iterator(nullptr,this);}~HashTable(){Clear();}void

Clear(){for

newtables;newtables.resize(newsize);for

(int

newtables[index];newtables[index]

cur;cur

nullptr;}_tables.swap(newtables);}//计算在表中的映射位置size_t

index

HashFunc(koft(data))%_tables.size();Node*

cur

_tables[index];//查找这个值在不在表中while

(cur){if

make_pair(Iterator(cur,this),false);}else{//头插到表中cur

cur-_next;}}Node*

HashTableK,K,SetOfT,Hash::Iterator

iterator;iterator

_ht.Insert(key);}private:HashTableK,K,SetOfT,Hash

_ht;};void

test_unorderedset(){unordered_setint

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

s.begin();while

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

pairK,

test_unorderedmap(){unordered_mapstring,

string