文章目录
1.哈希中的基本概念
哈希函数
之前的二叉搜索树与红黑树以及顺序结构他们的关键字和它的储存位置没有对应关系，所以在查找一个元素时要经过多次的关键字比较。
顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN )，搜索的效率取决于搜索过程中元素的比较次数。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以不经过任何比较，一次直接从表中得到要搜索的元素。
向该结构中插入数据时
根据待插入元素的关键字，以哈希函数计算出该元素的存储位置并按此位置进行存放
向该结构搜索数据时
利用哈希函数对元素的关键字进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键字相等则搜索成功
常见的哈希函数与缺陷
常见的哈希函数有：
- 直接定址法
- 除留余数法
缺陷：
直接定址法：1.如果数据范围很大，直接定址法会浪费很多空间。
2.不能处理浮点数和字符串等数据
除留余数法：
缺陷：1.不同的数值可能映射到同一个位置。
哈希表
上述过程就是哈希方法，在哈希方法中使用的将关键字与数据储存建立起联系的函数为哈希函数，构造出的数组称为哈希表
2.哈希冲突
不同的数值可能映射到同一个位置。这种现象称为哈希冲突
哈希冲突的解决方法(闭散列与开散列)
闭散列(开放地址法)
闭散列解决哈希冲突有两种方法
- 线性探测法
- 二次探测法
线性探测法：
查找的时候先按照哈希函数计算映射位置。如果不是这个数字，还要依次向下一个位置继续查找。
注意： 当线性探测数组没有空位时，要对数组进行增容
线性探测的缺陷
线性探测会导致”踩踏效应“，某个位置出现冲突时，可能导致其他数据冲突
二次探测：
如果超过了数组大小则类似循环队列一样，又回到了数组前面。
二次探测相比于线性探测减少了踩踏现象
负载因子
负载因子=已经储存的数据个数/空间大小。
负载因子越大，冲突的概率越大，增删查改的效率越低，空间利用率低。反之
在闭散列中负载因子最大为1
在闭散列中负载因子一般设置为0.7.也就是数据占了空间的70%就要增容，否则哈希冲突太多，效率收到影响
C++实现除留余数法闭散列线性探测哈希表(Key_Value模型)
注意：
1.为了方便删除数组中的数据和标记位置为空，选择添加状态枚举标记每个元素的状态，删除某个元素即把这歌元素的状态设置为删除即可。这个位置为空就将这个位置的状态设置为空状态
2.针对字符串类型无法进行整形运算，这里选择添加仿函数，用户可以自己定义类型转化为关键字的方法
3.因为实现哈希表选择C++STL中的vector和pair实现，所以不需要写析构函数，系统会自动调用vector和pair的析构函数
Hash_Table.h
#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace CloseHash//闭散列哈希
{
enum State{EMPTY,EXITS,DELETE};//状态枚举
template<class Key,class Value>
struct HashDate
{
HashDate() :_state(EMPTY) {}
pair<Key, Value>_kv;
State _state;
};
template<class Key>
struct HashKey//默认仿函数
{
int operator()(const Key _Key) { return _Key; }
};
//string特化,针对字符串类型选择字符串中所有字符的ASCLL码值作为关键字
template<>struct HashKey<string>
{
int operator()(const string& Str)
{
int Sum = 0;
for (int i = 0; i < Str.size(); i++)
{
Sum += Str[i];
}
return Sum;
}
};
template<class Key, class Value, class HashFuc = HashKey<Key>>
class HashTable
{
typedef HashDate<Key, Value> HashDate;
public:
HashTable() :_size(0) { _Table.resize(10); }
bool Insert(const pair<Key, Value>& kv)
{
HashFuc kot;
if (Find(kv.first)) { return false; }//不允许冗余
//计算负载因子>0.7增加哈希结构大小
if ((double)_size / (double)_Table.size() > 0.7)
{
//增容，复用原函数，最后将数组交换
HashTable<Key, Value, HashFuc> NewTable;
NewTable._Table.resize(_Table.size() * 2);
for (const auto& Date : _Table)
{
NewTable.Insert(Date._kv);
}
_Table.swap(NewTable._Table);
}
size_t Pos = kot(kv.first) % _Table.size();
while (_Table[Pos]._state == EXITS)//线性探测
{
Pos++;
Pos %= _Table.size();
}
_Table[Pos]._kv = kv;
_Table[Pos]._state = EXITS;
++_size;
return true;
}
HashDate* Find(const Key& key)
{
HashFuc kot;
size_t Pos = kot(key) % _Table.size();
while (_Table[Pos]._state != EMPTY)
{
if (_Table[Pos]._state != DELETE && _Table[Pos]._kv.first == key)//找到了
{
return &_Table[Pos];
}
++Pos;
Pos %= _Table.size();
}
return nullptr;
}
bool Erase(const Key& key)
{
HashDate* Pos = Find(key);
bool IsErase = false;
if (nullptr == Pos)
{
cout << "不存在的值" << endl;
}
else
{
Pos->_state = DELETE;
IsErase = true;
}
--_size;
return IsErase;
}
void PrintHashTable()//测试接口
{
for (size_t i = 0; i < _Table.size(); i++)
{
if (_Table[i]._state == EXITS)
{
cout << _Table[i]._kv.first << "->" << _Table[i]._kv.second << " ";
}
}
cout << endl;
}
private:
vector<HashDate>_Table;
size_t _size;//存放有效数据的个数
};
}
Test_Hash_Table.cpp
#include"Hash_Table.h"
void Test()//测试插入/删除/查找/打印接口
{
CloseHash::HashTable<int, int>Table;
vector<int>ret = { 1,2,100,20,4,44 };
Table.Erase(10);
for (const auto s : ret)
{
Table.Insert(make_pair(s, s));
}
Table.PrintHashTable();
for (size_t i = 0; i < ret.size(); i++)
{
if (Table.Find(ret[i]))
{
Table.Erase(ret[i]);
Table.PrintHashTable();
}
}
}
//针对字符串类型
//方法一：自定义仿函数
//方法二：偏特化默认仿函数
//struct StrHashKey
//{
// int operator()(const string& Str)
// {
// int Sum = 0;
// for (int i = 0; i < Str.size(); i++)
// {
// Sum += Str[i];
// }
// return Sum;
// }
//};
void Test2()//测试字符串类型
{
//统计次数
vector<string>Array = { "苹果","香蕉","西瓜","香蕉", "香蕉","西瓜","西瓜","苹果" };
//CloseSpace::HashTable<string, int,StrHashKey>Hash;
CloseHash::HashTable<string, int>Hash;
for (int i = 0; i < Array.size(); i++)
{
CloseHash::HashDate<string,int>*Pos=Hash.Find(Array[i]);
if (Pos == nullptr)
{
Hash.Insert(make_pair(Array[i], 1));
}
else
{
Pos->_kv.second++;
}
}
Hash.PrintHashTable();
}
int main()
{
Test();
Test2();
return 0;
}
运行结果：
开散列(哈希桶/拉链法)
首先对关键字集合用散列函数计算散列地址，具有相同地址的关键字归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
开散列一般负载因子为1时增容。相比于闭散列来讲，有效的避免了哈希冲突的踩踏现象，同时空间利用率高
C++实现除留余数法开散列哈希桶(Key_Value模型)
注意：
1.与闭散列注意点相同，要用状态标记数据的状态
2.针对字符串类型还要进行模板特化处理
3.开散列增容时不选择闭散列那样的定义新的对象复用函数。因为开散列每个位置是链表，如果在定义新对象意味着开辟新的链表节点，如果复用之前的函数就会出现释放之前旧节点，创建新节点的性能损失。
所以在开散列扩容选择：开辟新数组重新计算映射关系然后移动旧节点到新数组，最后交换数组的方法
4.HashDate中有自定义的元素指针，所以默认的析构函数不能使用，拷贝构造以及赋值运算符重载会导致浅拷贝问题
OpenHashTable.h
#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace OpenHash
{
template<class Key,class Value>
struct HashDate
{
HashDate<Key, Value>* _next;
pair<Key, Value>_kv;
HashDate(const pair<Key, Value>& Date) :_next(nullptr), _kv(Date) {}
};
//默认仿函数
template<class Key>
struct HashKey
{
int operator()(const Key& key) { return key; }
};
//特化字符串
template<>struct HashKey<string>
{
int operator()(const string& Str)
{
int Sum = 0;
for (int i = 0; i < Str.size(); i++)
{
Sum += ((i + 1) * Str[i]);//尽量避免冲突
}
return Sum;
}
};
template<class Key, class Value,class HashFuc=HashKey<Key>>
class Hash
{
typedef HashDate<Key, Value> HashDate;
public:
Hash() :_size(0) { _Table.resize(4); }
~Hash()//析构
{
for (size_t i = 0; i < _Table.size(); i++)
{
HashDate* cur = _Table[i];
if (cur != nullptr)
{
HashDate* next = cur->_next;
delete cur;
cur = next;
}
_Table[i] = nullptr;
}
}
Hash(const Hash<Key, Value, HashFuc>& dev)//拷贝构造函数
{
_size = dev._size;
_Table.resize(dev._Table.size());
for (size_t i = 0; i < dev._Table.size(); i++)
{
HashDate* cur = dev._Table[i];
while (cur != nullptr)
{
HashDate* copy = new HashDate(cur->_kv);
copy->_next = _Table[i];
_Table[i] = copy;
cur = cur->_next;
}
}
}
Hash& operator=(Hash<Key, Value, HashFuc> dev)//传值法,将传入值的拷贝于原来对象的元素交换
{
_Table.swap(dev._Table);
std::swap(_size, dev._size);
return *this;
}
bool Insert(const pair<Key, Value>& Date)
{
HashFuc kot;
if (Find(Date.first)) { return false; }//不允许冗余
if (_size == _Table.size())//负载因子太大扩容
{
vector<HashDate*>NewVector;
NewVector.resize(_Table.size() * 2);
//遍历原数组
for (int i = 0; i < _Table.size(); i++)
{
HashDate* cur = _Table[i];
while (cur != nullptr)//重新计算每个旧节点的映射关系，头插到新表中
{
HashDate* next = cur->_next;
size_t idex = kot(cur->_kv.first) % NewVector.size();
cur->_next = NewVector[idex];
NewVector[idex] = cur;
cur = next;
}
}
_Table.swap(NewVector);
}
size_t Pos = kot(Date.first) % _Table.size();
HashDate* cur = new HashDate(Date);//头插
cur->_next = _Table[Pos];
_Table[Pos] = cur;
++_size;
return true;
}
HashDate* Find(const Key& key)
{
HashFuc kot;
size_t Pos = kot(key) % _Table.size();
HashDate* cur = _Table[Pos];
while (cur != nullptr)
{
if (cur->_kv.first == key)
{
break;
}
cur = cur->_next;
}
return cur;
}
bool Erase(const Key& key)
{
HashFuc kot;
size_t Pos = kot(key) % _Table.size();
HashDate* cur = _Table[Pos];
HashDate* bef = nullptr;
while (cur->_kv.first != key)
{
bef = cur;
cur = cur->_next;
}
if(cur!=nullptr)
{
if (bef == nullptr) {//删除第一个节点
_Table[Pos] = cur->_next;
}
else {
bef->_next = cur->_next;
}
delete cur;
--_size;
return true;
}
else
{
cout << "无此元素" << endl;
return false;
}
}
void PrintHashTable()//测试用接口
{
for (int i = 0; i < _Table.size(); i++)
{
if (_Table[i] == nullptr)
{
cout << "nullptr" << " ";
}
else
{
HashDate* cur = _Table[i];
while (cur != nullptr)
{
cout << cur->_kv.first << "->" << cur->_kv.second << " ";
cur = cur->_next;
}
}
}
cout << endl;
}
private:
vector<HashDate*>_Table;
size_t _size;
};
}
OpenHashTable.cpp
#include"OpenHashTable.h"
void Test1()//测试插入/查找/删除/打印接口
{
OpenHash::Hash<int, int>Table;
vector<int>ret = { 1,2,100,20,4,44 };
for (int i = 0; i < ret.size(); i++)
{
Table.Insert(make_pair(ret[i], i));
}
Table.PrintHashTable();
for (const auto& e : ret)
{
if (Table.Find(e))
{
Table.Erase(e);
Table.PrintHashTable();
}
}
}
void Test2()//测试字符串类型
{
//统计次数
vector<string>Array = { "苹果","香蕉","西瓜","香蕉", "香蕉","西瓜","西瓜","苹果" };
OpenHash::Hash<string, int>Hash;
for (int i = 0; i < Array.size(); i++)
{
OpenHash::HashDate<string, int>* Pos = Hash.Find(Array[i]);
if (Pos == nullptr)
{
Hash.Insert(make_pair(Array[i], 1));
}
else
{
Pos->_kv.second++;
}
}
OpenHash::Hash<string, int>Copy(Hash);
OpenHash::Hash<string, int>Copy2 = Copy;
Hash.PrintHashTable();
Copy.PrintHashTable();
Copy2.PrintHashTable();
}
int main()
{
//Test1();
Test2();
return 0;
}
运行结果：
注意：极端情况下当所有的数据都冲突的时候，此时查找的时间复杂度为O(N)于顺序表相同。为了解决这种情况，可以将每个桶的结构由单链表的形式改成红黑树或AVL树提高查找效率