文章目录
- 哈希
- 哈希冲突
- 哈希函数
- 解决哈希冲突
- 闭散列：
- 开散列
哈希
在顺序结构和平衡树中，元素的Key和存储位置之间没有必然的联系，在进行查找的时候，要不断的进行比较，时间复杂度是O(N)或O(logN)
而有没有这样一种方案，可以直接不经过比较，从表中得到所需要的元素呢？直接进行获取就可以，如果存在这样的结构，那么对它而言的查找效率是很高的
插入元素
根据上面的原理，在插入元素的时候，根据插入元素的Key，找到一个可以映射到一个表中的具体位置，并进行存放
搜索元素
在对元素的Key进行计算后，就可以直接找到它被映射到了表中的哪一个位置，从而可以直接找到它在表中的位置，如果找到了就返回true
上面的这个原理，就叫做哈希，也叫做散列，而在哈希中使用的这个转换函数就叫做哈希函数，也叫做散列函数，构造出来的结构就叫做哈希表，也叫做散列表
下面用一个例子来举例：
例如数据集合有{1, 7, 6, 4, 5, 9}
那么就可以把根据一个哈希转换函数：hash(key) = key % capacity，得到一个专属于它的下标，把这个值存到下标的位置：
通过这样的方法就可以对元素和下标建立一种关系，在寻找的时候可以直接寻找到，在进行数据的存储和查找的过程拥有相当高的效率
但依旧有问题，如果存储的元素正好已经被存储过了呢？
哈希冲突
所谓哈希冲突，简单来说就是不同的Key值经过计算，得到了一个相同的hash值，此时再向表中填写数据就会有问题，这个过程就叫哈希冲突，也叫做哈希碰撞，那为什么会引起哈希碰撞？如何解决？
哈希函数
通常来说，引起哈希碰撞的一个原因是哈希函数有问题
常见的哈希函数定义：
- 直接定址法：取Key值的某个线性函数作为散列地址，例如Hash（Key）= A*Key + B
- 除留余数法：设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
- 平方取中法
- 折叠法
- 数学分析法
哈希函数设计的越好，出现哈希冲突的可能性就越低，但无法避免哈希冲突，也就是说，哈希冲突是一定会发生的
解决哈希冲突
解决的方法通常有两种，闭散列和开散列
闭散列：
当发生哈希冲突的时候，如果哈希表没有被装满，那么就说明哈希表中肯定还有空余位置，那么就放到冲突位置的下一个位置当中去
- 线性探测
从发生哈希冲突的位置开始，依次向后进行探测，直到探测到了一个空位置为止
那么下面模拟实现一下线性探测的实现过程
bool insert(const pair<K, V>& kv)
{
// 考虑扩容问题
if (_n * 10 / _t.size() == 7)
{
size_t newsize = _t.size() * 2;
vector<HashData<K, V>> newV;
newV.resize(newsize);
size_t _newn = 0;
// 把原来的数据放到新表中 遍历一次旧表
for (int i = 0; i < _t.size(); i++)
{
// 如果旧表中这个位置的值存在 就准备放到新表中
if (_t[i]._s == EXIST)
{
size_t newhashi = _t[i]._kv.first % newsize;
while (newV[newhashi]._s == EXIST)
{
newhashi++;
newhashi %= newsize;
}
newV[newhashi]._kv = _t[i]._kv;
newV[newhashi]._s = EXIST;
_newn++;
}
}
_t.swap(newV);
_n = newsize;
}
// 正常插入逻辑
size_t hashi = kv.first % _t.size();
while (_t[hashi]._s == EXIST)
{
// 如果插入元素的位置有内容，就插入到下一个位置
hashi++;
hashi %= _t.size();
}
_t[hashi]._kv = kv;
_t[hashi]._s = EXIST;
_n++;
return true;
}
但是闭散列的缺陷是很明显的，比如当插入数据是12,22,32,42…这样的数据的时候，就会导致不停地触发哈希冲突，这样会产生堆积的效应，为了避免出现这样的问题，又提出了开散列的方案
开散列
开散列也叫做哈希桶，也叫做拉链法，原理就是把具有相同地址的Key值放到一起，每一个子集就叫做一个桶，每个桶的元素通过单链表来进行链接，每个链表的头结点在哈希表中
开散列中每个桶中放的都是哈希冲突的元素
namespace opened_hashing
{
// 定义节点信息
template<class K, class V>
struct Node
{
Node(const pair<K, V>& kv)
:_next(nullptr)
, _kv(kv)
{}
Node* _next;
pair<K, V> _kv;
};
template<class K, class V>
class HashTable
{
typedef Node<K, V> Node;
public:
// 构造函数
HashTable()
:_n(0)
{
_table.resize(10);
}
// 析构函数
~HashTable()
{
//cout << endl << "*******************" << endl;
//cout << "destructor" << endl;
for (int i = 0; i < _table.size(); i++)
{
//cout << "[" << i << "]->";
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
//cout << cur->_kv.first << " ";
delete cur;
cur = next;
}
//cout << endl;
_table[i] = nullptr;
}
}
// 插入元素
bool insert(const pair<K, V>& kv)
{
// 如果哈希表中有这个元素，就不插入了
if (find(kv.first))
{
return false;
}
// 扩容问题
if (_n == _table.size())
{
HashTable newtable;
int newsize = _table.size() * 2;
newtable._table.resize(newsize, nullptr);
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
// 把哈希桶中的元素插入到新表中
int newhashi = cur->_kv.first % newsize;
// 头插
cur->_next = newtable._table[newhashi];
newtable._table[newhashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newtable._table);
}
// 先找到在哈希表中的位置
size_t hashi = kv.first % _table.size();
// 把节点插进去
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
_n++;
return true;
}
Node* find(const K& Key)
{
// 先找到它所在的桶
int hashi = Key % _table.size();
// 在它所在桶里面找数据
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == Key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
void print()
{
for (int i = 0; i < _table.size(); i++)
{
cout << i << "->";
Node* cur = _table[i];
while (cur)
{
cout << cur->_kv.first << " ";
cur = cur->_next;
}
cout << endl;
}
cout << endl;
}
private:
vector<Node*> _table;
size_t _n;
};
}
上面的实现看似没有问题，实际上依旧有问题，如果要传入的数据是string类，那么在比较的过程中会出现错误，因此要写一个仿函数用以处理这些情况
这里利用版本模板中的特化进行处理即可，处理细节比较巧妙
template<class T>
struct _Convert
{
T& operator()(const T& key)
{
return key;
}
};
template<>
struct _Convert<string>
{
size_t& operator()(const string& key)
{
size_t sum = 0;
for (auto e : key)
{
sum += e * 31;
}
return sum;
}
};
那么下一步就要进行对于哈希表的封装了，详情见模拟实现篇章
