在STL库中,有map和set两个关联式容器,这两个容器的底层都是以红黑树为底层。但是在后续的发展过程中,我们发现有些场景的数据不适合用红黑树进行存储,所以有人就发明了底层为哈希表的map和set,称为unordered_map 和 unordered_set,这两个容器的存储内容并不是顺序存储。
目录
一、unordered_map 和 unordered_set
<6>unordered_map 和 unordered_set 的封装
一、unordered_map 和 unordered_set
<1>接口的介绍
这两个容器在使用方面与set和map高度相似,
我们可以发现,基本上这里的接口都和map和set的接口高度重合,具体的用法可自行查询,与map和set无太大的差异。
<2>性能区别
我们可以使用一定的数据对这两个容器进行插入的测试,以此来比较它们之间的性能。下面以set为例。
这里我们先以十万量级的数据做对比,
我们可以看见,在除去重复值的情况下,我们可以看见总共插入3万多的整数,但set插入的时间是unordered_set的两倍。
下面我们对上述的数据进行修改,由于srand函数只能生成3万多个随机数,会产生很多的重复值。所以我们可以对测试代码稍加修改,消除一些重复值,然后将数据量扩大到一百万级别。
运行结果
我们可以看见,虽然两者的插入时间相差不大,但unordered_set的速度仍然比set的插入速度要快。当然,在一些特定的场景下,set插入速度就unordered_set快(比如在有序场景下)。从时间复杂度上来说,哈希表属于O(1)级别,而红黑树属于O(logN);
二、底层
什么是哈希?哈希又称散列,就是将存储的值和存储位置建立起关联关系,并将其存储起来。
上面这种情况就是我们常见的一种情况,把对应的数据映射到对应的下标,并++,但是这种存储方式就存在一种弊端,那就是当数据范围非常大时,我们就需要开非常的空间来存储对应的数据,这种情况是不可取的,所以我们就需要通过别的方式来建立映射。
<1>分类
1.直接定址法
直接定址法就是上述我们所介绍的方法,这种方法胜在能直接找出对应的映射位置,但是会造成空间的浪费。
2.除留余数法
对于直接定址法所产生的问题,我们可以通过除留余数法进行解决。这个方法就是将对应的数据除以哈希表的大小,也就是顺序表的大小,产生的余数就是对应的新下标。但是,这个方法也有一个缺点,那就是会造成哈希冲突(哈希碰撞),也就是多个值映射到同一个位置。
3.随机数法(了解即可,使用的频率较少)
选择一个随机函数,取关键字的随机函数为它的哈希地址,。
还有许多的方法可以建立映射,这里我们不一一赘述,如有需要,可自寻查询。
<2>哈希冲突的解决方法
1、闭散列
该方法也称为开放定址法,当哈希冲突发生时,我们可以将新的数据放到冲突位置的下一个空位置当中。寻找空位的方法也有许多,这里我们主要介绍线性探测的方式来查找。该方法就是依次在映射位置向后查找,遇到结尾要回绕,直到遇见空就停止。
而哈希冲突越多,插入的效率就越低。所以就有了负载因子的概念,负载因子 = 实际存储的数据 / 表的大小。一般我们会将负载因子控制在0.7,如果超过0.7,一般我们就会进行扩容操作。
1、查找与插入
插入位置 i = key % 表的大小,根据i的大小,无论是插入还是查找,我们都可以通过线性探测依次向后查找即可,我们就可以完成插入与删除操作。
2、删除
在删除之前,我们需要先进行查找,这里会产生一些特殊的情况,下面举个例子。
如果我们将15删除后,查找6,我们就会发现找不到6,因为我们在找到6前,就已经存在了空。所以我们对空间上的位置加上一个标记,以此来表示它是被删除的,还是存在,亦或是空。如果是被删除的状态,我们就需要继续向后寻找。
2、开散列
开散列的拉链法,又成为哈希桶。这个方法其实就是将相同的映射值用链表连接起来,顺序表上存储的是链表的头节点。
开散列的删除、插入和查找工作会更加简单,如果要查找,直接在对应的映射的地址上的链表依次查找即可,删除就是单链表的删除。
<3>代码实现中的一些问题
1、在扩容时,我们需要注意的是,新表的数据需要通过旧表重新映射得来。这也就是为什么在数据量级比较大时,set和unordered_set插入速度差不多的原因。
2、在开散列的开放定址法中,我们可以需要通过每个节点加上状态标记,方便后续的查找和删除
3、由于我们在前面存储的数据都是整数,但是日常生活中不可能都是存储整数,一般我们都是以字符串的方式存储数据(也有可能是其他类型的数据),我们需要通过哈希函数来对这些数据进行转换成整数。
哈希函数存在很多的算法,这里不一一赘述,读者可以自行搜寻。比较常见的就是BKDR、DJB、AP等等,这里我使用的BKDR的算法,也就是乘131,1313.....等数值。这里需要特别注意的是,我们一般不用字符串的长度作为转换值,这样可能回造成数值的高度重合。
4、在开散列的开放定址法中,我们的探测方式并不只有线性探测,但需要注意的是查找、删除和插入所用的方法一定是要一样的。
<4>代码实现(闭散列)
template<class K>
struct HashFunc
{
size_t operator()(const K& s)
{
return s;
}
};
template<>//模板特换
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto& e : s)
{
hash += e;
hash *= 131;//防止出现字符串因顺序不同,而造成返回整型相同。
}
return hash;
}
};
namespace open_address
{
enum State
{
EMPTY,
EXIST,
DELETE
};
template<class K, class V>
struct HashData
{
pair<K, V> data;
State state = EMPTY;
};
template<class K, class V, class HashFunc = HashFunc<K>>
class HashTable
{
public:
HashTable(size_t size = 10)
{
_table.resize(size);
}
HashTable<K, V, HashFunc>* Find(const K& key)
{
HashFunc ht;
size_t hashi = ht(key) % _table.size();
while (_table[hashi].state != EMPTY)
{
if (key == _table[hashi].data.first && _table[hashi].state == EXIST)
{
return &_table[hashi];
}
++hashi;
hashi %= _table.size();
}
return nullptr;
}
bool Erease(const K& key)
{
HashTable<K, V>* ret = Find(key);
if (ret)
{
ret->_table.state = DELETE;
}
else
{
return false;
}
--_n;
return true;
}
bool insert(const pair<K, V>& val)
{
//扩容
if ((double)_n / _table.size() >= 0.7)
{
size_t newsize = _table.size() * 2;
//vector<HashData> newtable(newsize);//注释的代码和下面一段代码效果等同
遍历旧表
//for (auto& e : _table)
//{
// if (e.state == EXIST)
// {
// size_t newi = e.data.first % newtable.size();
// while (newtable[newi].state == EXIST)
// {
// ++newi;
// newi %= _table.size();
// }
// newtable[newi].data = e;
// newtable[newi].state = EXIST;
// }
//}
//_table.swap(newtable);
HashTable<K, V, HashFunc> newtable(_table.size() * 2);
for (auto& e : _table)
{
if (e.state == EXIST)
{
newtable.insert(e.data);
}
}
_table.swap(newtable._table);
}
HashFunc ht;
size_t hashi = ht(val.first) % _table.size();
//线性探测
while (_table[hashi].state == EXIST)
{
++hashi;
hashi %= _table.size();
}
_table[hashi].data = val;
_table[hashi].state = EXIST;
_n++;
return true;
}
private:
vector<HashData<K, V>> _table;
size_t _n = 0;
};
}
<5>迭代器的实现和开散列的哈希表实现
迭代器:
template<class K, class V, class KeyOFT, class Hash>//前置声明
class HashTable;
template<class K, class V, class KeyOFT, class Hash>
struct HashIterator
{
public:
typedef HashTable<K, V, KeyOFT, Hash> HT;
typedef HashNode<V> Node;
typedef HashIterator<K, V, KeyOFT, Hash> Self;
HashIterator(HT* p, Node* pc)
:hc(p)
,node(pc)
{
}
V* operator->()
{
return &node->val;
}
V& operator*()
{
return node->val;
}
Self& operator++()
{
if (node->next)
{
node = node->next;
}
else
{
KeyOFT kot;
Hash hs;
size_t hashi = hs(kot(node->val)) % hc->ptr.size();
hashi++;
while (hashi < hc->ptr.size())
{
if (hc->ptr[hashi])
{
node = hc->ptr[hashi];
break;
}
hashi++;
}
if (hashi == hc->ptr.size())
{
node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& val)
{
return node != val.node;
}
HT* hc;
Node* node;
};
这里前置声明是为了能够访问HashTable中的私有成员,这里我直接定义的是HashTable这个类,也可以直接将迭代器的成员变量设置成vector,这样就不需要加前置声明了。
HashTable:
template<class K, class V, class KeyOFT, class Hash>
class HashTable
{
public:
//为了访问hc中的私有成员
template<class K, class V, class KeyOFT, class Hash>
friend struct HashIterator;
typedef HashNode<V> Node;
typedef HashIterator<K, V, KeyOFT, Hash> Iterator;
HashTable()
{
ptr.resize(10, nullptr);
_n = 0;
}
~HashTable()
{
for (size_t i = 0; i < ptr.size(); i++)
{
Node* cur = ptr[i];
while (cur)
{
Node* next = cur->next;
delete cur;
cur = next;
}
ptr[i] = nullptr;
}
}
Iterator begin()
{
for (size_t i = 0; i < ptr.size(); i++)
{
//找到第一个桶的第一个节点
if (ptr[i])
{
return Iterator(this, ptr[i]);
}
}
return end();
}
size_t size()
{
return this->_n;
}
Iterator end()
{
return Iterator(this, nullptr);
}
bool Erease(const K& key)
{
Hash h;
KeyOFT kot;
size_t hashi = h(key) % ptr.size();
Node* cur = ptr[hashi];
Node* prv = nullptr;
while (cur)
{
if (kot(cur->val) == key)
{
if (prv)
{
prv->next = cur->next;
}
else
{
ptr[hashi] = cur->next;
}
delete cur;
--_n;
return true;
}
prv = cur;
cur = cur->next;
}
return false;
}
pair<Iterator,bool> insert(const V& val)
{
if (Find(val).first != end())
{
return make_pair(Find(val).first, false);
}
else
{
Hash h;
KeyOFT kot;
//这里我们直接不采用直接swap两个表的方式,我们直接将节点挂到新的表上,这样我们
//节省析构节点的时间,在所有节点重新挂完后,我们再swap即可
if (_n == ptr.size())//负载因子等于1,就开始扩容
{
vector<Node*> newTable(ptr.size() * 2, nullptr);
for (size_t i = 0; i < ptr.size(); i++)
{
//依次取出旧表中的节点
Node* cur = ptr[i];
while (cur)
{
size_t num = h(kot(cur->val)) % (ptr.size() * 2);
cur->next = newTable[num];
newTable[num] = cur;
cur = cur->next;
}
}
ptr.swap(newTable);
}
size_t n = h(kot(val)) % ptr.size();
Node* newnode = new Node(val);
newnode->next = ptr[n];
ptr[n] = newnode;
_n++;
return make_pair(Iterator(this,newnode),true);
}
}
pair<Iterator,bool> Find(const V& val)
{
KeyOFT kot;
Hash h;
size_t n = h(kot(val)) % ptr.size();
Node* cur = ptr[n];
while (cur)
{
if (kot(cur->val) == kot(val))
{
return make_pair(Iterator(this,cur),true);
}
cur = cur->next;
}
return make_pair(Iterator(this,nullptr),false);
}
private:
vector<Node*> ptr;
size_t _n;
};
上述的KeyOFT模板参数是为上层的unoreded_map 和unordered_set封装做准备的。
<6>unordered_map 和 unordered_set 的封装
unordered_set:
template<class K,class Hash = HashFunc<K>>
class unorderset
{
struct SetKeyOFT
{
const K& operator()(const K& key)
{
return key;
}
};
typedef typename Hash_Bucket::HashTable<const K, K, SetKeyOFT, HashFunc<K>>::Iterator Iterator;
public:
pair<Iterator,bool> Insert(const K& kv)
{
return ht.insert(kv);
}
Iterator begin()
{
return ht.begin();
}
Iterator end()
{
return ht.end();
}
bool Erase(const K& key)
{
return ht.Erease(key);
}
Iterator Find(const K& Key)
{
return ht.Find(Key);
}
private:
Hash_Bucket::HashTable<const K ,K, SetKeyOFT, HashFunc<K>> ht;
};
unordered_map:
template<class K, class V,class Hash = HashFunc<K>>
class unordermap
{
public:
struct MapKeyOFT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOFT, Hash>::Iterator Iterator;
pair<Iterator,bool> Insert(const pair<K, V>& kv)
{
return ht.insert(kv);
}
Iterator begin()
{
return ht.begin();
}
Iterator end()
{
return ht.end();
}
bool Erase(const K& key)
{
return ht.Erease(key);
}
pair<Iterator, bool> Find(const K& Key)
{
return ht.Find(Key);
}
V& operator[](const K& key)
{
pair<Iterator, bool> ret = Insert(make_pair(key,V()));
return ret.first->second;
}
private:
Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOFT, Hash> ht;
};
以上就是所有内容,感谢阅读!!!