C++进阶——哈希
1.哈希的概念以及介绍
哈希结构是一种可以不经过任何比较，一次直接从表中得到要搜索的元素的数据结构。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立
一一映射关系，那么在查找时通过该函数可以很快找到该元素。
通过哈希构造的方式称为为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)或散列表。
2.哈希表
哈希表（Hash Table）是一种基于哈希函数实现的数据结构，可以以平均常数时间复杂度（O(1)）进行数据的插入、删除和查找操作，十分的高效。哈希表通过将键值（key）映射到哈希值（hash value），然后将这些值存储在一个数组中，使得可以快速访问对应的值（value）。
2.1哈希函数
哈希表通过哈希函数构造出哈希表，而哈希函数的设置则至关重要。
哈希函数设计原则
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果哈希表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
下面两种哈希函数是较为常用的哈希函数。
直接定址法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址，通过数据的模取得到余数确定数据存储的地址，进而将数据映射存储到对应的哈希地址上。
关于除留余数法的哈希函数，例子如下：
2.2 哈希冲突
哈希冲突发生在不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突
或哈希碰撞。
哈希函数的设置不合理容易导致哈希冲突发生的概率增大，相反，如果哈希函数的设置越合理则发生哈希冲突的概率会越低。哈希冲突的发生会降低哈希结构对数据操作的效率，但是哈希冲突并不能被避免，只能减少其发生的可能性。
例如当插入数据11时，通过哈希函数得到的数据映射哈希地址为1，与数据1的存储地址相同，发生哈希冲突。
2.21负载因子
在哈希冲突中有一个十分重要的存在——负载因子
负载因子大小 = 储存数据个数 / 容量大小，负载因子的大小影响着发生哈希冲突的可能性
当负载因子过大时，哈希表中的空余位置少，容易发生哈希冲突，当负载因子较小时，此时哈希表中空余位置较多，不易引发哈希冲突。负载因子大小的控制是十分重要的，当负载因子过大时，哈希表的储存容量需要及时扩大，以减少哈希冲突的发生率。
负载因子的大小一般控制在0.7左右会比较好，当负载因子大于这个数再对哈希表进行增容，这样既能降低哈希冲突的发生率，也能不浪费储存的空间。
2.3哈希冲突的解决
解决哈希冲突的两种常见方法为：开散列、闭散列。
2.31闭散列
闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中还有空位置可以放入数据，可以把key存放到冲突位置中的 “下一个” 空位置中去。对于寻找冲突位的下一个空位有不同的方法。
1.线性探测
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
- 插入
通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，
使用线性探测找到下一个空位置，插入新元素
- 删除
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素
会影响其他元素的搜索，因此线性探测会采用标记的伪删除法来删除一个元素。
线性探测的实现
enum State//记录各个位置存储数据的状态
{
EMPTY,
EXIT,
DELETE,
};
template<class T>
struct HashData
{
T _data;
State _state;
};
template<class T>
class HashTable
{
typedef HashData<T> HashData;
private:
vector<HashData> _tables;
size_t _num = 0;//数据个数
public:
bool insert(const T& d)
{
if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7)
//负载因子过大扩容，避免效率低下
{
int newSize = (_tables.size() == 0 ? 10 : _tables.size() * 2);
vector<HashData> newTables;
newTables.resize(newSize);
//预先开辟空间+数据初始化使得size（）为当前空间可存储数据个数
for (int i = 0; i < _tables.size(); ++i)
{
if (_tables[i]._state == EXIT)
{
size_t index = _tables[i]._data % newTables.size();
while (newTables[index]._state == EXIT)
{
index++;
if (index = _tables.size())
{
index = 0;
}
}
newTables[index] = _tables[i];
}
}
_tables.swap(newTables);//交换存储地址，变量newTables出作用域后被销毁
}
size_t index = d % _tables.size();//
while (_tables[index]._state == EXIT)//查找插入位置
{
if (_tables[index]._data == d)//数据重复，插入失败
{
return false;
}
index++;
if (index == _tables.size())//后面找完了，往前找
{
index = 0;
}
}
_tables[index]._data = d;
_tables[index]._state = EXIT;
_num++;
return true;
}
HashData* find(const T& d)
{
size_t index = d % _tables.size();
while (_tables[index]._state != EMPTY)//不为空往后找
{
if (d == _tables[index]._data)//找到相同数据
{
if (_tables[index]._state == DELETE)//数据不存在
{
return nullptr;
}
else//找到了
{
return &_tables[index];
}
}
if (index == _tables.size())//后面找完了，往前找
{
index = 0;
}
index++;
}
return nullptr;
}
bool erase(const T& d)
{
HashData* ret = find(d);
if (ret == nullptr)
{
return false;
}
else
{
ret->_state = DELETE;
_num--;
return true;
}
}
};
2.二次探测
对于线性探测，其缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，二次探测采取了每次探测步长为探测次数的平方大小，每当探测哈希表的空置发生冲突后，下次的探测步长将会变大。也就是说，第一次探测步长为1^2，第二次为2^2,第n次为n^2。
2.32开散列
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同哈希地
址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链
接起来，各链表的头结点存储在哈希表中。
开散列的实现
开散列的实现与闭散列的实现大致思路是相同的，同样需要控制负载因子大小，通过除留余数法计算各个数据的哈希地址，映射到对应的位置上，不同的是，开散列的循序表中存放的是各个单列表的头节点。
template <class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
template<class T>
class HashTable
{
typedef HashNode<T> Node;
private:
vector<Node*> _tables;
size_t _num = 0;
public:
bool insert(const T& data)
{
//负载因子等于1时增容，避免大量哈希冲突导致效率低下
if (_num == _tables.size())
{
vector<Node*> newTables;
size_t newSize = (_tables.size() == 0 ? 10 : _tables.size() * 2);
newTables.resize(newSize);
for (int i = 0; i < _tables.size(); i++)//将旧表数据插入映射到新表中去
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = data % newTables.size();
//头插
cur->_next = newTables[index];
newTables[index] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t index = data % _tables.size();
Node* cur = _tables[index];
while (cur)//先遍历找是否有重复数据
{
if (cur->_data == data)//数据重复
{
return false;
}
else
{
cur = cur->_next;
}
}
Node* newNode = new Node(data);
//头插
newNode->_next = _tables[index];
_tables[index] = newNode;
_num++;
return true;
}
Node* find(const T& data)
{
size_t index = data % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (cur->_data == data)
{
return cur;
}
else
{
cur->_next;
}
}
return nullptr;
}
bool erase(const T& data)
{
size_t index = data % _tables.size();
Node* cur = _tables[index];
Node* curPrev = nullptr;
while (cur)
{
if (data == cur->_data)
{
if (curPrev == nullptr)
{
_tables[index] = cur->_next;
}
else
{
curPrev->_next = cur->_next;
}
delete cur;
}
else
{
curPrev = cur;
cur = cur->_next;
}
}
}2.4开散列与闭散列的异同
结构：
两者的哈希表都是循序表的结构
但闭散列的哈希表中每个位置单独存放一个数据，而开散列的哈希表中每个位置存放的是单链表的头节点，用于链接哈希地址相同的数据。
插入数据：
两者都是通过哈希函数确定各个数据的哈希地址将数据映射到对应位置上
但闭散列的数据插入是每个数据单独占有一个位置，且各个位置上存储着当前数据的状态，发生哈希冲突需要在哈希表上寻找空余位置插入，而开散列的数据插入，会将所有哈希地址相同的数据用一个单链表连接起来，发生哈希冲突需要在当前单链表寻找插入位置。
删除数据：
闭散列的数据删除不能直接物理上的删除，需要使用标记状态的假删除，否则会影响到其他数据，开散列的数据删除可以直接使用物理上的空间删除，并不会影响到其他数据。
2.5开散列与闭散列
应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。
事实上：
由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <=
0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。
3.哈希的应用
哈希中有两个十分重要的应用，分别是位图、布隆过滤器，用于处理海量数据的处理。
3.1位图
3.11位图的概念
率位图，就是用每一个比特位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。由于位图对于每位空间的利用，位图能极大提高对内存空间的利用，在处理海量数据的时候可以有效减少使用的储存空间。
3.12位图的实现
class _bitset
{
private:
vector<int> _bits;
size_t _num;//映射存储的数据个数
public:
bitset(size_t N)
:_num(0)
{
_bits.resize(N / 32 + 1, 0);//开辟位个数空间
}
void set(size_t x)
{
int index = x / 32; //确定为第几个整型
int pos = x % 32; //确定为第几个比特位
_bits[index] |= (1 << pos);//将对应位数据改为1
++_num;
}
void reset(size_t x)
{
int index = x / 32;
int pos = x % 32;
_bits[index] &= ~(1 << pos);//将对应位数据改为0
--_num;
}
bool test(size_t x)//检查数据是否存在
{
int index = x / 32;
int pos = x % 32;
int ret = (_bits[index] & (1 << pos)) >> pos;//确定对应比特位数据是否为1
if (ret == 1)
{
return true;
}
else
{
return false;
}
}
};上述位图的实现对于整形数据，将每个整型，即4个字节，32个比特位的空间，使用位操作符可以更改每个比特位的数据，用于存储不同数据的状态，用1表示数据存在，0表示不存在。
位图常常用于：在海量数据中检测某个数据是否存在其中，数据的去重，两数据的交并集合等，都可以通过位图来完成。
例如下列一个简单的例子，对于在存放100个数据的位图，将1至100的奇数存放在位表中，通过遍历可得知每个数据其是否存在。
int main()
{
_bitset bs(100);
for (int i = 1; i < 100; i += 2)
{
bs.set(i);
}
for (int i = 0; i < 100; i++)
{
printf("[%d]:%d ", i, bs.test(i));
}
}
位图作为哈希的一种应用，不但能够减少内存空间的使用，其效率也十分高效，在对于海量数据的问题十分有效。
例如：查找40亿个不重复的数据中某个数据是否存在。这种海量数据情况使用红黑树去解决行不通，对于40亿个整型数据，每个4字节的空间，共计160亿字节，也就是需要16G左右的空间，这种情况下，内存空间是不够的，而如果采用位表来实现查找，我们可以利用每个比特位的空间，40个数据，需要40个比特位的空间，也就是 ：40/ 8 = 5亿字节，500M左右的空间即可解决海量数据的问题。
3.2布隆过滤器
3.21布隆过滤器的概念
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概
率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存
在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也
可以节省大量的内存空间。
3.22布隆过滤器的实现
布隆过滤器的实现是通过位图和结合哈希函数取得对应映射值来实现的，且利用了仿函数。
struct HashStr1
{
size_t operator()(const string & str)
{
size_t hash = 0;
for (size_t i = 0; i < str.size(); i++)
{
hash *= 131;
hash += str[i];
}
return hash;
}
};
struct HashStr2
{
size_t operator()(const string& str)
{
size_t hash = 0;
size_t magic = 63689;
for (size_t i = 0; i < str.size(); i++)
{
hash *= magic;
hash += str[i];
magic *= 378551;
}
return hash;
}
};
struct HashStr3
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (size_t i = 0; i < str.size(); i++)
{
hash *= 65599;
hash += str[i];
}
return hash;
}
};template<class K = string,class Hash1 = HashStr1,
class Hash2 = HashStr2,class Hash3 = HashStr3>
class bloomfilter
{
private:
_bitset _bs;
size_t _N;//空间大小
public:
bloomfilter(size_t num)
:_bs(5*num)
,_N(5*num)
{}
void set(const K& key)
{
size_t index1 = Hash1()(key) % _N;//Hash1()为匿名对象
size_t index2 = Hash2()(key) % _N;
size_t index3 = Hash3()(key) % _N;
_bs.set(index1);
_bs.set(index2);
_bs.set(index3);
}
bool test(const K& key)
{
size_t index1 = Hash1()(key) % _N;
if (_bs.test(index1) == false)
return false;
size_t index2 = Hash2()(key) % _N;
if (_bs.test(index2) == false)
return false;
size_t index3 = Hash3()(key) % _N;
if (_bs.test(index3) == false)
return false;
return true;
}
};1.布隆过滤器的数据插入
由于单次映射发生冲突的概率很大，所以布隆过滤器常常会使用多次映射来减少冲突的发生。映射对应的比特位的值改为1表示产生映射，0,表示不存在映射。将数据插入时会将所有映射的对应哈希地址的比特位的值改为1。
2.布隆过滤器的数据删除
布隆过滤器的使用常常会映射多个哈希地址，而不同的哈希地址可能被多次映射，所以布隆过滤器一般是不能进行数据的删除，一旦删除数据就可能会改变其他数据的映射情况。
3.布隆过滤器的数据查找
布隆过滤器查找数据会分别计算每个哈希值对应的比特位置存储的是否为0，只要有一个为0，就代表该元素一定不在哈希表中，否则可能在哈希表中。
布隆过滤器对于判断某一数据是否存在其中不一定是准确的，而判断某一数据不存在其中一定是准确的。这同样是因为，多映射的关系，由于其他数据的多次映射可能会与判断存在数据的映射哈希地址想同，导致会误判，对于判断数据不存在其中则是准确的，只有数据不存在其中时，对应哈希地址映射的比特位的值才会都会0。
3.23布隆过滤器的优缺点
优点
- 增加和查询元素的效率非常高，时间复杂度为:O(K) (K为哈希函数的个数)。
- 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势。
- 相比其他数据结构有着很大的空间优势，处理相同数据需要的空间少很多。
- 使用同一组散列函数的布隆过滤器可以进行交、并、差运算。
缺点
- 通过映射的方式存入数据，映射有冲突性，具有误判率，不能准确判断元素是否在集合中。
- 不能获元素本身。
- 一般情况下不能从布隆过滤器中删除元素。
原文地址：https://blog.csdn.net/Bit_qnw/article/details/142764200
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！