我要评论一、哈希的概念及特性
（一）概念
哈希表（hash table）是一种特殊的数据结构，主要用于快速实现数据的查找、插入和删除操作。哈希表的核心在于通过哈希函数（散列函数）将关键码值映射到表中一个位置来访问记录，从而加快查找速度。哈希表由一个存放记录的数组组成，这个数组被称为散列表。
（二）常见的哈希函数
1. 直接定址法（不存在哈希冲突）：
2.除留余数法（存在哈希冲突）：
3.平方取中法：
4.折叠法
5.随机数法：
6. 数学分析法：
注： 哈希函数设计的越精妙，产生哈希冲突的可能性越低，但是无法避免哈希冲突。
（三）哈希冲突
在哈希表中可能会存在哈希函数设计不够合理的情况，因此会出现哈希冲突，即不同的关键字通过相同的哈希函数算出了相同的哈希地址。如上表中如果插入关键字17，那么通过哈希函数计算出的哈希地址为 hash(17) = 17 % 10 = 7 ，则与关键字7的哈希地址发生了冲突。
（四）哈希冲突解决办法：
解决哈希冲突的两种常见的办法是： 闭散列和开散列
二、闭散列
也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，
那么可以把key存放到冲突位置中的“下一个” 空位置中去。
本质是当前位置冲突了，后面找一个合适的位置继续存储。
线性探测
从发生冲突的位置开始，依次向后探测，直到找到下一个空位置为止。
- 插入
通过哈希函数获取待插入元素在哈希表中的位置 - 如果该位置没有元素则直接插入，如果该位置中有元素则代表发生了哈希冲突，使用线性探测找到下一个空位置，插入新元素。
代码实现如下：
template<class k, class v>
class hashtable {
public:
hashtable(size_t size = 10)
{
_tables.resize(size);
}
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;
hashtable<k, v> newht(newsize);
// 遍历旧表，插入到新表
for (auto& e : _tables)
{
if (e._state == exist)
{
newht.insert(e._kv);
}
}
_tables.swap(newht._tables);
}
// 线性探测
size_t hashi = kv.first % _tables.size();
while (_tables[hashi]._state == exist)
{
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = exist;
_n++;
return true;
}
private:
vector<hashdata<k, v>> _tables;
size_t _n = 0;
};
- 删除
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
如果要删除15这个值，接下来继续进行查找6的操作，如果直接删除则会出现如下情况：
此时，15已经被删除，但是如果我们要继续查找6这个元素，根据查找的原则，找到或者遇到空则停止，此时则会出现表中6是存在的，但是由于15被删除为空，所以查找不到6这个关键字。因此可以通过标记的方法来解决这个问题，在哈希表中设置三种状态，分别为empty，exist，delete。
代码实现如下：
enum state // 枚举三种状态
{
empty,
exist,
delete
};
template<class k, class v>
struct hashdata {
pair<k, v> _kv;
state _state = empty; // 标记，初始状态设置为空
};
bool erase(const k& key)
{
size_t hashi = key % _tables.size();
while (_tables[hashi]._state != empty)
{
if (_tables[hashi]._kv.first == key)
{
_tables[hashi]._state = delete;
_n--;
return true;
}
++hashi;
hashi %= _tables.size();
}
return false;
}
- 查找
使用相同的哈希函数计算哈希地址，如果计算出的地址关键字不是要找的值，那么继续线性向后查找。直到找到或者遇到空。根据上面删除后无法继续查找的问题，因此在查找过程中如果遇到标记为删除的位置，则继续查找。如果一直找到了表尾的位置，需要继续向下查找，则需要往表头回绕继续查找。
代码实现如下：
hashdata<k, v>* find(const k& key)
{
size_t hashi = key % _tables.size();
while (_tables[hashi]._state != empty)
{
if (_tables[hashi]._state == exist && _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
else {
hashi++;
hashi %= _tables.size();
}
}
return nullptr;
}
- 扩容
在哈希表中，哈希冲突越多，则效率就会越低。对于闭散列，荷载因子（负载因子）是特别重要的因素。一般限制在0.7。
闭散列的模拟实现
/*
仿函数处理key
当遇到不同类型的key值时，都需要将key值转为size_t类型，再将size_t类型的值通过哈希
函数转换为地址。
*/
template<class k>
struct hashfunc {
size_t operator()(const k& key)
{
return (size_t)key;
}
};
template<>
struct hashfunc<string> {
size_t& operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash += e;
hash *= 131;
}
return hash;
}
};
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(size_t size = 10)
{
_tables.resize(size);
}
hash hs;
hashdata<k, v>* find(const k& key)
{
size_t hashi = hs(key) % _tables.size();
while (_tables[hashi]._state != empty)
{
if (_tables[hashi]._state == exist && hs(_tables[hashi]._kv.first) == hs(key))
{
return &_tables[hashi];
}
else {
hashi++;
hashi %= _tables.size();
}
}
return nullptr;
}
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;
hashtable<k, v> newht(newsize);
for (auto& e : _tables)
{
if (e._state == exist)
{
newht.insert(e._kv);
}
}
_tables.swap(newht._tables);
}
hash hs;
size_t hashi = hs(kv.first) % _tables.size();
while (_tables[hashi]._state == exist)
{
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = exist;
_n++;
return true;
}
bool erase(const k& key)
{
hash hs;
size_t hashi = hs(key) % _tables.size();
while (_tables[hashi]._state != empty)
{
if (_tables[hashi]._kv.first == key)
{
_tables[hashi]._state = delete;
_n--;
return true;
}
++hashi;
hashi %= _tables.size();
}
return false;
}
private:
vector<hashdata<k, v>> _tables;
size_t _n = 0;
};
}
三、开散列拉链法/哈希桶
（一）概念：
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
根据上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
首先每个桶的元素都是通过一个单链表链接起来，各个链表的头节点都存储在哈希表中。
因此需要先创建单链表节点的类。
代码实现如下：
template<class t>
struct hashnode {
typedef hashnode<t> node;
hashnode(const t& data)
:_next(nullptr)
,_data(data)
{}
node* _next;
t _data;
};
仿函数在开放地址法已经写好，直接使用即可。
代码如下：
/*
仿函数处理key
当遇到不同类型的key值时，都需要将key值转为size_t类型，再将size_t类型的值通过哈希
函数转换为地址。
*/
template<class k>
struct hashfunc {
size_t operator()(const k& key)
{
return (size_t)key;
}
};
template<>
struct hashfunc<string> {
size_t& operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash += e;
hash *= 131;
}
return hash;
}
};
- 查找
通过哈希函数计算出关键字在哪个桶中，接下来只需遍历这个桶即可。
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;
}
- 插入
所实现的哈希桶中，值时唯一的。首先使用哈希函数，计算出key值所在的哈希地址，如果发现关键字已经存在，则返回false。
代码实现如下：
bool insert(const pair<k, v>& kv)
{
/*
寻找哈希桶中是否已经存在要插入的值，如果存在则返回false。
*/
if (find(kv.first))
return false;
hash hs;
// 负载因子到1就扩容
if (_n == _tables.size())
{
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;
}
- 删除
首先计算出桶的位置，接下来在桶中找到这个值，如果存在则删除，但是要先保存即将删除节点的前一个节点，这样在删除节点后才可以将链表重新连接在一起。
如果删除的节点是第一个节点，则没有前一个节点，此时就直接将此节点和计算出的桶的位置连接起来。
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) // 存在前一个节点
{
prev->_next = cur->_next;
}
else //不存在前一个节点
{
_tables[hashi] = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
（二）开散列整体代码模拟实现：
// t -> k
// t -> pair<k,v>
template<class t>
struct hashnode {
typedef hashnode<t> node;
hashnode(const t& data)
:_next(nullptr)
,_data(data)
{}
node* _next;
t _data;
};
template<class k, class t, class keyoft, class hash>
//封装迭代器
class hashtable;
template<class k, class t, class keyoft, class hash>
struct __htiterator {
typedef hashtable<k, t, keyoft, hash> ht;
typedef hashnode<t> node;
typedef __htiterator<k, t, keyoft, hash> self;
node* _node;
ht* _ht;
__htiterator(node* node,ht* ht)
:_node(node)
,_ht(ht)
{}
self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else {
keyoft kot;
hash hs;
size_t hashi = hs(kot(_node->_data))% _ht->_tables.size();
hashi++;
while (hashi <_ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
hashi++;
}
//后面没有桶了
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
t& operator*()
{
return _node->_data;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
};
// 前置声明
template<class k, class t,class keyoft, class hash>
class hashtable {
public:
template<class k, class t, class keyoft, class hash>
friend struct __htiterator;
typedef hashnode<t> node;
typedef __htiterator<k, t, keyoft, hash> iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]) {
return iterator(_tables[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
hashtable(size_t size = 10)
{
_tables.resize(size, nullptr);
_n = 0;
}
~hashtable()
{
for (int 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 t& kv)
{
keyoft kot;
if (find(kot(kv)) != end())
{
return false;
}
hash hs;
// 负载因子到1就扩容
if (_tables.size() == _n)
{
size_t newsize = _tables.size() * 2;
vector<node*> new_tables(newsize,nullptr);
// 取出旧表当中的节点，重新计算挂到新的表桶中
for (int i = 0; i < _tables.size(); i++)
{
node* cur = _tables[i];
while (cur)
{
node* next = cur->_next;
// 头插到新表
size_t hashi = hs(kot(cur->_data)) % newsize;
cur->_next = new_tables[hashi];
new_tables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(new_tables);
}
size_t hashi = hs(kot(kv)) % _tables.size();
node* newnode = new node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
iterator find(const k& key)
{
keyoft kot;
hash hs;
size_t hashi = hs(key) % _tables.size();
node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur,this);
}
cur = cur->_next;
}
return iterator(nullptr,this);
}
bool erase(const k& key)
{
keyoft kot;
hash hs;
size_t hashi = hs(key) % _tables.size();
node* prev = nullptr;
node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev)
{
prev->_next = cur->_next;
}
else {
_tables[hashi] = cur->_next;
}
delete cur;
return true;
}
else {
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector<node*> _tables;
size_t _n;
};
}
（三）unorderset的封装
template<class k>
class set
{
struct setkeyoft
{
const k& operator()(const k& key)
{
return key;
}
};
public:
typedef typename hash_bucket::hashtable<k, k, setkeyoft, hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
bool insert(const k& key)
{
return _ht.insert(key);
}
iterator find(const k& key)
{
return _ht.find(key);
}
bool erase(const k& key)
{
_ht.erase(key);
}
private:
hash_bucket::hashtable<k,k,setkeyoft> _ht; // 底层使用哈希桶实现
}
（四）unordermap的封装
template<class k,class v>
class map
{
struct mapkeyoft
{
const k& operator()(const pair<k,v>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::hashtable<k, pair<k, v>, mapkeyoft, hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
bool insert(const pair<k, v>& kv)
{
return _ht.insert(kv);
}
iterator find(const k& kv)
{
return _ht.find(kv);
}
bool erase(const k& kv)
{
_ht.erase(key);
}
private:
hash_bucket::hashtable<k,pair<k,v>,mapkeyoft> _ht; // 底层使用哈希桶实现
}
发表评论