C++11中引进了unordered系列的四个容器,而之所以这几个容器效率如此之高,是因为运用到了哈希的思想。
顺序结构以及平衡树中,元素关键码与其存储位置没有对应的关系,所以在插入和查找操作时,需要遍历结构,这样造成的时间复杂度太高。
而我们的哈希就是通过某种函数,让元素的关键码与元素的存储位置构建起一一映射关系。这就是哈希的概念。
当向该结构中:
哈希中使用的函数叫做哈希函数,通过哈希构建的结构称为哈希表或者散列表。
特别注意:以上不论是顺序搜索,还是平衡树搜索或者哈希搜索,得到的key值都不能相同。
什么是哈希冲突呢?其实啊就是不同的关键码通过相同的哈希函数得到相同的映射位置。
这种就叫哈希冲突或者哈希碰撞。发生哈希冲突并具有相同映射位置的不同的关键码就叫同义词。
引起哈希冲突的原因也可能是:哈希函数设计不合理。
我们的哈希函数需要满足:
我们有下面常见的哈希函数:
1、直接定址法(常用)
直接定址法字面上来说就是通过关键码直接得到映射位置。最多再加一个倍数变换,也就是取关键字的某个线性函数为散列地址。
Hash(Key)= A*Key + B
直接定址法的优点是简单并且消除哈希冲突,但是需要事先知道数据的分布情况,因为直接定址法适用于数据集中且数据小的情况,如下:
2、除留余数法(常用)
如果我们设散列表允许的地址数为m,取一个不大于m,但最接近或者等于m的质数作为除数。
Hash(key)=key%p(p<=m)
简单来说,就是将关键码除以散列表的大小得到的余数作为映射的位置。除留余数法的优点是可以处理分散的数据,缺点是会导致哈希冲突,例如对于{1,4,5,614}。
可以看见是会发生哈希冲突的。
3、平方取中法(了解)
假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址。平方取中法适用于不知道关键字分布,但是数据又不是很大的时候。
4、折叠法(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这 几部分叠加求和,并按散列表表长,取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况。
5. 随机数法(了解)
选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中
random为随机数函数。随机数法适用于关键词长度不等的情况。
6. 数学分析法(了解)
设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定 相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散 列地址。数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的 若干位分布较均匀的情况。
闭散列:也叫开放地址法,当发生哈希冲突时,如果哈希表未被填满,说明哈希表中必然还有空位置,那么可以把key存放到冲突位置的下一个空位置中去,为什么说是空位置呢?下面我们会讲解。
这里我们采用线性探测的方法:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
我们来看看实例,假设我们要将arr映射到Hash表中,而表的大小为10,那么:
int arr[]={4,6,14,25,34}
Hash(i)=arr[i]%10;//表的大小为10
那么就应该如下:
注意:当元素本来该在的位置被占用时,需要往后找下一个空位置。比如:4先进入表,就把4的位置占住了,那么当14再进去的时候,由于下标是4的地方已经被占住了,所以向后找到下标为5的位置,插入。而如果此时再来一个28,那么就插入下标为9的地方,而如果再来了一个29,我们可以看到后面的表已经满了,那么就要从头开始查找插入,结果就应该是:
那么好,我们现在已经知道插入一个元素时,先用他的值对表的大小取模,得到位置,如果该位置为空,那么就插入;如果不为空,就向后找下一个空位置。那么大家有没有考虑过我先删掉一个元素再插入呢?
例如我先删除14,再插入54呢?可以看到有两个问题:
那么其实我们的解决方法就是,为每个位置引进一个state状态(EXIST,DELETE,NULL)。
那么我们就可以进行查找、插入、删除操作了:
代码实现如下:
#pragma once
#include <vector>
#include <iostream>
using namespace std;
//标识每个存储位置的状态--空、存在与删除
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 HashTable {
public:
HashTable()
: _n(0)
{
//此处将哈希表的大小默认给为10,各位可以自己给定
_tables.resize(10);
}
bool insert(const pair<K, V>& kv) {
if (find(kv.first))
return false;
//除留余数法 && 线性探测法
//将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置,如果该位置被占用往后放
size_t hashi = kv.first % _tables.size();
//不能放在EXIST的位置,DELETE和EMPTY都能放
while (_tables[hashi]._state == EXIST)
{
++hashi;
hashi%= _tables.size();//防止超过表的大小
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
//将find的返回值定义为Data的地址,可以方便我们进行删除以及修改V
HashData<K, V>* find(const K& key)
{
Hash hash; //仿函数对象,后面会细讲
size_t hashi = hash(key) % _tables.size();
//记录hashi的起始位置
size_t starti = hashi;
//最多找到空
while (_tables[hashi]._state != EMPTY) {
//key相等并且state为EXIST才表示找到
if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)
{
return &_tables[hashi];
}
++hashi;
hashi %= _tables.size();
}
return nullptr;
}
bool erase(const K& key) {
//找不到就不删,找到就把状态置为DELETE即可
HashData<K, V>* ret = find(key);
if (ret) {
ret->_state = DELETE;
return true;
}
return false;
}
private:
vector<Data> _tables;
size_t _n; //记录表中有效数据的个数
};
可以看到,我们表的大小是有限的,不可能插入无数个数,所以不可避免的会发生扩容操作。
我们可以回忆一下数组的扩容,我们是直接在原来的数组上直接多开辟空间。那么同样的方法在这里行不行得通呢?
答案是否定的,因为我们这里要符合哈希函数的映射,如果我们扩容后映射条件是会改变的,比如表的大小从10扩容到20,那么同样的17,原来应该是在下标为7的地方,扩容后就应该在下标17的地方,所以扩容前后的映射条件是不同的。
那我们是不是要等到表满了才扩容呢,其实并不是,如果满了再扩容就有点局促了,没有一点的缓冲的地方,所以我们要规定,插入的元素达到表的多少就扩容。我们定义一个载荷因子。
我们这里定义载荷因子为0.7。
所以扩容具体操作如下:
//扩容
if ((double)_n / _tables.size() > 0.7)
{
//此处不能直接原地扩容,因为映射关系需要改变
Hashtable<K,V,Hash> newHT;
newHT._tables.resize(_tables.size() * 2);
for (auto& e : _tables)
{
if(e._state==EXIST)
{
//此处不会死循环,因为不会进入需不需要扩容这个判断
newHT.Insert(e._data);
}
}
_tables.swap(newHT._tables);
}
我们上面考虑的情况都是插入的值为整数的情况,那么如果插入的是字符串呢?
按道理来讲我们要先将字符串转换为整数,再进行插入。那我们能不能把求映射位置的表达式换成这样呢?
size_t hashi = kv.first[0] % _tables.size();
很显然是不能的,这样又只能满足字符串,那么编译器又不知道你要插入什么类型的元素,万一你插入整型,而整型又不能取[],又会显得鸡肋。
这种问题还得是需要仿函数这位大哥来解决。我们可以为不同的类型定义不同的处理方式:
//int类型
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)
{
return s[0];
}
};
那么对于字符串这种特殊情况,就有很多人去研究具体该如何定义他的映射函数才是更完美的。那么其中最好的就是BKDR哈希字符串算法,也就是将每一位的字符乘以131或者特定的数字,最后相加。
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t len = 0;
for (auto e : s)
{
len += e;
len *= 131;
}
return len;
}
};
#include<iostream>
#include<vector>
using namespace std;
//int类型
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 len = 0;
for (auto e : s)
{
len += e;
len *= 131;
}
return len;
}
};
namespace open_address
{
enum State
{
EMPTY,
DELETE,
EXIST
};
template<class K, class V>
struct Hashdata
{
pair<K, V> _data;
State _state = EMPTY;
};
template<class K, class V,class Hash=HashFunc<K>>
class Hashtable
{
public:
Hashtable(size_t size = 10)
{
_tables.resize(size);
}
Hashdata<K, V>* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._data.first == key
&& _tables[hashi]._state == EXIST)
{
return &_tables[hashi];
}
++hashi;
hashi %= _tables.size();
}
return nullptr;
}
bool Insert(const pair<K,V>& kv)
{
if (Find(kv.first))
{
return false;
}
//扩容
if ((double)_n / _tables.size() > 0.7)
{
//此处不能直接原地扩容,因为映射关系需要改变
Hashtable<K,V,Hash> newHT;
newHT._tables.resize(_tables.size() * 2);
for (auto& e : _tables)
{
if(e._state==EXIST)
{
//此处不会死循环,因为不会进入需不需要扩容这个判断
newHT.Insert(e._data);
}
}
_tables.swap(newHT._tables);
}
Hash hs;
size_t hashi = hs(kv.first) % _tables.size();
while (_tables[hashi]._state != EMPTY)
{
++hashi;
hashi%= _tables.size();
}
_tables[hashi]._data = kv;
_tables[hashi]._state = EXIST;
return true;
}
bool Erase(const K& key)
{
if (!Find(key))
{
return false;
}
else
{
Hashdata<K, V>* ret = Find(key);
ret->_state = DELETE;
_n--;
return true;
}
}
private:
vector<Hashdata<K,V>> _tables;
size_t _n = 0; //实际存储的数据个数
};
}
开散列法又叫做链地址法,首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中(我们这里采用头插的方式)。
闭散列的各个元素之间不会互相影响,所以就不用为每个节点定义状态了。而且每个节点里面都是链表节点。
//int类型
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 len = 0;
for (auto e : s)
{
len += e;
len *= 131;
}
return len;
}
};
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;
private:
vector<Node*> _tables; //指针数组
size_t _n; //表中有效数据的个数
};
}
开散列所用的结构已经与闭散列不相同了,所以对应的操作也应该作出变换。
//插入
bool insert(const pair<K, V>& kv) {
if (find(kv.first))
return false;
//调用仿函数的匿名对象来将key转换为整数
size_t hashi = Hash()(kv.first) % _tables.size();
//哈希桶头插
Node* newNode = new Node(kv);
newNode->next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return true;
}
//查找
Node* find(const K& key) {
size_t hashi = Hash()(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) {
//由于单链表中删除节点需要改变上一个节点的指向,所以这里不能find后直接erase
size_t hashi = Hash()(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
//删除还要分是否为头结点
if (cur->_kv.first == key) {
if (cur == _tables[hashi])
_tables[hashi] = cur->next;
else
prev->next = cur->next;
delete cur;
--_n;
return true;
}
//迭代
prev = cur;
cur = cur->next;
}
return false;
}
与闭散列同样的道理,开散列的插入操作也涉及到扩容操作。因为当我们插入元素时,每个桶中的节点个数会增加,那么极端情况下,可能某个桶下面会挂炒鸡多的节点,这样会影响查找和删除操作的效率。我们就需要进行扩容操作。
我们该什么时候扩容呢?哈希表最好的情况是每个下面都挂一个节点,所以当插入元素个数等于表的大小的时候就进行扩容,此时载荷因子大小为1:
代码如下:
Hash hs;
if (_n == _tables.size())
{
//不用跟开放地址法一样重新创一个HashTable对象,因为会造成指针节点创建又删除
vector<Node*> newvector(_tables.size()*2,nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur1 = _tables[i];
while (cur1)
{
Node* cur2 = cur1->_next;
size_t hashi = hs(cur1->_data) % newvector.size();
cur1->_next = newvector[i];
newvector[i] = cur1;
cur1 = cur2;
}
//把原来的指针置空
_tables[i] = nullptr;
}
_tables.swap(newvector);
}
此处我们无需再去跟开放地址法一样创建一个HashTable对象,然后再根据所有的值各自创建节点插入到扩容后的新表中,因为这样导致新节点的创建,旧节点的销毁。这样是得不偿失的。
我们采用的是直接取出旧表中的节点插入到新表中(注意:不能将整个桶直接插入到新表,因为同样的值对于新表来说映射结果可能改变了),然后交换旧表与新表即可,这样节约了大量的时间。
//哈希表的仿函数
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return key;
}
};
//类模板特化
template<>
struct HashFunc<string> {
size_t operator()(const string& key) {
//BKDR字符串哈希算法
size_t sum = 0;
for (auto ch : key)
sum = sum * 131 + ch;
return sum;
}
};
//开散列
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()
: _n(0)
{
_tables.resize(10, nullptr);
}
//析构--手动释放哈希表中的每个元素,以及每个元素指向的哈希桶
~HashTable() {
//释放每个元素的哈希桶
for (size_t i = 0; i < _tables.size(); ++i) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->next;
delete cur;
cur = next;
}
}
}
//插入
bool insert(const pair<K, V>& kv) {
if (find(kv.first))
return false;
Hash hs;
//扩容--当载荷因子达到1时我们进行扩容
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;
//重新计算映射关系--调用仿函数的匿名对象来将key转换为整数
size_t hashi = hs(cur->_kv.first) % newTables.size();
cur->next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
}
_tables.swap(newTables);
newTables.clear(); //不写也可以,局部的vector变量出作用域自动调用析构
}
//调用仿函数的匿名对象来将key转换为整数
size_t hashi = Hash()(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;
//由于单链表中删除节点需要改变上一个节点的指向,所以这里不能find后直接erase
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
//删除还要分是否为头结点
if (cur->_kv.first == key) {
if (cur == _tables[hashi])
_tables[hashi] = cur->next;
else
prev->next = cur->next;
delete cur;
--_n;
return true;
}
//迭代
prev = cur;
cur = cur->next;
}
return false;
}
private:
vector<Node*> _tables; //指针数组
size_t _n; //表中有效数据的个数
};
}
我们上面在介绍除留余数法时给出的定义是这样的:设哈希表中允许的地址数为m,取一个不大于m,但最接近或者等于m的素数p作为除数,按照 哈希函数 Hash(key) = key % p (p<=m), 将关键码转换成哈希地址;
这里为什么要选择素数来作为除数呢?因为这样能减少哈希冲突发生的概率。
所以我们C++中就有人专门去研究了哪些素数最合适作为除数。那么STL源码如下:
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
inline unsigned long __stl_next_prime(unsigned long n)
{
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
这里还有一个问题,我们设定的是当载荷因子达到1的时候就进行扩容,这样保证哈希表中的每个位置下面挂着三五个节点,保证了效率。
但是极端情况下,例如经历某些特殊攻击的时候(专门插入位于同一种哈希碰撞情况的素数),那么机会导致某个链表很长,这里我们就要对链表这个数据机构做出变换,可以把它换成红黑树,红黑树可以保证查找、插入和删除操作的时间复杂度都是 O(log n),比链表快得多。
所以在极端情况下,可以用红黑树来作为存储结构,而普通情况下就采用链表来存储就可以了。
总结
好了,到这里今天的知识就讲完了,大家有错误一点要在评论指出,我怕我一人搁这瞎bb,没人告诉我错误就寄了。
祝大家越来越好,不用关注我(疯狂暗示)