c++哈希（开散列原理及实现）
我把c++哈希表上篇讲解放在这了，建议大家先看这篇。
前言
在上篇文章中我们详细介绍了，哈希的思想及实现原理，也认识到了闭散列最大的缺陷就是空间利用率比较低，容易这也是哈希的缺陷。怎么来解决这个问题呢？下面我们就来学习一种新的方法————————开散列（链地址法）
一、开散列概念
在前面我们讲的开放定址法，是通过哈希函数将关键码与存储位置建立映射关系，从而将关键码，存储在哈希表中，而这种方式，在数据量大的情况下很容易发生哈希冲突（哈希碰撞）。
为了解决这里的问题，有人提出了，开散列这种方法。
开散列：
当然这里也是利用了哈希映射，只是对底层存储结构做了改变。
开散列法又叫链地址法(开链法)，首先对关键码集合用哈希函数计算散列地址，具有相同地
址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链
接起来，各链表的头结点存储在哈希表中。
通俗的讲，就是我们在闭散列使用的是，vector< int>来模拟哈希表，而使用它发生哈希冲突时我们就要，使用线性探测这种方法来解决它，这样太麻烦了效率还低，不如把哈希表中每个节点换成一个单链表（这里叫哈希桶），这样再发生哈希冲突，我们就可以直接在链表中插入，哈希冲突就很好的解决了。
二、开散列的实现（链地址法的实现）
2.1、哈希桶结点定义
我们想要利用单链表形式来存储关键码，首先要定义链表结点。
注：代码的注释可以帮助我们理解
template<class K, class V>
struct HashNode
{
HashNode* _next;//链接结点
pair<K, V> _kv;//存储关键码
HashNode(const pair<K, V>& kv)
:_kv(kv)
,_next(nullptr)
{}
};
2.2、哈希函数的实现
同闭散列一样，这里我们也需要哈希函数帮助我们建立，关键码与存储位置之间的关系。
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>//，模板特化，应对string类型情况
struct HashFunc<string>
{
size_t operator()(const string& key)
{
// BKDR
size_t hash = 0;
for (auto e : key)
{
hash *= 31;//一种算法，可以有效降低字符串映射位置相同的概率
hash += e;
}
cout << key << ":" << hash << endl;
return hash;
}
};
2.3、插入操作
通过哈希映射找到桶的位置，使用头插尾插都可（同单链表的插入操作）。
在进行插入操作时，如果哈希桶过长（单链表过长）会导致我们的查找效率变低，因此当插入一定量的数据时，我们仍需要进行扩容操作，这里我们也使用负载因此作为是否扩容的依据。
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))//查找防止插入重复
return false;
Hash hf;
if (_n == _tables.size())
{
vector<Node*> newTables;
newTables.resize(_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 = hf(cur->_kv.first) % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t hashi = hf(kv.first) % _tables.size();
Node* newnode = new Node(kv);
// 头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
}
2.4、查找操作
使用关键码（要查找值）映射出哈希值（也就是关键所在桶的序号），在对应桶中查找。
Node* Find(const K& key)
{
Hash hf;
size_t hashi = hf(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}
2.5、删除操作
同单链表删除相同
bool Erase(const K& key)
{
Hash hf;
size_t hashi = hf(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;
}
prev = cur;
cur = cur->_next;
}
return false;
}
3、全部代码
剩下的简单成员函数，就交给大家自己看吧
namespace hash_bucket
{
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)
{
// BKDR
size_t hash = 0;
for (auto e : key)
{
hash *= 31;
hash += e;
}
cout << key << ":" << hash << endl;
return hash;
}
};
template<class K, class V>
struct HashNode
{
HashNode* _next;
pair<K, V> _kv;
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);
}
~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 hf;
if (_n == _tables.size())
{
vector<Node*> newTables;
newTables.resize(_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 = hf(cur->_kv.first) % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t hashi = hf(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 hf;
size_t hashi = hf(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}
bool Erase(const K& key)
{
Hash hf;
size_t hashi = hf(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;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;//哈希表
size_t _n = 0;
};
总结
总的来说，这部分代码实现比较简单，主要时掌握哈希思想。