哈希表与布隆过滤器
哈希操作： 高维空间到低维空间的映射（映射规则自己规定）。 （哈希表的低维数据就是数组下标。）
哈希冲突无法避免因此更加强调处理方法
哈希表的处理方法：
（1）开放定址法。（线性探测法：在已有计算下标情况下，再计算下面的一个下标。）（二次再散列（分别+1^ 2 + 2^2 +2 ^3 +…）使用较多）
（2）再哈希法。(需要设定哈希函数与其他哈希处理方式配合使用兜底)
（3）建立公共溢出区。（建立公共溢出缓冲区（可使用红黑树O(logn)、数组O(n)进行存放））
（4）拉链（链表）法。（将哈希表每个位置当成链表头节点）
创建哈希表（处理冲突的方法：开放地址法）
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
using namespace std;
class HashTable{
public:
HashTable(int n=100):flag(n),data(n),cnt(0){}
//存入操作
void insert(string s){
//第一步：创建hash_func函数 返回ind下标
int ind = hash_func(s)%data.size();//计算哈希值
recalc_ind(ind,s);//冲突处理
//获得合法数组下标
if(flag[ind] == false){
data[ind] = s;
flag[ind]= true;
cnt++;
if(cnt*100>data.size()*75){
expand();//扩容操作
}
}
return ;
}
bool find(string s){
int ind=hash_func(s)%data.size();//计算哈希值
recalc_ind(ind,s);//冲突处理
return flag[ind];
}
private:
int cnt;
vector<string> data;
vector<bool> flag;//用于记录相应位置有没有存数据。防止哈希冲突，大小应与data数组大小一样
void expand(){
int n = data.size()*2;//通常情况下扩大原存储区的两倍
HashTable h(n);
for(int i =0;i<data.size();i++){
if(flag[i]==false) continue;
h.insert(data[i]);
}
*this = h;//新的哈希表赋值给原来的哈希表
return ;
}
//计算哈希值:将任意数据类型转换成整形
int hash_func(string &s){
int seed = 131,hash = 0;//BKDRHash
for(int i =0,s[i];i++){
hash = hash*seed+s[i];
}
return hash & 0x7fffffff;
}
void recalc_ind(int &ind,string &s){
int t =1;//这里t表示当前正在试探第几次
while(flag[ind] && data[ind]!=s){//如果当前位置为1则表示存储了数据&&当前值防止存储两次
//这里使用平方探测法
ind += t*t;
t+=1;
ind %= data.size();//再将ind转化成数组下标
}
return ;
}
};
int main(){
int op;
string s;
while(cin>>op>>s){
switch(op){
case 1:h.insert(s);break;
case 2:cout<<"find"<<s<<":"<<h.find(s)<<endl;break;
}
}
return 0;
}
装填因子：
存储元素个数/哈希总容量 = 0.75（超过0.75需要扩容）函数使用expand()进行扩容 时间复杂度为O(n)
使用建立公共缓冲区的方式处理冲突建立哈希表：
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
using namespace std;
class HashTable{
public:
HashTable(int n=100):flag(n),data(n),cnt(0){}
//存入操作
void insert(string s){
//第一步：创建hash_func函数 返回ind下标
int ind = hash_func(s)%data.size();//计算哈希值
recalc_ind(ind,s);//冲突处理
//获得合法数组下标
if(flag[ind] == false){
data[ind] = s;
flag[ind]= true;
cnt++;
if(cnt*100>data.size()*75){
expand();//扩容操作
}
}else{//如果插入的当前位置存在值则将值放入到公共溢出区
buff.insert(s);
}
return ;
}
bool find(string s){
int ind=hash_func(s)%data.size();//计算哈希值
recalc_ind(ind,s);//冲突处理
if(flag[ind]==false) return false;
if(data[ind] == s) return true;
return buff.find(s) != buff.end();
}
private:
int cnt;
vector<string> data;
vector<bool> flag;//用于记录相应位置有没有存数据。防止哈希冲突，大小应与data数组大小一样
set<string>buff;//公共缓冲区使用set(底层红黑树(O(logn)))实现
void expand(){
int n = data.size()*2;//通常情况下扩大原存储区的两倍
HashTable h(n);
for(int i =0;i<data.size();i++){
if(flag[i]==false) continue;
h.insert(data[i]);
}
//将公共溢出区的元素插入到新的哈希表中
for(auto x:buff){
h.insert(x);
}
*this = h;//新的哈希表赋值给原来的哈希表
return ;
}
//计算哈希值:将任意数据类型转换成整形
int hash_func(string &s){
int seed = 131,hash = 0;//bkdrhash
for(int i =0,s[i];i++){
hash = hash*seed+s[i];
}
return hash & 0x7fffffff;
}
void recalc_ind(int &ind,string &s){
return ;//没有冲突处理，直接return
}
};
int main(){
int op;
string s;
while(cin>>op>>s){
switch(op){
case 1:h.insert(s);break;
case 2:cout<<"find"<<s<<":"<<h.find(s)<<endl;break;
}
}
return 0;
}
使用拉链法处理哈希冲突建立哈希表
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
using namespace std;
class Node{
public:
Node(string data = "",Node = nullptr):data(),next(nullptr){}
string data;
Node *next;
void insert(Node *node){
node ->next = this.next;
this->next = node;
return ;
}
};
class HashTable{
public:
HashTable(int n=100):flag(n),data(n),cnt(0){}
//存入操作
void insert(string s){
//第一步：创建hash_func函数 返回ind下标
int ind = hash_func(s)%data.size();//计算哈希值
recalc_ind(ind,s);//冲突处理
//将当前元素存储到当前链表的中去
Node *p =&data[ind];
while(p->next && p->next->data!=s)p=p->next;
if(p->next == nullptr){
//说明当前插入的数据在当前链表中没有，此时将当前数据插入到整个链表的末尾结点的下一位
p->insert(new Node(s));
cnt+=1;
if(cnt >data.size()*3)//此时装填因子相当于是3的情况，说明在拉链法中每个位置上平均存储数据数量是3个则发生扩容操作。
expend();
}
return ;
}
bool find(string s){
int ind=hash_func(s)%data.size();//计算哈希值
recalc_ind(ind,s);//冲突处理
Node *p = &data[ind].next;//头结点不存储数据所以在头结点的下一位开始查找
while(p&&p->data!=s) p=p->next;
return p!=nullptr;//此时说明p为空 如果p不为空则说明找到了。
}
private:
int cnt;//这里装填因子可以大于1
vector<Node> data;//哈希表每个位置为链表的头结点
void expand(){
int n = data.size()*2;//通常情况下扩大原存储区的两倍
HashTable h(n);
for(int i =0;i<data.size();i++){
//以遍历链表的方式遍历每个位置
Node *p = data[i].next;
while(p){
h.insert(p->data);//当p不为空时将p所存储的数据存储到新的链表中
p= p->next;
}
}
*this = h;//新的哈希表赋值给原来的哈希表
return ;
}
//计算哈希值:将任意数据类型转换成整形
int hash_func(string &s){
int seed = 131,hash = 0;//bkdrhash
for(int i =0,s[i];i++){
hash = hash*seed+s[i];
}
return hash & 0x7fffffff;
}
void recalc_ind(int &ind,string &s){
return ;//没有冲突处理，直接return
}
};
int main(){
int op;
string s;
while(cin>>op>>s){
switch(op){
case 1:h.insert(s);break;
case 2:cout<<"find"<<s<<":"<<h.find(s)<<endl;break;
}
}
return 0;
}
传统哈希表，存储空间与元素数量有关
布隆过滤器，存储空间与元素数量无关
传统的哈希表当涉及庞大数据量时比如爬虫存储url判重时 * 不可行 *
布隆过滤器有一片数据存储区用于存储二进制标记（拥有一组哈希函数当一个数据进函数后映射出二进制数如果有一个哈希函数映射出0则表示数据不存在，如果映射出对应位置都为1也只能表明大概率存在）：用于判断元素是否存在且存在误判率。所以大多用于大数据、信息安全有要求的场景。
leetcode 题目训练
705. 设计哈希集合
class Node{
public:
Node(int key=0,Node *next = nullptr):key(key),next(next){}
int key;
Node *next;
void insert_after(Node *node){
node->next = this->next;
this->next=node;
return;
}
void remove_after(){
if(this->next == nullptr) return ;
Node *p = this->next;
this->next = this->next->next;
delete p;
return ;
}
};
class MyHashSet {
public:
//拉链法
/** Initialize your data structure here. */
vector<Node> data;
MyHashSet():data(100) {}
int hash_func(int key){return key & 0x7fffffff;}
void add(int key) {
if(contains(key))return ;//如果存在当前元素直接return
int ind = hash_func(key)%data.size();//否则通过哈希函数计算key所对应的哈希值再对数组大小取余
data[ind].insert_after(new Node(key));//向哈希表中插入元素的过程
return ;
}
void remove(int key) {
int ind = hash_func(key) % data.size();//寻找移除元素的下标
Node *p = &data[ind];
while(p->next &&p->next->key!=key) p=p->next;
//此时找到了待删除结点的前一个节点
p->remove_after();
return ;
}
/** Returns true if this set contains the specified element */
bool contains(int key) {
int ind = hash_func(key)%data.size();
Node *p = data[ind].next;
while(p&&p->key!=key) p=p->next;
return p!=nullptr;
}
};
- 设计哈希映射
class Node{
public:
Node(int key=0,int value = 0,Node *next=nullptr):value(value),key(key),next(next){}
int key,value;
Node *next;
void insert_after(Node *node){
node->next = this->next;
this->next = node;
return ;
}
void remove_after(){
if(this->next == nullptr) return ;
Node *p = this->next;
this->next = this->next->next;
delete p;
return ;
}
};
class MyHashMap {
public:
//拉链法设计哈希函数
vector<Node>data;
/** Initialize your data structure here. */
MyHashMap():data(100) {}
int hash_func(int key){return key&0x7fffffff;}
/** value will always be non-negative. */
void put(int key, int value) {
int ind = hash_func(key)%data.size();
Node *p = &data[ind];
while(p->next && p->next->key!=key) p=p->next;
//当前存在p->next为空/p->next的key值找到 两种情况
if(p->next){//1.若p->next不为空
p->next->value = value;
}else{//2.若P的next为空则在当前节点后添加一个新的结点存储键值对
p->insert_after(new Node(key,value));
}
return ;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
int ind = hash_func(key)%data.size();
Node *p = data[ind].next;
while(p && p->key !=key) p=p->next;
if(p == nullptr) return -1;
return p->value;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
int ind = hash_func(key)%data.size();
Node *p = &data[ind];
while(p->next&&p->next->key!=key) p=p->next;
p->remove_after();
return ;
}
};
面试题 16.25. LRU 缓存
class Node{
public:
Node(int key =0,int value=0,Node *prev = nullptr,Node *next = nullptr)
:key(key),value(value),prev(prev),next(next){}
int key,value;
Node *next,*prev;//指针域指向前后位置
Node *remove_this(){//将当前节点的前一位指向当前节点的下一位
if(this->prev) this->prev->next = this->next;
if(this->next) this->next->prev = this->prev;
this->next = this->prev = nullptr;//当前位置前后两个指针分别赋值为空
return this;//返回当前节点的地址
}
void insert_prev(Node *node){
node->next = this;
node->prev = this->prev;
if(this->prev) this->prev->next = node;
this->prev = node;
return ;
}
};
class HashList{//使用哈希链表模拟一个队列=>知道队列的头和尾
public:
int capacity;//最大存储元素数量
Node head,tail;//虚拟头和虚拟尾 便于插入和删除
unordered_map<int,Node *>data;//哈希表实现unordered_map（int型到链表结点地址的映射）
HashList(int capacity):capacity(capacity){
head.next =&tail;
tail.prev =&head;
}
void put(int key,int value){//功能：新插入一个结点
if(data.find(key)!=data.end()){//注：find()函数如果未找到则返回end的值
//说明新插入的值原本就存在，首先应该找到当前节点,然后将存在的值从列表中拿出来查到列表的末尾
data[key]->value = value;//先修改值
data[key]->remove_this();//然后再将该节点从整个链表中移出来
}else{
data[key] = new Node(key,value);
}
tail.insert_prev(data[key]);//最后将该节点放到整个链表的末尾
if(data.size()>capacity){//检测是否超出了哈希表的存储空间
data.erase(data.find(head.next->key));//如果超出容量则删除head的后一个结点（哈希表中删除）
delete head.next->remove_this();//再在链表中删除 通过delete将当前节点的空间回收掉
}
return ;
}
int get(int key){//哈希链表中获取结点值
if(data.find(key) == data.end())return -1;
data[key]->remove_this();
tail.insert_prev(data[key]);
return data[key]->value;
}
};
class LRUCache {
public:
HashList h;
LRUCache(int capacity):h(capacity) {}
int get(int key) {
return h.get(key);
}
void put(int key, int value) {
h.put(key,value);
}
};
- TinyURL 的加密与解密
class Solution {
public:
Solution(){srand(time(0));}
char ch(int x){//通过x随机生成大小写字符和'0'-'9' (0-25=a-z;26-51=A-Z;52-61='0'-'9')
x %= 62;
if(x<26) return x+'a';
if(x<52) return x-26+'A';
return x-52+'0';
}
string rand_string(int n){
//随机生成字符串的长度为n
string s="";
for(int i=0;i<n;i++){
s+=ch(rand());
}
return s;
}
unordered_map<string,string> h;//短网址，长网址
// Encodes a URL to a shortened URL.
string encode(string longUrl) {
string s;//没使用过的短网址
do{
s=rand_string(5);
}while(h.find(s)!=h.end());//如果短网址存在过就继续生成
h[s] = longUrl;
return s;
}
// Decodes a shortened URL to its original URL.
string decode(string shortUrl) {
return h[shortUrl];
}
};
- 重复的DNA序列
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
unordered_map<string,int> h;
for(int i=0,I=s.size()-9;i<I;i++){
h[s.substr(i,10)] +=1 ;
}
vector<string> ret;
//扫描哈希表中元素，将值大于1的键存入结果数组ret中
for(auto x:h){
if(x.second == 1) continue;
//此时剩余都是超过一次
ret.push_back(x.first);
}
return ret;
}
};
- 最大单词长度乘积
class Solution {
public:
int maxProduct(vector<string>& words) {
vector<int> mark(words.size());
for(int i=0;i<words.size();i++){
for(auto c:words[i]){
mark[i] |=(1<<(c-'a'));
}
}
int ans = 0;
for(int i=0;i<words.size();i++){
for(int j=i+1;j<words.size();j++){
if(mark[i]&mark[j]) continue;
ans = max(ans,int(words[i].size() *words[j].size()));
}
}
return ans;
}
};
- 搜索二维矩阵 II(两个位置：左下和右上为边界就可以)
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int i=0,j=matrix[0].size()-1;
while(i<matrix.size() && j>=0){
if(matrix[i][j] == target) return true;
if(matrix[i][j] < target)i+=1;
else j-=1;
}
return false;
}
};
- 在二叉树中分配硬币
class Solution {
public:
//硬币移动的总代价
int getResult(TreeNode *root,int &n,int &m){//节点数量n,硬币数量m
n = m =0;
if(root == nullptr) return 0;
n = 1,m = root->val;
int ans=0,n1,m1;
ans += getResult(root->left,n1,m1);
ans += abs(n1-m1);
n += n1,m += m1;
ans += getResult(root->right,n1,m1);
ans += abs(n1-m1);
n += n1,m += m1;
return ans;
}
int distributeCoins(TreeNode* root) {
int n,m;
return getResult(root,n,m);
}
};
- 扁平化多级双向链表
class Solution {
public:
Node* flatten(Node* head) {
Node *p = head,*k,*q;//这里p为原链表结点，k是需要扁平化后的首节点,q为原链表p后面的节点
while(p){
if(p->child){
q=p->next;
k =flatten(p->child);
p->child = nullptr;//扁平化以后，需要将p->child指向空！！！！
p->next = k;
k->prev = p;
while(p->next) p=p->next;//p顺着k的链表一直往后走 走到k的末尾；
p->next = q;
if(q)q->prev = p;
}
p=p->next;
}
return head;
}
};
- 二叉树中所有距离为 K 的结点
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *root,int c,int k,vector<int> &ret){//c为当前所在层号，k和寻找的目标层号
if(k<0) return ;
if(root == nullptr) return ;
if(c == k) {//找到目标层就将该层对应的结点数值传到ret数组中
ret.push_back(root->val);
return ;
}
dfs(root->left,c+1,k,ret);
dfs(root->right,c+1,k,ret);
return ;
}
TreeNode *getResult(TreeNode *root ,TreeNode *target,int &k,vector<int> &ret){//距离为k的结点
if(root == nullptr) return nullptr;
if(root== target){
dfs(root,0,k,ret);//root所在层为第0层
return root;
}
if(getResult(root->left,target,k,ret)){
k-=1;
if(k==0) ret.push_back(root->val);
dfs(root->right,0,k-1,ret);//因为当前节点在左子树中我们需要特殊处理右子树的节点数量
return target;
}else if(getResult(root->right,target,k,ret)){
k-=1;//回溯的过程中k需要先减1
if(k==0) ret.push_back(root->val);
dfs(root->left,0,k-1,ret);
return target;
}
return nullptr;
}
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
vector<int> ret;
getResult(root,target,k,ret);
return ret;
}
};