Hash目录
前言 ：本文以上传至我的个人博客，在这里 www.lienguang.com
一. 无序系列关联式容器
1. 对比
什么是unordered系列
unordered系列的关联式容器有unordered-map/unordered-set/unordered-multimap/unordered-multiset，这些版本的关联式容器和普通版本的又有什么区别呢？我们简单使用下和普通版本的做一个对比。
#include <iostream>
#include <map>
#include <unordered_map>
int main()
{
std::map<int, int> m;
m.insert(std::make_pair(1, 1));
m.insert(std::make_pair(4, 4));
m.insert(std::make_pair(2, 2));
m.insert(std::make_pair(4, 4));
m.insert(std::make_pair(6, 6));
std::cout << "map:" << std::endl;
for(auto e : m)
{
std::cout << e.first << " " << e.second << std::endl;
}
std::unordered_map<int, int> um;
um.insert(std::make_pair(1, 1));
um.insert(std::make_pair(4, 4));
um.insert(std::make_pair(2, 2));
um.insert(std::make_pair(4, 4));
um.insert(std::make_pair(6, 6));
std::cout << "unordered-map:" << std::endl;
for(auto e : um)
{
std::cout << e.first << " " << e.second << std::endl;
}
}
map:
1 1
2 2
4 4
6 6
unordered-map:
6 6
2 2
1 1
4 4
对比结果很明显，我们发现map往往会将插入的键值对按照key的大小比较排序，因此打印出来的数据是有序的，因为其底层是一棵红黑树，因此这样的结果也是理所应当的，但是unordered-map就如它的名字一样遍历出来的数据是无序的，但是依然能完成键值对的查找功能，unordered-map与map最为显著的差距就在这里，看上去unordered-map并不如map强大，那为什么还要存在unordered系列呢？因为其查找索引能够达到O（1）的时间复杂度，比红黑树更快，因为其底层数据结构是一个哈希桶，关于底层实现我们之后再讨论，至于unordered系列的使用，和非unordered系列几乎没有区别，之前已经写过，可以点击这个链接回顾一下：STL——关联式容器
2. unordered_map
- 存储<key, value>键值对的关联式容器，其允许通过key快速的索引到与其对应的value。
- 键值用于唯一地标识元素，而映射值是一个对象，其内容与此键值关联。键值和映射值的类型可能不同
- 没有对<key, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中
- unordered_map容器通过key访问单个元素要比map快
- 实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value
例如：
unordered_map<int, int> um;
um.insert(make_pair(1, 1));
//operator[]: 插入
um[100] = 100;
//operator[]: 修改
um[1] = 15;
注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回。这里贴出其底层实现：
mapped_type& operator[] ( const key_type& k );
pair<iterator, bool> insert(const value_type &x);
(*((this->insert(make_pair(k,mapped_type()))).first)).second
所以对insert返回值的first，就是pair第一个元素iterator迭代器，进行解引用，得到一个pair数据也就是kv键值对，拿到second成员，就是value。
还有一个需要注意的地方，mapped_type()。
这是value的默认构造，插入成功会返回当前K对应的pair数据迭代器以及bool（这里是true）。
插入失败会返回已经存在的K对应的pair数据迭代器以及bool（这里是false）。
3. unordered_set
- 其底层依然存储着一个pair，不过其中key值和value值都是相同的即<value, value>
- 插入元素只需提供value即可。
- 取消了[]操作，因为set的key和value一致并且不允许修改于是这个接口也不再有存在的必要。
例如：
unordered_set<int> us;
us.insert(10);
unordered_set<int>::iterator uit = us.begin();
while (uit != us.end())
{
cout << *uit << " ";
++uit;
}
4.小总结
二. 哈希表
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( log2n)，搜索的效率取决于搜索过程中元素的比较次数。
那有没有一种搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素？当然是有的。
unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构. 那什么是哈希表？
哈希表是一种根据映射来存储数据的结构，我们可以自定义一个哈希函数，通过key和哈希函数算出各个value实际在空间中存储的位置，然后进行value的存储，我们想要查找某个数据的时候也只需要通过同样的方法找到对应位置就可以拿到value。
举个例子，我们现在有个数组，我们约定数组对应下标就存储对应key的数据value。如arr[1] = value1, arr[2] = value2, … , arr[n] = valuen。由此一来我们想要根据key查找某个value就直接访问数组中对应下标的元素arr[key]即可。这就是通过哈希建立映射的方法，并且这里的查找速度只需要O1，这就是典型的以空间换时间的做法，因为这里可能会出现空间的大量浪费。
如果发生这么一种情况，key的上限过大，比如几千万，但是中间的数据可能十分零散，此时我们为了继续建立映射不得不创建一个长度为几千万的数组，会导致中间可能会有很多空间根本没有映射来存value，例如现在要存储两个映射key == 1, key == 10000000，我们发现这两个映射之间在没有其他映射了，那么这一个长度为10000000的数组中就只存了两个值，由此就算我们节省了时间却浪费了过多的空间，因此哈希函数的选择尤为重要了。
总之哈希表就是这么一种通过哈希函数建立key和value之间映射的结构。
1. 哈希函数
某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
- 插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放 - 搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)。
哈希函数的确定十分重要，向我们刚刚所举的例子中我们采用的哈希函数就是直接导致我们造成大量空间浪费的原因，因此在适当的时机选取何时的哈希函数也是十分重要的，接下来简单介绍几种哈希函数。
直接定址法
取关键字的某个线性函数为散列地址：Hash(key) = A * key + b。这种哈希函数的优点也很明显，十分简单，均匀，但是它只适用于key的范围确定，且值较小还比较连续的情景，一但key过大，或者不连续就会出现大量空间被浪费的情况。
除留余数法
这种方法是最为常用的哈希函数。假设我们散列表中允许的最大地址为m，我们可以取一个小于等于m的质数p作为除数，然后执行哈希函数Hash(key) = key % p(p <= m)，将余数作为地址进行定址。一般来说我们为了使得哈希表可以增容都会将除数设置为随着哈希表总长度而改变的变量，并且在不考虑其他因素的情况下，除数==容量的情况可以最大程度的利用空间。
平方取中法
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为 4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。
下面来看一个例子：
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间大小，这里设置为10
目前来看没问题，但是向集合中插入元素44，会出现什么问题？
余数都为4，我们都要存在地址为4的位置上，此时该怎么办呢，我们一个位置又不能存储两个数啊，于是这里就牵扯到了如何解决哈希冲突。
2. 哈希冲突
不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。
哈希冲突的解决可以分为两大类，闭散列和开散列。
闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
- 插入
1.通过哈希函数获取待插入元素在哈希表中的位置
2.如果该位置中没有元素则直接插入新元素
3.如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
例如：还是上面那个例子，插入44，找到空的位置
- 查找
1.通过哈希函数计算元素在哈希表中的位置
2.查看当前位置的元素是否与查找数据相同，相同则查找结束
3.不相同，继续向后查找，直到找到或者走到空的位置（说明不存在） - 删除
1.查找元素
2.将该元素状态置为删除状态，这是一种假删除，只修改状态，不删掉数据
二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就 是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为： Hi= (H0 + i ^ 2) % m, 或者：H0 = (Hi - i ^ 2) % m。其中： i = 1,2,3… ， H0是通过散列函数Hash(x)对元素的关键码key进行计算得到的位置，m是表的大小。
闭散列的模拟实现
这里使用除留余数法+线性探测法实现哈希表。在实现时要注意为了标记散列表一个位置当前是否已经存在元素，我们要给每个结点都附加一个状态值，空/存在/删除三种状态，空和存在状态很好理解，删除状态的定义是为了方便再哈希表中删除结点所定义的状态，因为如果我们直接删除一个结点的话可能会影响其他结点的查找，因此我们一般删除都是采用该表状态为删除状态的这种伪删除法。
#include<utility>
#include<vector>
#include<iostream>
using namespace std;
enum State
{
EMPTY,
EXIST,
DELETE
};
template<class K, class V>
struct Node
{
public:
pair<K, V> _kv= pair<K, V>();
State _state= EMPTY;
};
template<class K,class V>
class HashTabke
{
public:
typedef Node<K, V> Node;
HashTabke(size_t n = 5)
:_size(0)
{
_ht.resize(n);
}
bool insert(const pair<K,V>& kv)
{
//检查容量
CheckCapacity();
//哈希函数计算位置，这里用除留余数法
int idx = kv.first%_ht.size();
while (_ht[idx]._state == EXIST)
{
//如果存在看k是否相同
if (_ht[idx]._state == EXIST && _ht[idx]._kv.first == kv.first)
return false;
//如果存在 但K不相同 继续++
++idx;
if (idx == _ht.size())
idx = 0;
}
//状态为空或者删除
_ht[idx]._kv = kv;
_ht[idx]._state = EXIST;
++_size;
return true;
}
Node* find(const K& key)
{
int idx = key % _ht.size();
while (_ht[idx]._state!=EMPTY)
{
if (_ht[idx]._state == EXIST && key == _ht[idx]._kv.first)
return &_ht[idx];
++idx;
if (idx == _ht.size())
idx = 0;
}
return nullptr;
}
bool erase(const K& key)
{
Node* cur = find(key);
if (cur)
{
//删除 只修改状态
cur->_state = DELETE;
--_size;
return true;
}
return false;
}
void CheckCapacity()
{
if (_ht.size() == 0 || _size * 10 / _ht.size() >= 7)
{
int newc = _ht.size() == 0 ? 5 : 2 * _ht.size();
HashTabke<K, V> newht(newc);
//遍历旧表
for (int i = 0; i < _ht.size(); i++)
{
if (_ht[i]._state == EXIST)
{
newht.insert(_ht[i]._kv); //插入新表
}
swap(_ht, newht._ht);
}
}
}
private:
vector<Node> _ht;
size_t _size;
};
我们还要关心一个概念即负载因子，哈希表总会有被存满的时候，尤其是采用闭散列的时候，如果存放数据越多，就会发生越来越多的冲突，我们在解决起来可能就要遍历整张表，使得哈希表的性能下降，因此我们要尽可能避免一张哈希表被存满，这里就要对哈希表进行扩容。
负载因子 = _size / c（容量）,(_size为哈希表中有效结点的个数)。这个公式可知负载因子是不可能大于1的，等于1时则哈希表已满，那么我们必须选取一个合适的值，当哈希表还没满，性能降低还不太明显的时候就进行增容，当然增容也不能太过频繁，因为哈希表的增容也会付出很大代价，一般来说对于闭散列我们的负载因子要求其大于等于0.7就可以开始增容了。
在上面的实现中，对于增容的操作也是需要注意的，首先如果是空表容量为0，就直接设置为5，否则将容量设置为原来的二倍。创建一张新表，遍历旧表，将旧表中存在的元素插入新表中。
开散列
开散列：也叫哈希桶或拉链法。开散列相比闭散列，可以更加有效的解决哈希冲突，因为其的结构是在哈希表的每一个节点上添加一个链表，所有经过哈希函数计算得出地址的结点直接添加到对应的链表上即可，这样一个地址上就不止可以存放一个元素，而是可以存放无限个，更好的处理了哈希冲突。其结构如下：
要注意虽然哈希桶每个结点下面可以挂无数个结点，但是这里的单链表不易过长，否则每次查找结点都要遍历单链表，性能又会有很大程度的降低，于是我们还是需要进行扩容处理，而与闭散列不同的是，闭散列是达到装载因子的时候进行扩容，而开散列则是在元素个数等于它的桶个数，则进行扩容。
开散列的模拟实现
这里使用除留余数法实现哈希桶。
首先介绍一下插入的操作。
#include<utility>
#include<vector>
#include<iostream>
using namespace std;
//开散列
//哈希表中存放结点指针
//每一个哈希表的位置都是一个单链表
//所以产生相同哈希位置的数据都会放入同一个单链表中
template<class K>
struct keyofValue
{
const K& operator() (const K& data)
{
return data;
}
};
template<class V>
struct HashNode
{
V _data;
HashNode<V>* _next;
HashNode(const V& data=V())
:_data(data),
_next(nullptr)
{}
};
template<class K,class V,class keyofValue>
class HashTable
{
public:
typedef HashNode<V> Node;
HashTable(size_t n = 10)
{
_ht.resize(n);
}
bool insert(const V& data)
{
//检查容量
checkCapacity();
//拿到V的K，计算位置
keyofValue kov;
int idx = kov(data) % _ht.size();
//判断当前哈希桶是否存在K重复的元素
Node* cur = _ht[idx];//拿到头节点
while (cur != NULL)
{
if (kov(cur->_data) == kov(data))
return false;
cur = cur->_next;
}
//K不重复，头插
cur=new Node(data);
cur->_next = _ht[idx];
_ht[idx] = cur;
++_size;
return true;
}
private:
vector<Node*> _ht;
size_t _size = 0;
};
注意我这里的实现，
HashTable类有两个成员，一个为vector，里面存放节点指针，另一个为大小_size。
HashNode类为节点的类，有data数据和next下一个节点指针，并且节点中只存放value，并不存放Key。
插入时，检查容量，拿到V的K，计算位置，使用cur拿到该位置的头节点，当K重复的时候，返回false，否则进行头插的操作。
先看第一种增容方法，先创建新表，遍历旧表，从i=0，也就是第一个位置开始，将每一个头节点插入新的表，再删除旧表节点，把原来的桶置为空，最后遍历完成，新旧表进行交换，这时候新表（newtable）全部变成空，并且为局部变量，直接销毁。但是这样一new一delete效率太低，因此有第二个方法。
void checkCapacity()
{
if (_ht.size() == _size)
{
//增容
int newc = _ht.size() == 0 ? 10 : 2 * _size;
HashTable<K, V, keyofValue> newtable;
for (int i = 0; i < _ht.size(); ++i)
{
Node* cur = _ht[i];
while (cur)
{
Node* next = cur->_next;
newtable.insert(cur->_data);
delete cur;
cur = next;
}
//原来的桶置为空
_ht[i] = nullptr;
}
swap(_ht, newtable._ht);
}
}
增容时，创建新表，把数据对应的节点挂到新表对应的哈希桶中，旧表中的节点置为空。先创建新的vector，遍历旧表，计算每个节点在新表中的位置，改变指针的指向即可，把原来的桶置为空，最后遍历完成，进行vector的交换。
void checkCapacity()
{
if (_ht.size() == _size)
{
//增容
int newc = _ht.size() == 0 ? 10 : 2 * _size;
vector<Node*> newht;
newht.resize(newc);
keyofValue kov;
for (int i = 0; i < _ht.size(); ++i)
{
Node* cur = _ht[i];
while (cur)
{
Node* next = cur->_next;
int idx = kov(cur->_data) % newc;
cur->_next = newht[idx];
newht[idx] = cur;
cur = next;
}
//原来的桶置为空
_ht[i] = nullptr;
}
swap(_ht, newht);
}
}
查找的操作，先拿到Key，计算位置，进行单链表的查找。
Node* find(const V& key)
{
keyofValue kov;
int idx = key % _ht.size();//计算位置
Node* cur = _ht[idx];
while (cur)
{
if (cur->_data == data)
return cur;
cur = cur->_next;
}
return nullptr;
}
删除的操作，也是先获取位置，再进行单链表的删除。
bool erase(const K& key)
{
int idx = key % _ht.size();
keyofValue kov;
Node* cur = _ht[idx];
Node* prev = nullptr;
while (cur)
{
if (kov(cur->_data) == key)
{
//删除该节点
if (prev == nullptr)
_ht[idx] = cur->_next;
else
prev->_next = cur->_next;
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
接下来，做一个哈希表的迭代器，需要对节点进行封装，另外需要有一个哈希表的成员，因为一个桶的一条链表走完，并不知道下一条链子在哪里，所以需要借助哈希表，拿到下一个桶的位置，继续++操作。
++时：
如果当前单链表走到空，为了找到下一个非空链表的头结点， 需要定位当前节点在哈希表中的位置，对当前位置+1，从表中的下一个位置开始查找第一个非空链表的头结点。循环结束，需要判断判断是否找到一个非空的头结点，如果idx >= _pht->_ht.size()，说明走到最后空的位置了，当前节点设置为nullptr。
template <class K,class V,class keyofValue>
struct HashIterator
{
typedef HashNode<V> Node;
typedef HashIterator<K,V,keyofValue> Self;
typedef HashTable<K,V,keyofValue> Htable;
Node* _node;
Htable* _pht;
HashIterator(Node* node, Htable* pht)
:_node(node)
,_pht(pht)
{}
V& operator*()
{
return _node->_data;
}
V* operator->()
{
return &_node->_data;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
Self& operator++()
{
//next不为空
if (_node->_next)
_node = _node->_next;
//单链表走到空
else
{
//找到下一个非空链表的头结点
// 1. 定位当前节点在哈希表中的位置
//kov: 获取value的key
keyofValue kov;
size_t idx = kov(_node->_data) % _pht->_ht.size();
// 2. 从表中的下一个位置开始查找第一个非空链表的头结点
++idx;
for (; idx < _pht->_ht.size(); ++idx)
{
if (_pht->_ht[idx])
{
_node = _pht->_ht[idx];
break;
}
}
// 3. 判断是否找到一个非空的头结点
if (idx >= _pht->_ht.size())
_node = nullptr;
}
return *this;
}
};
三. 模拟实现
1. unordered_map封装实现
借助我们刚刚实现的哈希表，进行封装，需要注意的是，为了和库里保持一致，提供 [ ] 的操作，需要将insert的返回值更改为pair类型的键值对，这个上面已经讲到，插入操作直接调用哈希表的insert即可，因此我们还需要对哈希表的insert（）函数返回值进行修改，如下。
pair<iterator,bool> insert(const V& data)
{
//检查容量
checkCapacity();
//拿到V的K，计算位置
keyofValue kov;
int idx = kov(data) % _ht.size();
//判断当前哈希桶是否存在K重复的元素
Node* cur = _ht[idx];//拿到头节点
while (cur != NULL)
{
if (kov(cur->_data) == kov(data))
//return false;
return make_pair(iterator(cur, this), false);
cur = cur->_next;
}
//K不重复，头插
cur=new Node(data);
cur->_next = _ht[idx];
_ht[idx] = cur;
++_size;
//return true;
return make_pair(iterator(cur, this), true);
}
对于 [ ] 的重载操作：
insert返回值的first，也就是pair第一个元素iterator迭代器，进行解引用，因为我们实现的迭代器里是重载了 * 解引用运算符的，所以得到一个pair数据也就是kv键值对，拿到second成员，就是value。
第二种方法，拿到pair第一个元素iterator迭代器，进行箭头 -> 的操作，拿到数据（kv键值对）的地址，对second成员，也就是value进行访问。
template<class K,class V>
class Unordered_map
{
struct mapkeyofValue
{
const K& operator()(const pair<K, V>& data)
{
return data.first;
}
};
public:
typedef typename HashTable<K, pair<K, V>, mapkeyofValue>::iterator iterator;
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
//return ret.first->second;
return (*ret.first).second;
}
pair<iterator,bool> insert(const pair<K, V>& data)
{
return _ht.insert(data);
}
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
private:
HashTable<K, pair<K, V>, mapkeyofValue> _ht;
};
测试
Unordered_map<int, string> ump;
ump.insert(make_pair(1, "a"));
ump.insert(make_pair(11, "b"));
ump.insert(make_pair(12, "c"));
ump.insert(make_pair(8, "e"));
ump.insert(make_pair(28, "f"));
ump.insert(make_pair(3, "g"));
ump[13] = "x";
Unordered_map<int, string>::iterator it = ump.begin();
cout << "* 遍历" << endl;
while (it != ump.end())
{
cout << (*it).first << " " << (*it).second;
++it;
cout << endl;
}
cout << endl;
it = ump.begin();
cout << "- > 遍历" << endl;
while (it != ump.end())
{
cout << it->first << " " << it->second;
++it;
cout << endl;
}
cout << endl;
cout << "范围for 遍历" << endl;
for (auto& p : ump)
{
cout << p.first << " " << p.second;
cout << endl;
}
结果没有问题。
* 遍历
11 b
1 a
12 c
13 x
3 g
28 f
8 e
- > 遍历
11 b
1 a
12 c
13 x
3 g
28 f
8 e
范围for 遍历
11 b
1 a
12 c
13 x
3 g
28 f
8 e
2 . unordered_set 封装实现
和上面相差无几，需要注意的是，取消了 [ ] 的重载，因为键值是不允许修改的，set的迭代器取值直接*it即可，并没有map中first和second的取值方式了。
template<class K>
class Unordered_set
{
struct setkeyofValue
{
const K& operator()(const K& data)
{
return data;
}
};
public:
typedef typename HashTable<K, K, setkeyofValue>::iterator iterator;
pair<iterator,bool> insert(const K& key)
{
return _ht.insert(key);
}
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
private:
HashTable<K, K,setkeyofValue> _ht;
};
测试
Unordered_set<int> us;
us.insert(1);
us.insert(11);
us.insert(2);
us.insert(5);
us.insert(15);
us.insert(8);
us.insert(15);
Unordered_set<int>::iterator it = us.begin();
while (it != us.end())
{
cout << *it<<" ";
++it;
}
11 1 2 15 5 8
3.改进
存储类型的改进
只能存储key为整形的元素，其他类型怎么解决？
所以此处提供将key转化为整形的方法。引进另一个模板参数，采用模板的特化，假设传入的是整数，重载了（）运算符的仿函数还是返回key整数值，传入的是string，就会按照一定的规则转化，这里采用一种简单的方法，对字符串进行转化，当然还有很多方法，这里不再深究，如下。
template<class K>
struct Hfun
{
const K& operator()(const K& key)
{
return key;
}
};
template<>
struct Hfun<string>
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (auto ch : str)
{
hash = hash * 131 + ch;
}
return hash;
}
};
如图，这时候就需要给哈希表和迭代器的参数列表里增加一个新的模板参数：哈希函数。
并且，在每一个需要计算位置的地方，都需要使用我们的仿函数，计算得到新的整数值。
这时候我们再做一个小小的测试。
Unordered_set<string> us;
us.insert("abc");
us.insert("bbc");
us.insert("cbc");
us.insert("dbc");
us.insert("ebc");
如图所示，经过字符串转整数，计算出来的位置效果也是很不错的。
增容的改进
“科学家说：你的表的大小用我这个素数表，效率提高不少”
有人专门做过研究，表的大小为素数的时候，产生哈希冲突的概率会减少，具体的原因不做阐述，读者可以自行研究一下。用了这个素数表以后，增容时就可以按照这个表的数据进行增容，不过对我们哈希表的实现逻辑没有太大的影响，只是一个小小的优化。
size_t GetNextPrime(size_t prime)
{
//素数表
const int PRIMECOUNT = 28;
static const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
size_t i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i];
}
return primeList[i-1];
}
四. 全部代码
下面是无序列容器全部的实现逻辑。
#include<utility>
#include<vector>
#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
//开散列
//哈希表中存放结点指针
//每一个哈希表的位置都是一个单链表
//所以产生相同哈希位置的数据都会放入同一个单链表中
//前置声明
template <class K, class V, class keyofValue, class Hfun>
class HashTable;
template<class K>
struct keyofValue
{
const K& operator() (const K& data)
{
return data;
}
};
template<class V>
struct HashNode
{
V _data;
HashNode<V>* _next;
HashNode(const V& data=V())
:_data(data),
_next(nullptr)
{}
};
template <class K,class V,class keyofValue, class Hfun>
struct HashIterator
{
typedef HashNode<V> Node;
typedef HashIterator<K,V,keyofValue,Hfun> Self;
typedef HashTable<K,V,keyofValue,Hfun> Htable;
Node* _node;
Htable* _pht;
HashIterator(Node* node, Htable* pht)
:_node(node)
,_pht(pht)
{}
V& operator*()
{
return _node->_data;
}
V* operator->()
{
return &_node->_data;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
Self& operator++()
{
//next不为空
if (_node->_next)
_node = _node->_next;
//单链表走到空
else
{
//找到下一个非空链表的头结点
// 1. 定位当前节点在哈希表中的位置
//kov: 获取value的key
keyofValue kov;
Hfun hfun;
//把key转化为整数
size_t idx = hfun(kov(_node->_data)) % _pht->_ht.size();
// 2. 从表中的下一个位置开始查找第一个非空链表的头结点
++idx;
for (; idx < _pht->_ht.size(); ++idx)
{
if (_pht->_ht[idx])
{
_node = _pht->_ht[idx];
break;
}
}
// 3. 判断是否找到一个非空的头结点
if (idx >= _pht->_ht.size())
_node = nullptr;
}
return *this;
}
};
template<class K,class V,class keyofValue,class Hfun>
class HashTable
{
public:
//迭代器声明为友元类
template <class K, class V, class keyofValue,class Hfun>
friend struct HashIterator;
typedef HashNode<V> Node;
typedef HashIterator<K, V, keyofValue,Hfun> iterator;
HashTable(size_t n = 10)
{
_ht.resize(n);
}
iterator begin()
{
//第一个非空链表头节点
for (size_t i = 0; i < _ht.size(); i++)
{
if (_ht[i])
{
return iterator(_ht[i], this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
pair<iterator,bool> insert(const V& data)
{
//检查容量
checkCapacity();
//拿到V的K，计算位置
keyofValue kov;
Hfun hfun;
int idx = hfun(kov(data)) % _ht.size();
//判断当前哈希桶是否存在K重复的元素
Node* cur = _ht[idx];//拿到头节点
while (cur != NULL)
{
if (kov(cur->_data) == kov(data))
//return false;
return make_pair(iterator(cur, this), false);
cur = cur->_next;
}
//K不重复，头插
cur=new Node(data);
cur->_next = _ht[idx];
_ht[idx] = cur;
++_size;
//return true;
return make_pair(iterator(cur, this), true);
}
size_t GetNextPrime(size_t prime)
{
//素数表
const int PRIMECOUNT = 28;
static const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
size_t i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i];
}
return primeList[i-1];
}
void checkCapacity()
{
if (_ht.size() == _size)
{
//增容
int newc = GetNextPrime(_ht.size());
vector<Node*> newht;
newht.resize(newc);
keyofValue kov;
Hfun hfun;
for (size_t i = 0; i < _ht.size(); ++i)
{
Node* cur = _ht[i];
while (cur)
{
Node* next = cur->_next;
int idx = hfun(kov(cur->_data)) % newc;
cur->_next = newht[idx];
newht[idx] = cur;
cur = next;
}
//原来的桶置为空
_ht[i] = nullptr;
}
swap(_ht, newht);
}
}
Node* find(const K& key)
{
keyofValue kov;
Hfun hfun;
int idx = hfun(key) % _ht.size();//计算位置
Node* cur = _ht[idx];
while (cur)
{
if (kov(cur->_data) == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
bool erase(const K& key)
{
Hfun hfun;
int idx = hfun(key) % _ht.size();
keyofValue kov;
Node* cur = _ht[idx];
Node* prev = nullptr;
while (cur)
{
if (kov(cur->_data) == key)
{
//删除该节点
if (prev == nullptr)
_ht[idx] = cur->_next;
else
prev->_next = cur->_next;
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
/*void checkCapacity()
{
if (_ht.size() == _size)
{
//增容
int newc = _ht.size() == 0 ? 10 : 2 * _size;
HashTable<K, V, keyofValue> newtable;
for (int i = 0; i < _ht.size(); ++i)
{
Node* cur = _ht[i];
while (cur)
{
Node* next = cur->_next;
newtable.insert(cur->_data);
delete cur;
cur = next;
}
//原来的桶置为空
_ht[i] = nullptr;
}
swap(_ht, newtable._ht);
}
}*/
private:
vector<Node*> _ht;
size_t _size = 0;
};
//struct strHfun
//{
// size_t operator()(const string& str)
// {
// size_t hash = 0;
// for (auto ch : str)
// {
// hash = hash * 131 + ch;
// }
// return hash;
// }
//};
template<class K>
struct Hfun
{
const K& operator()(const K& key)
{
return key;
}
};
template<>
struct Hfun<string>
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (auto ch : str)
{
hash = hash * 131 + ch;
}
return hash;
}
};
template<class K,class V,class HashFun = Hfun<K>>
class Unordered_map
{
struct mapkeyofValue
{
const K& operator()(const pair<K, V>& data)
{
return data.first;
}
};
public:
typedef typename HashTable<K, pair<K, V>, mapkeyofValue,HashFun>::iterator iterator;
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
//cout << (*ret.first).first;
//return ret.first->second;
return (*ret.first).second;
}
pair<iterator,bool> insert(const pair<K, V>& data)
{
return _ht.insert(data);
}
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
private:
HashTable<K, pair<K, V>, mapkeyofValue,HashFun> _ht;
};
template<class K,class HashFun = Hfun<K>>
class Unordered_set
{
struct setkeyofValue
{
const K& operator()(const K& data)
{
return data;
}
};
public:
typedef typename HashTable<K, K, setkeyofValue,HashFun>::iterator iterator;
pair<iterator,bool> insert(const K& key)
{
return _ht.insert(key);
}
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
private:
HashTable<K, K,setkeyofValue,HashFun> _ht;
};