【C++】Hash闭散列
目录
一、哈希的概念
1.1 哈希冲突
1.2 哈希函数
1.3 装载因子
二、闭散列
2.1 线性探测
2.2 Insert 插入
2.3 Find 查找
2.4 Erase删除
2.5 插入复杂类型
2.6 二次探测
三、源代码与测试用例
3.1 hash源代码
3.2 测试用例
一、哈希的概念
在前面学习了二叉搜索树、AVL树、红黑树之后，我们得知顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须经过关键码的多次比较。顺序查找的时间复杂度为 O(N)，平衡树中为树的高度，即(logN)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快的找到该元素。
当向该结构中：
- 插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
- 搜索元素
对元素的关键码进行同样的计算，把求得的函数当作元素的存储位置，在结构中按此位置取元素进行比较，若关键码相等，则搜索成功。
该方法即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(hash Table)(或称散列表)
使用以上方法插入直接进行映射插入，搜索时不必进行关键码的比较，因为搜索速度非常快。
问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？
1.1 哈希冲突
对于两个数据元素的关键字，其 key1 != key2，但是存在 key1 % p == key2 % p，此时 key1 和key2 就会被映射到 hash Table 中相同的位置。
假设我们将需要存的数n,存的索引值 = n % 10
现在需要将20存入该表中,计算出的键值为0,但是该位置已经有数据了,即发生了哈希冲突.
此时：不同关键字通过相同的哈希函数计算处相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
1.2 哈希函数
引起哈希冲突的一个原因在于：哈希函数设计的不够合理。
哈希函数的设计原则：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间。
- 哈希函数计算出来的地址能均匀的分布在整个空间中。
- 哈希函数设计应足够简单。
常见的两种哈希函数
1. 直接定址法
取关键字的某个线性函数为散列地址：hash(key) = A * Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况。
题目举例：387. 字符串中的第一个唯一字符
2.除留余数法(常用)
设散列表中允许的地址数为 m ，取一个不大于 m ，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：hash(key) = key % p(p<= m)，将关键码转化为哈希地址。
就是以下这种方法
1.3 装载因子
如果hash的插入，进行映射后如果找不到空位就要一直往后面检测查找空位，所以如果当哈希表中只有一个空位时，插入一个数据的时间复杂度很可能就变成了O(N)，所以说再这种情况发生前我们就要对其进行扩容。
那什么情况下进行扩容呢?应该括多大呢？如果是除留余数法，那质数 p又应该是多少呢？
散列表的装载因子定义为：a = 填入表中的元素个数 / 散列表的长度
即。装载因子越小，冲突的概率越小，空间利用率低；装载因子越大，冲突的概率越大，空间利用率高。
而库中的做法是，装载因子如果大于0.7，就进行扩容。
二、闭散列
闭散列：也叫开放地址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的"下一个"空位置中去。
寻找下一个空位置方式有线性探测和二次探测，接下来我们结合理论并实现一下。
2.1 线性探测
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置即可。
结构定义：
首先我们定义结构，我们定义每个位置有三种状态{存在，空位，删除}，一个位置要么是以及有数据了，要么是没有数据，没什么有一个删除呢？
如果出现下面这种情况，20在3的后面进行插入，将3删除后，20便无法查找到，所以我们会再添加一个删除状态，防止以下这种情况发生。
使用一个数组进行存储，其中每一个位置位HashDate类型，该类型中会记录当前位置的状态。再添加一个size变量，用于记录当前存储的有效数据个数。结构如下：
enum State {EMPTY,EXIST,DELETE}; //每个位置有三种状态
template<class K,class V>
struct HashDate
{
pair<K, V> _kv;
State _state;
};
template<class K,class V>
class HashTable
{
public:
//成员函数：
private:
vector<HashDate<K, V>> _table;
size_t _size=0;
};2.2 Insert 插入
- 通过哈希函数(保留余数法)获取待插入元素在哈希表中的位置
- 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。
接下来有几个问题：
1. 确定质数p，我们应该取vector的size()还是capacity()作为质数？
使用size()，因为capacity()是vector开辟的总空间，超过size()的部分是不能直接使用的，只能使用size()以内的空间，而size要通过我们插入数据或resize进行改变。简而言之，vector中超过size()，小于capacity()的部分我们是不能直接访问的，尽管已经开辟。
2.如果线性探测一直探测到 i 下标超过hash_table.size()，我们应该如何做。
如果一直探测超过数组的下标，应该绕回数组的开始处，所以每次 i++ 后，我们可以继续进行取模，如果超过了size()，会自动从数组0下标处开始探测；当然，使用if判断 i 超过size()，超过就置0也是可以的。
3.当装载因子超过0.7之后，我们应该怎么做。
即_size / _table.size() >=7 时，我们要进行扩容，创建一个新哈希表，然后将旧表中的数据拷贝到新表中，此时我们可以复用 Insert 函数，因为新表是不存在扩容问题的，所以会使用 Insert 中插入逻辑的代码，然后将数据全部插入到新表中，最后我们将新表与旧表的进行swap一下，就将新表扩容指向的内容交换给了临时变量，临时变量调用析构函数，自动释放，这样，扩容问题就得到了解决。
代码如下：
bool Insert(const pair<K, V>& kv)
{
//如果 size==0 或装载因子 >=0.7 进行扩容
if (_table.size() == 0 || 10 * _size / _table.size() >= 7)
{
size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
HashTable<K, V> newHash;
newHash._table.resize(newSize);
//将旧表中的数据拷贝到新表中 --- 复用Insert继续拷贝数据
for (auto e : _table)
{
if (e._state == EXIST)
{
newHash.Insert(e._kv);
}
}
//进行交换 newHash自动调用其析构函数
_table.swap(newHash._table);
}
size_t hashi = kv.first % _table.size();
while (_table[hashi]._state == EXIST) //如果存在数据就一直往后找
{
hashi++;
//如果hashi++超过size()，需要绕回数组的开始
hashi %= _table.size();
}
//找到位置，插入数据
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_size;
return true;
}注意，如果插入的是负数，会发生整形提升，int类型会转变为我们的size_t 类型，此时负数再进行取模，就可以得到一个合法的映射位置，也可以被查找的。
接下来还有一个问题，如果数据发生冗余怎么办。就是如果插入的是已经存在的值，应该如何处理呢？
2.3 Find 查找
所以我们可以在插入之前编写一个find函数，如果该数据存在，则不进行插入。
HashDate<K, V>* Find(const K& key)
{
//判断表为空的情况
if (_table.size() == 0)
return nullptr;
size_t hashi = key % _table.size();
while (_table[hashi]._state != EMPTY)
{
//如果找到key了，并且状态不是DELETE
if (_table[hashi]._kv.first == key && _table[hashi]._state != DELETE)
{
return &_table[hashi];
}
hashi++;
//如果超过表的长度，则除以表的大小，让其回到表头。
hashi %= _table.size();
}
return nullptr;
}此时有一个问题， 我们的循环是_state !=EMPT，如果遍历重回到起点，这些遍历到的数据_state都为EMPTY，就可能导致死循环，所以我们还要保存起始位置的状态，如果重回起点则也返回false(当然，这是一种非常极端的情况，但是会出现)。
2.4 Erase删除
删除的思路非常简单，如果find查找到该值，直接将其对应的state改为DELETE即可。
bool Erase(const K& key)
{
HashDate<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_size;
return true;
}
return false;
}然后我们测试一下这插入、查找、删除这三个接口。
2.5 插入复杂类型
那如果我们想实现一个统计次数的哈希表，则 key 值是string类型的怎么办呢？string类型或字符串类型是无法被取模的。那再如果我们想插入一个自己定义的复杂类型呢？
我们先来看看STL库中是如何解决这个问题的。
所以我们要编写默认的hash取key的仿函数作为缺省参数。
在任何进行取模的地方我们要让key值调用默认的仿函数取出key值。
所以我们可以自定义编写将string类型(或其它复杂类型)转化为 size_t 类型的仿函数
struct HashFuncString
{
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
val += ch;
return val;
}
};然后我们将测试代码跑起来：
void test_hash04_string()
{
string arr[] = { "苹果","西瓜","菠萝","草莓","菠萝","草莓" ,"菠萝","草莓"
, "西瓜", "菠萝", "草莓", "西瓜", "菠萝", "草莓","苹果" };
HashTable<string,int, HashFuncString> countHT;
for (auto& str : arr)
{
auto ptr = countHT.Find(str);
if (ptr)
ptr->_kv.second++;
else
countHT.Insert({ str,1 });
}
countHT.Print();
}
但是在库中的unordered_map并不需要我们自己传入仿函数，因为string是一个挺常见的类型，库中使用了模板的特化，对string类型进行了特殊处理，我们接下来也将其进行改动为特化的形式。
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
val += ch;
return val;
}
};
此时不传入自定义的仿函数，一样可以成功运行：
其实，我们模拟实现的string->int的仿函数写的并不规范，因为key值是唯一的，如果出现以下这种情况，即使key值是不同的，但是通过仿函数计算后的映射却是相同的。比如：
所以，我们要对字符串的Hash函数进行特殊处理，这里有一篇博客进行了详细的讲解：字符串Hash函数对比，这里我就直接使用(BKDR)的规则进行改写了：
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
val = val * 131 + ch;
return val;
}
};
线性探测就实现完了，接下来就是改造为二次探测的实现：
2.6 二次探测
二次探测不是指探测两次，而是 i 的指数方进行探测。
如下是使用线性探测和二次探测插入同一组数据的插入结果，如下：
然后我们在线性探测的方式上进行改动：
三、源代码与测试用例
3.1 hash源代码
enum State { EMPTY, EXIST, DELETE }; //每个位置有三种状态
template<class K, class V>
struct HashDate
{
pair<K, V> _kv;
State _state= EMPTY;
};
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)
{
size_t val = 0;
for (auto ch : key)
val = val * 131 + ch;
return val;
}
};
template<class K, class V,class Hash=HashFunc<K>>
class HashTable
{
public:
bool Insert(const pair<K, V>& kv)
{
//如果表中已经存在该数据
if (Find(kv.first)) return false;
//如果 size==0 或装载因子 >=0.7 进行扩容
if (_table.size() == 0 || 10 * _size / _table.size() >= 7)
{
size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
HashTable<K, V, Hash> newHash;
newHash._table.resize(newSize);
//将旧表中的数据拷贝到新表中 --- 复用Insert继续拷贝数据
for (auto e : _table)
{
if (e._state == EXIST)
{
newHash.Insert(e._kv);
}
}
//进行交换 newHash自动调用其析构函数
_table.swap(newHash._table);
}
Hash hash;
size_t hashi = hash(kv.first) % _table.size();
while (_table[hashi]._state == EXIST) //如果存在数据就一直往后找
{
hashi++;
//如果hashi++超过size()，需要绕回数组的开始
hashi %= _table.size();
}
//找到位置，插入数据
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_size;
return true;
}
HashDate<K,V>* Find(const K& key)
{
//判断表为空的情况
if (_table.size() == 0)
return nullptr;
Hash hash;
size_t hashi = hash(key) % _table.size();
while (_table[hashi]._state != EMPTY)
{
//如果找到key了，并且状态不是DELETE
if (_table[hashi]._kv.first == key && _table[hashi]._state!=DELETE)
{
return &_table[hashi];
}
hashi++;
//如果超过表的长度，则除以表的大小，让其回到表头。
hashi %= _table.size();
}
return nullptr;
}
bool Erase(const K& key)
{
HashDate<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_size;
return true;
}
return false;
}
void Print()
{
for(int i=0;i< _table.size();i++)
{
if (_table[i]._state == EXIST)
cout <<"i:" <<i<<" [" << _table[i]._kv.first << " " << _table[i]._kv.second <<"]" << endl;
}
}
private:
vector<HashDate<K, V>> _table;
size_t _size=0;
};3.2 测试用例
void test_hash01()
{
HashTable<int, int> Hash;
int a[] = { 1,11,4,15,26,7};
for (auto e : a)
{
Hash.Insert(make_pair(e, e));
}
Hash.Print();
cout << endl;
}
void test_hash02()
{
HashTable<int, int> Hash;
int a[] = { 1,11,4,15,26,7,13,5,34,9 };
for (auto e : a)
{
Hash.Insert(make_pair(e, e));
}
Hash.Print();
cout << endl;
}
void test_hash03()
{
HashTable<int, int> Hash;
int a[] = { 1,11,4,15,26,7,13,5,34,9 };
for (auto e : a)
{
Hash.Insert(make_pair(e, e));
}
Hash.Print();
cout << endl<<"find:"<<endl;
cout << (Hash.Find(11)->_kv).first << endl;
cout << (Hash.Find(4)->_kv).first << endl;
cout << (Hash.Find(5)->_kv).first << endl;
cout << (Hash.Find(34)->_kv).first << endl;
cout << "Erase:" << endl;
Hash.Erase(11);
cout << Hash.Find(11) << endl;
}
void test_hash04_string()
{
string arr[] = { "苹果","西瓜","菠萝","草莓","菠萝","草莓" ,"菠萝","草莓"
, "西瓜", "菠萝", "草莓", "西瓜", "菠萝", "草莓","苹果" };
HashTable<string,int> countHT;
for (auto& str : arr)
{
auto ptr = countHT.Find(str);
if (ptr)
ptr->_kv.second++;
else
countHT.Insert({ str,1 });
}
countHT.Print();
}
void test_hash05_string()
{
HashFunc<string> hash;
cout << hash({ "abc" }) << endl;
cout << hash({ "bac" }) << endl;
cout << hash({ "cba" }) << endl;
cout << hash({ "bbb" }) << endl;
}