🌈个人主页：秦jh_-CSDN博客

🔥 系列专栏：https://blog.csdn.net/qinjh_/category_12575764.html?spm=1001.2014.3001.5482

​ 

目录

unordered系列关联式容器 

unordered_set的使用

unordered_map的使用

底层结构

哈希概念

哈希冲突

哈希冲突解决 

闭散列

线性探测

 插入

扩容

 开散列

插入

 扩容

前言

💬 hello! 各位铁子们大家好哇。

             今日更新了哈希的相关内容

🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

unordered系列关联式容器 

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时时间复杂度为O(logN)。在C++11中，STL又提供了4个 unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同， 查询时的时间复杂度为O(1)。

unordered_set的使用

unordered_set、unordered_map跟set和map的使用差不多，只是unordered是无序的，且迭代器是单向的。

unordered_map的使用

unordered_map也是无序的。

 unordered_map是存储键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。在内部,unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。 unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭 代方面效率较低。unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问 value。

底层结构

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

哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素 时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O(logN)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置 取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称 为哈希表(Hash Table)(或者称散列表) 

总结：

哈希思想：值--存储位置建立映射关系。

哈希表：哈希思想实现的数据结构。

例如：数据集合{1，7，6，4，5，9}；

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

哈希冲突

不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

哈希冲突解决 

解决哈希冲突两种常见的方法是：闭散列和开散列 

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有 空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。 

线性探测

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

插入

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

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素 会影响其他元素的搜索。因此线性探测采用标记的伪删除法来删除一个元素。 

如上图，如果采用的是物理删除元素。遇到空就停止，查找31时，可以正常找到。当删除55后，再去找31，就找不到了，因为原本55的位置现在是空，这样就造成31在，但是找不到的情况。所以采用标记法。

 插入

 哈希表中元素个数到达一定的数量，哈希冲突概率会增大，需要扩容来降低哈希冲突，因此哈希表中元素是不会存满的。那什么时候扩容呢?

扩容

 负载因子：α=填入表中的元素个数 / 散列表的长度。

负载因子越大，冲突率越高，效率越低。

负载因子越小，冲突率越低，效率越高，空间利用率越低。

对于开放定址法，负载因子是很重要的因素，一般控制在0.7~0.8以下。超过0.8时，就得扩容。

所以插入的完整代码如下：

<code>bool Insert(const pair<K, V>& kv)

{

if (Find(kv.first)) //不允许冗余

return false;

//扩容

if (_n * 10 / _tables.size() >= 7)

{

//方法一

//size_t newsize = _tables.size() * 2; //用vector的话需要手动映射

//vector<HashData<K, V>> newtables(newsize);

旧表重新计算负载到新表

//for(size_t i=0;i<_tables.size();i++)

//{ }

//方法二

HashTable<K, V> newHT;

newHT._tables.resize(_tables.size() * 2);

//旧表重新计算负载到新表

for (size_t i = 0; i < _tables.size(); i++)

{

if (_tables[i]._state == EXIST)

{

newHT.Insert(_tables[i]._kv);//用HashTable对象插入，可以复用Insert，不需要手动映射

} //newHT已经是扩容好的了，就跳过扩容，直接来到探测部分

} //新表插入好后，再跟旧表互换

_tables.swap(newHT._tables);

}

size_t hashi = kv.first % _tables.size(); //不能模capacity,否则会得到比size大的数，而size后面的位置不能用[]得到

//线性探测

while (_tables[hashi]._state == EXIST)

{

++hashi;

hashi %= _tables.size(); //如果往后找找不到，就回到前面继续找

}

_tables[hashi]._kv = kv;

_tables[hashi]._state = EXIST;

++_n;

return true;

}

当key不是int类型而是string时，就不能取余数了。那该怎么办呢？

 这里需要用到仿函数，如下图：

当key可以强转成整形时（比如负数，指针等），用缺省的仿函数即可。当key是string这种不能强转成整形的类型时，就要手动写一个转换成整形的仿函数。上方是取string的第一个字符进行返回。同时也要手动传入这个仿函数。

 这种取首字符的方法不是很好，下面是另一种字符串哈希算法：

该方法是遍历整个字符串，把ASCII码值全部加起来并返回。但是遇到"aadd","abcd"等字符串，还是无法较好的映射，于是就有大佬发现乘上某些数后，就不那么容易冲突，如下图：

 由于字符串经常被用来当key，所以这里可以使用特化：

使用特化后，就不需要传这个仿函数了。当类型是可以强转的时候，就会走第一个，当类型是string的时候，就会优先走第二个。

上面的过程是闭散列，代码如下：

<code>template<class K>

struct HashFunc

{

size_t operator()(const K& key)

{

return (size_t)key; //负数、指针都能转

}

};

//特化

template<>

struct HashFunc<string>

{

size_t operator()(const string& key)

{

size_t hash = 0;

for (auto ch : key)

{

hash *= 131;

hash += ch;

}

return hash;

}

};

namespace open_address

{

enum State

{

EMPTY,

EXIST,

DELETE

};

template<class K, class V>

struct HashData

{

pair<K, V> _kv;

State _state = EMPTY;

};

template<class K, class V, class Hash = HashFunc<K>>

class HashTable

{

public:

HashTable()

{

_tables.resize(10);

}

bool Insert(const pair<K, V>& kv)

{

if (Find(kv.first)) //不允许冗余

return false;

//扩容

if (_n * 10 / _tables.size() >= 7)

{

//方法一

//size_t newsize = _tables.size() * 2; //用vector的话需要手动映射

//vector<HashData<K, V>> newtables(newsize);

旧表重新计算负载到新表

//for(size_t i=0;i<_tables.size();i++)

//{ }

//方法二

HashTable<K, V, Hash> newHT;

newHT._tables.resize(_tables.size() * 2);

//旧表重新计算负载到新表

for (size_t i = 0; i < _tables.size(); i++)

{

if (_tables[i]._state == EXIST)

{

newHT.Insert(_tables[i]._kv);//用HashTable对象插入，可以复用Insert，不需要手动映射

} //newHT已经是扩容好的了，就跳过扩容，直接来到探测部分

} //新表插入好后，再跟旧表互换

_tables.swap(newHT._tables);

}

Hash hs;

size_t hashi = hs(kv.first) % _tables.size(); //不能模capacity,否则会得到比size大的数，而size后面的位置不能用[]得到

//线性探测

while (_tables[hashi]._state == EXIST)

{

++hashi;

hashi %= _tables.size(); //如果往后找找不到，就回到前面继续找

}

_tables[hashi]._kv = kv;

_tables[hashi]._state = EXIST;

++_n;

return true;

}

HashData<K, V>* Find(const K& key)

{

Hash hs;

size_t hashi = hs(key) % _tables.size();

//线性探测

while (_tables[hashi]._state != EMPTY)

{

if (_tables[hashi]._state == EXIST &&

_tables[hashi]._kv.first == key)

{

return &_tables[hashi];

}

++hashi;

hashi %= _tables.size();

}

return nullptr;

}

bool Erase(const K& key)

{

HashData<K, V>* ret = Find(key);

if (ret == nullptr)

{

return false;

}

else

{

ret->_state = DELETE;

--_n;

return true;

}

}

private:

vector<HashData<K, V>> _tables;

size_t _n = 0; //有效数据个数

};

void TestHT1()

{

int a[] = { 10001,11,55,24,19,12,31 };

HashTable<int, int> ht;

for (auto e : a)

{

ht.Insert(make_pair(e, e));

}

cout << ht.Find(55) << endl;

cout << ht.Find(31) << endl;

ht.Erase(55);

cout << ht.Find(55) << endl;

cout << ht.Find(31) << endl;

}

void TestHT2()

{

int a[] = { 10001,11,55,24,19,12,31 };

HashTable<int, int> ht;

for (auto e : a)

{

ht.Insert(make_pair(e, e));

}

ht.Insert(make_pair(32, 32));

ht.Insert(make_pair(32, 32));

}

//如果key不支持强转成整形取模，就要自己提供转换成整形的仿函数

void TestHT3()

{

HashTable<string, int> ht;

ht.Insert(make_pair("sort", 1));

ht.Insert(make_pair("left", 1));

ht.Insert(make_pair("insert", 1));

//cout << StringHashFunc()("abcd") << endl;

//cout << StringHashFunc()("aadd") << endl;

}

}

 开散列

概念：开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地 址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链 接起来，各链表的头结点存储在哈希表中。

插入

插入是头插，让新节点的next指向当前的第一个节点，然后再让新节点变成头节点。

 扩容

扩容的大逻辑跟前面一样。但是需要注意，vector里面每个位置存的是一个一个的桶，当swap后，newHT出了作用域就会调用析构，此时只会销毁每个位置，而不会销毁每个桶，所以需要我们自己写出析构函数。

上面的扩容方式，new了多少个节点，就得销毁多少个节点，所以不太好，下面是另一种方式：

重新开一个vector，将旧表里的桶依次取出放到新表对应的位置上，然后销毁旧表的每个位置，最后再进行交换。 

 插入完整代码如下：

<code>bool Insert(const pair<K, V>& kv)

{

if (Find(kv.first))

return false;

Hash hs;

//扩容

//负载因子为1时扩容

if (_n == _tables.size())

{

//HashTable<K, V> newHT;

//newHT._tables.resize(_tables.size() * 2);

旧表重新计算负载到新表

//for (size_t i = 0; i < _tables.size(); i++)

//{

//Node* cur = _tables[i];

//while(cur)

//{

//newHT.Insert(cur->_kv);

//cur = cur->_next;

//}

//}

//_tables.swap(newHT._tables);

vector<Node*> newTables(_tables.size() * 2, nullptr);

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

while(cur)

{

Node* next = cur->_next;

//头插到新表的位置

size_t hashi = hs(cur->_kv.first) % newTables.size();

cur->_next = newTables[hashi];

newTables[hashi] = cur;

cur = next;

}

_tables[i] = nullptr;

}

_tables.swap(newTables);

}

size_t hashi = hs(kv.first) % _tables.size();

Node* newnode = new Node(kv);

//头插

newnode->_next = _tables[hashi];

_tables[hashi] = newnode;

++_n;

return true;

}

闭散列完整代码：

template<class K>

struct HashFunc

{

size_t operator()(const K& key)

{

return (size_t)key; //负数、指针都能转

}

};

//特化

template<>

struct HashFunc<string>

{

size_t operator()(const string& key)

{

size_t hash = 0;

for (auto ch : key)

{

hash *= 131;

hash += ch;

}

return hash;

}

};

namespace hash_bucket

{

template<class K, class V>

struct HashNode

{

pair<K, V> _kv;

HashNode<K, V>* _next;

HashNode(const pair<K, V>& kv)

:_kv(kv)

,_next(nullptr)

{}

};

template<class K, class V, class Hash = HashFunc<K>>

class HashTable

{

typedef HashNode<K, V> Node;

public:

HashTable()

{

_tables.resize(10, nullptr);

_n = 0;

}

~HashTable()

{

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

while (cur)

{

Node* next = cur->_next;

delete cur;

cur = next;

}

_tables[i] = nullptr;

}

}

bool Insert(const pair<K, V>& kv)

{

if (Find(kv.first))

return false;

Hash hs;

//扩容

//负载因子为1时扩容

if (_n == _tables.size())

{

//HashTable<K, V> newHT;

//newHT._tables.resize(_tables.size() * 2);

旧表重新计算负载到新表

//for (size_t i = 0; i < _tables.size(); i++)

//{

//Node* cur = _tables[i];

//while(cur)

//{

//newHT.Insert(cur->_kv);

//cur = cur->_next;

//}

//}

//_tables.swap(newHT._tables);

vector<Node*> newTables(_tables.size() * 2, nullptr);

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

while(cur)

{

Node* next = cur->_next;

//头插到新表的位置

size_t hashi = hs(cur->_kv.first) % newTables.size();

cur->_next = newTables[hashi];

newTables[hashi] = cur;

cur = next;

}

_tables[i] = nullptr;

}

_tables.swap(newTables);

}

size_t hashi = hs(kv.first) % _tables.size();

Node* newnode = new Node(kv);

//头插

newnode->_next = _tables[hashi];

_tables[hashi] = newnode;

++_n;

return true;

}

Node* Find(const K& key)

{

Hash hs;

size_t hashi = hs(key) % _tables.size();

Node* cur = _tables[hashi];

while (cur)

{

if (cur->_kv.first == key)

{

return cur;

}

cur = cur->_next;

}

return nullptr;

}

bool Erase(const K& key)

{

Hash hs;

size_t hashi = hs(key) % _tables.size();

Node* prev = nullptr;

Node* cur = _tables[hashi];

while (cur)

{

if (cur->_kv.first == key)

{

//如果删除的是第一个

if (prev == nullptr)

{

_tables[hashi] = cur->_next;

}

else

{

prev->_next = cur->_next;

}

delete cur;

return true;

}

else

{

prev = cur;

cur = cur->_next;

}

}

return false;

}

private:

vector<Node*> _tables; //指针数组

size_t _n;

//vector<list<pair<K, V>>> _tables;

};

void TestHT1()

{

int a[] = { 10001,11,55,24,19,12,31,4,34,44 };

HashTable<int, int> ht;

for (auto e : a)

{

ht.Insert(make_pair(e, e));

}

ht.Insert(make_pair(32, 32));

ht.Insert(make_pair(32, 32));

ht.Erase(31);

ht.Erase(11);

}

void TestHT2()

{

HashTable<string, int> ht;

ht.Insert(make_pair("sort", 1));

ht.Insert(make_pair("left", 1));

ht.Insert(make_pair("insert", 1));

}

}