常见的K-V结构，实现了元素关键码与元素值的映射关系，但没有实现元素关键值与元素存储位置的映射关系，在遍历过程中，一般的顺序表或搜索二叉树要进行关键值的多次比较，其中顺序表的时间复杂度为O(n),二叉搜索树的时间复杂度O(lgn)
对此希望找到一种理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素
常见哈希函数
1. 直接定制法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况
2. 除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
根据待删除元素的关键码，以此函数计算出该元素的存储位置并按此位置进行删除
哈希表结构：在闭散列中，将哈希表底层结构设置为vector容器，容器中每一个元素为一个hashNode结构体，包括kv键值对和状态标志位
初始化将其hashNode的状态设置为空
template <class k,class v>
struct HashNode
{
pair<k, v> kv;
STATE state = EMPTY;
};
template <class k, class v>
class HashTable
{
public:
typedef HashNode<k, v> Node;
HashTable(size_t n = 10)
:HSTable(n)
,_size(0)
{
}
private:
vector<Node> HSTable;
size_t _size;
};
上述插入操作，可能会产生哈希冲突，通过线性探测法，从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，插入一个新元素
在查找过程值，要想找到发生冲突元素，就必须给标志位
删除也类似，采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
enum STATE{
EXIST //已存在
,DELETE //删除过
,EMPTY //空位置
};通过定义一个枚举类型，包括已存在不可插入状态（EXIST），空位置可插入状态(EMPTY)，删除过的位置状态(DELETE)
插入代码如下：
bool insert(const pair<k, v>& kv)
{
checkcapacity();
//计算hash位置
int idx = kv.first%HSTable.size();
//搜索
while (HSTable[idx].state != EMPTY)//其余两种状态都需要继续查找
{
//当前位置已经有数据，且与要插入新数据相同，则插入失败
if (HSTable[idx].state ==EXIST&& kv.first == HSTable[idx].kv.first)
return false;
++idx;
if (idx == HSTable.size() - 1)//向后查找过程到结尾 从头再开始找空位
idx = 0;
}
//此时找到空位置,插入新元素，状态置为已存在，hash表大小+1
HSTable[idx].kv = kv;
HSTable[idx].state = EXIST;
_size++;
return true;
//插满扩容
}由于插入过程实际上是在vector容器基础上完成，如果需要插入元素足够多，可能导致当前所创造的哈希表插满，此时就需要检查容量，进行扩充操作
扩容判断条件是：负载因子>0.7,此时认为产生冲突的可能性大，需要进行扩容
扩容并非在原表基础上增大size，而是开辟新表，将原表已存在状态位置元素进行逐一存放，代码如下：
void checkcapacity()
{
//负载因子控制是否增容
//负载因子越小，冲突越小，但空间浪费越大
if (HSTable.size()==0&&_size * 10 / HSTable.size() > 7)
{
//开新表
int newcap = HSTable.size() == 0 ? 10 : 2 * HSTable.size();
HashTable<k, v> newHST(newcap);
//直接拷贝会导致hash值计算前后不一致
//需要重新计算hash位置
for (int i = 0; i < HSTable.size(); i++)
{
if (HSTable[i].state == EXIST)
{
newHST.insert(HSTable[i].kv);
}
}
swap(newHST);
}
}
void swap(HashTable<k, v>& HT)
{
swap(HSTable,HT.HSTable);
swap(_size, HT._size);
}查找：由于hash冲突，直接通过索引查找难以找到发生hash冲突而通过线性探测法存放的元素，非空位置逐一查找，如果索引超过了表大小，需要循环从头开始
Node* find(const k& key)
{
//计算hash位置
int idx = key%HSTable.size();
//搜索
while (HSTable[idx].state != EMPTY)
{
if (HSTable[idx].state == EXIST && key == HSTable[idx].first)
return &HSTable[idx];
++idx;
if (idx == HSTable.size() - 1)
idx = 0;
}
return nullptr;
}删除：删除并非真删除，释放元素，而是改变对应元素位置状态信息
bool erase(const k& key)
{
Node* node = find(key);
if (node)
{
node->state = DELETE;
_size--;
return true;
}
return false;
}首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
bool insert(const V& val)
{
checkcapacity();
KeyofValue kov;
int idx = kov(val) % _hst.size();
//查找
Node* cur = _hst[idx];
while (cur)
{
if (kov(cur->_val) == kov(val))
{
//key重复
return false;
}
cur = cur->_next;
}
//插入 头插
cur = new Node(val);
cur->_next = _hst[idx];
_hst[idx] = cur;
_size++;
return true;
}
哈希桶通过建立新连接进行扩容操作：
void checkcapacity()
{
if (_size == _hst.size())
{
int newcap = _size == 0 ? 10 : 2 * _size;
vector<Node*> newhst(newcap);
KeyofValue kov;
for (int i = 0; i < _hst.size(); i++)
{
Node* cur = _hst[i];
while (cur)
{
Node* next = cur->_next;
int idx = kov(cur->_val) % newhst.size();
//新表头插
cur->_next = newhst[idx];
newhst[idx] = cur;
cur = next;
}
//原表断开 置空
_hst[i] = nullptr;
}
swap(_hst,newhst);
}
}迭代器的++步骤：
#include<iostream>
#include<vector>
using namespace std;
template <class V>
struct HashNode
{
V _val;
HashNode<V>* _next;
HashNode(const V& val)
:_val(val)
,_next(nullptr)
{
}
};
//hash表的前置声明
template<class K, class V, class KeyofValue>
class HSTable;
//hash表迭代器 封装单链表节点
template<class K, class V, class KeyofValue>
struct HashIterator{
typedef HashNode<V> Node;
typedef HSTable<K, V, KeyofValue> ht;
typedef HashIterator<K, V, KeyofValue> Self;
//成员：节点指针，哈希表指针
Node* _node;
ht* _hptr;
HashIterator(Node* node,ht* hptr)
:_node(node)
,_hptr(hptr)
{
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
//找下一个非空链表头结点
else
{
//计算当前节点在hash表中位置
KeyofValue kov;
int idx = kov(_node->_val) % _hptr->_hst.size();
//从下一位置开始查找
++idx;
for (int; idx < _hptr->_hst.size(); idx++)
{
if (_hptr->_hst[idx])
{
_node = _hptr->_hst[idx];//找到非空链表头结点给node记录
break;
}
}
if (idx = _hptr->_hst.size())//此时走到end位置 将node节点置为空
{
_node = nullptr;
}
}
return *this;
}
};
template<class K,class V,class KeyofValue>
class HSTable
{
public:
typedef HashNode<V> Node;
typedef HashIterator<K, V, KeyofValue> iterator;
//由于迭代器需要访问其私有成员_hst 声明为友元类
friend HashIterator<K, V, KeyofValue>;
HSTable(int n=10)
:_hst(n)
,_size(0)
{
}
iterator begin()
{
for (int i = 0; i < _hst.size(); i++)
{
if (_hst[i])
{
return iterator(_hst[i], this);
}
else
return iterator(nullptr,this);
}
}
iterator end()
{
return iterator(nullptr, this);
}
private:
vector<Node*> _hst;
int _size;
};
位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
比如Tencent的一道面试题：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中
此题解法较多，一般容易想到的就是暴力求解，直接遍历查询，但海量数据导致时间复杂度过大，无法实际中应用；稍微进阶一些的会想到采用二分查找，虽然相比较于直接遍历，把时间复杂度从O(n)提升到O(lgn)，但对于40亿数据还是难以实现
而通过位图可以实现：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：
代码实现如下：
#include<iostream>
#include<vector>
using namespace std;
/*
位图应用：
（1）存放不重复数据简单信息，不需要存放数据本身 优点：节省空间，查找效率高
*/
class bitset
{
public:
//位图内存大小与数据范围有关
bitset(size_t range)
:_bit(range/32+1)
{
}
//存储信息
void set(size_t num)
{
//计算整数位置
int idx = num / 32;
//计算比特位置
int bitidx = num % 32;
//对应比特位置1 按位或运算
_bit[idx] |= (1 << bitidx); //把1向左移动bixidx位置 或运算之后 将其置为1
}
//查找信息
bool test(size_t num)
{
//计算整数位置
int idx = num / 32;
//计算比特位置
int bitidx = num % 32;
//对应比特位右移bitidx后 与1 与运算 如果为1 则为1 否则为0
return (_bit[idx] >> bitidx)&1;
}
//删除信息
void reset(size_t num)
{
//计算整数位置
int idx = num / 32;
//计算比特位置
int bitidx = num % 32;
//对应比特位置10
_bit[idx] &= ~(1 << bitidx);
}
private:
//数组
vector<int> _bit;
//默认bit位个数为 32 位
};布隆过滤器是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
布隆过滤器的实现依然需要借助位图的实现来完成，依然依靠0-1进行标记数据是否存在
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
代码如下：
//布隆过滤器
// 假设布隆过滤器中元素类型为K，每个元素对应3个哈希函数
template<class T, class KToInt1, class KToInt2,class KToInt3>
class BloomFilter
{
public:
BloomFilter(size_t size) // 布隆过滤器中元素个数
: _bmp(3 * size), _bitcount(3 * size)
{}
//存储信息：使用多个bit位存储
void set(const T& val)
{
KToInt1 k1;
KToInt2 k2;
KToInt3 k3;
int idx1 = k1(val) % _bitcount;
int idx2 = k2(val) % _bitcount;
int idx3 = k3(val) % _bitcount;
_bmp.set(idx1);
_bmp.set(idx2);
_bmp.set(idx3);
}
bool test(const T& val)
{
KToInt1 k1;
KToInt2 k2;
KToInt3 k3;
int idx1 = k1(val) % _bitcount;
int idx2 = k2(val) % _bitcount;
int idx3 = k3(val) % _bitcount;
if (!_bmp.test(idx1))
return false;//三个有一个为0 肯定不存在 三个均为1 可能存在（不能说一定存在）
if (!_bmp.test(idx2))
return false;
if (!_bmp.test(idx3))
return false;
if (_bmp.test(idx1) && _bmp.test(idx2) && _bmp.test(idx3))
return true;
}
private:
bitset _bmp;
size_t _bitcount; // bit位的个数
};
struct KToInt1
{
//hash函数计算方式1
};
struct KToInt2
{
//hash函数计算方式2
};
struct KToInt3
{
//hash函数计算方式3
};
void test()
{
BloomFilter<string, KToInt1, KToInt2, KToInt3> bf(10);
}