Cuckoo Hashing
Description
One of the most fundamental data structure problems is the dictionary problem: given a set D of words you want to be able to quickly determine if any given query string q is present in the dictionary D or not. Hashing is a well-known solution for the problem. The idea is to create a function h : Σ* → [0..n-1] from all strings to the integer range 0, 1, .., n-1, i.e. you describe a fast deterministic program which takes a string as input and outputs an integer between 0 and n-1. Next you allocate an empty hash table T of size n and for each word w in D, you set T[h(w)] = w. Thus, given a query string q, you only need to calculate h(q) and see if T[h(q)] equals q, to determine if q is in the dictionary. Seems simple enough, but aren't we forgetting something? Of course, what if two words in D map to the same location in the table? This phenomenon, called collision, happens fairly often (remember the Birthday paradox: in a class of 24 pupils there is more than 50% chance that two of them share birthday). On average you will only be able to put roughly √n-sized dictionaries into the table without getting collisions, quite poor space usage!
A stronger variant is Cuckoo Hashing. The idea is to use two hash functions h1 and h2. Thus each string maps to two positions in the table. A query string q is now handled as follows: you compute both h1(q) and h2(q), and if T[h1(q)] = q, or T[h2(q)] = q, you conclude that q is in D. The name "Cuckoo Hashing" stems from the process of creating the table. Initially you have an empty table. You iterate over the words d in D, and insert them one by one. If T[h1(d)] is free, you set T[h1(d)] = d. Otherwise if T[h2(d)] is free, you set T[h2(d)] = d. If both are occupied however, just like the cuckoo with other birds' eggs, you evict the word r in T[h1(d)] and set T[h1(d)] = d. Next you put r back into the table in its alternative place (and if that entry was already occupied you evict that word and move it to its alternative place, and so on). Of course, we may end up in an infinite loop here, in which case we need to rebuild the table with other choices of hash functions. The good news is that this will not happen with great probability even if D contains up to n/2 words!
Input
On the first line of input is a single positive integer 1 ≤ t ≤ 50 specifying the number of test cases to follow. Each test case begins with two positive integers 1 ≤ m ≤ n ≤ 10000 on a line of itself, m telling the number of words in the dictionary and n the size of the hash table in the test case. Next follow m lines of which the ith describes the ith word di in the dictionary D by two non negative integers h1(di) and h2(di) less than n giving the two hash function values of the word di. The two values may be identical.
Output
For each test case there should be exactly one line of output either containing the string "successful hashing" if it is possible to insert all words in the given order into the table, or the string "rehash necessary" if it is impossible.
Sample Input
2
3 3
0 1
1 2
2 0
5 6
2 3
3 1
1 2
5 1
2 5
Sample Output
successful hashing
rehash necessary
裸2SAT
相同值的位置表示为 !A or !B 即可
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define M 40005
using namespace std;
int all,be[],n,m,x,y;
int dfn[M],low[M],instack[M],belong[M],stack[M],stak,curr,num;
int e[M],ne[M],ee[M];
vector<int> vec[]; void add(int x,int y){
e[all]=y;
ee[all]=x;
ne[all]=be[x];
be[x]=all++;
}
void tarjan(int x){
instack[x]=;
stack[++stak]=x;
dfn[x]=low[x]=++curr;
for(int j=be[x];j!=-;j=ne[j])
if(!dfn[e[j]]){
tarjan(e[j]);
if(low[x]>low[e[j]]) low[x]=low[e[j]];
}else if(instack[e[j]]&&low[x]>low[e[j]])
low[x]=low[e[j]];
if(dfn[x]==low[x]){
int j;
++num;
do{
j=stack[stak--];
instack[j]=;
belong[j]=num;
}while(j!=x);
}
}
int solve(){
curr=stak=num=;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(instack,,sizeof(instack));
for(int i=;i<*n;i++)
if(!dfn[i]) tarjan(i);
bool flag=;
for(int i=;i<n;i++)
if(belong[*i]==belong[*i+]){
flag=;
break;
}
return flag;
}
int main()
{
int tt;
scanf("%d",&tt);
while(tt--)
{
for(int i=; i<=; i++)
vec[i].clear();
all=;
memset(be,-,sizeof(be));
scanf("%d%d",&n,&m);
for(int i=; i<n; i++)
{
scanf("%d%d",&x,&y);
for(vector<int>::iterator it=vec[x].begin(); it!=vec[x].end(); it++)
{
add(*it,*i+);
add(*i,(*it)^);
}
for(vector<int>::iterator it=vec[y].begin(); it!=vec[y].end(); it++)
{
add(*it,*i);
add(*i+,(*it)^);
}
vec[x].push_back(*i);
vec[y].push_back(*i+);
}
// for(int i=0; i<all; i++)
// printf("%d %d\n",ee[i],e[i]);
if(!solve()) printf("successful hashing\n");
else printf("rehash necessary\n");
}
return ;
}
看网上题解也可以用二分图匹配做,顺便写写练手
#include <cstdio>
#include <cstring>
#define M 80005
struct Edge{
int y,ne;
}e[M];
int be[M],pre[M],all,x,y,n,m;
bool vis[M];
void add(int x, int y)
{
e[all].y=y;
e[all].ne=be[x];
be[x]=all++;
}
void init()
{
all=;
memset(be,-,sizeof(be));
memset(pre,-,sizeof(pre));
}
bool dfs(int u)
{
for(int i=be[u]; i!=-; i=e[i].ne)
{
int v=e[i].y;
if(!vis[v])
{
vis[v]=;
if(pre[v]==- || dfs(pre[v]))
{
pre[v]=u;
return ;
}
}
}
return ;
}
int main()
{
int tt;
scanf("%d",&tt);
while(tt--)
{
init();
scanf("%d%d",&n,&m);
for(int i=; i<n; i++)
{
scanf("%d%d",&x,&y);
add(i,x+n);
add(i,y+n);
}
int ans=;
bool flag=;
for(int i=; i<n; i++)
{
memset(vis,,sizeof(vis));
if(!dfs(i))
{
flag=;
break;
}
}
if(flag) printf("successful hashing\n");
else printf("rehash necessary\n");
}
return ;
}
HDU 1672 Cuckoo Hashing的更多相关文章
-
Cuckoo for Hashing(hash)hunnuoj
Problem B:Cuckoo for HashingAn integer hash table is a data structure that supports insert, delete a ...
-
Cuckoo for Hashing_双哈希表
问题 B: Cuckoo for Hashing 时间限制: 1 Sec 内存限制: 64 MB提交: 24 解决: 12[提交][状态][讨论版] 题目描述 An integer hash ta ...
-
Cuckoo hash算法分析——其根本思想和bloom filter一致 增加hash函数来解决碰撞 节省了空间但代价是查找次数增加
基本思想: cuckoo hash是一种解决hash冲突的方法,其目的是使用简单的hash 函数来提高hash table的利用率,同时保证O(1)的查询时间 基本思想是使用2个hash函数来处理碰撞 ...
-
Locality-sensitive hashing Pr[m(Si) = m(Sj )] = E[JSˆ (Si, Sj )] = JS(Si, Sj )
A hash function that maps names to integers from 0 to 15. There is a collision between keys "Jo ...
-
Java数据结构与算法解析(十二)——散列表
散列表概述 散列表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值. 散列表的思路很简单,如果所有的键都是整数,那么就可以使用一个简单 ...
-
《大数据日知录》读书笔记-ch3大数据常用的算法与数据结构
布隆过滤器(bloom filter,BF): 二进制向量数据结构,时空效率很好,尤其是空间效率极高.作用:检测某个元素在某个巨量集合中存在. 构造: 查询: 不会发生漏判(false negativ ...
-
CMU Database Systems - Indexes
这章主要描述索引,即通过什么样的数据结构可以更加快速的查询到数据 介绍Hash Tables,B+tree,SkipList 以及索引的并行访问 Hash Tables hash tables可以实现 ...
-
二. 大数据常用的算法和数据结构 <;<;大数据日知录>;>; 读书笔记
基本上是hash实用的各种举例 布隆过滤器 Bloom Filter 常用来检测某个原色是否是巨量数据集合中的成员,优势是节省空间,不会有漏判(已经存在的数据肯定能够查找到),缺点是有误判(不存在的数 ...
-
Go语言实现布谷鸟过滤器
转载请声明出处哦~,本篇文章发布于luozhiyun的博客:https://www.luozhiyun.com/archives/453 介绍 在我们工作中,如果遇到如网页 URL 去重.垃圾邮件识别 ...
随机推荐
-
关于Ubuntu运行级别、开机启动脚本的说明
关于Ubuntu运行级别.开机启动脚本的说明 目录简介 1.1介绍Ubuntu下面的自启动脚本目录 1.2 Linux操作系统运行级别的概念 1.3关于操作系统自启脚本的启动顺序 1.4 Lin ...
-
Redis教程(六):Sorted-Sets数据类型
转载于:http://www.itxuexiwang.com/a/shujukujishu/redis/2016/0216/133.html 一.概述: Sorted-Sets和Sets类型极为相似, ...
-
hdu 3342 Legal or Not(拓扑排序) HDOJ Monthly Contest – 2010.03.06
一道极其水的拓扑排序……但是我还是要把它发出来,原因很简单,连错12次…… 题意也很裸,前面的废话不用看,直接看输入 输入n, m表示从0到n-1共n个人,有m组关系 截下来m组,每组输入a, b表示 ...
-
JSON 之FastJson解析
http://blog.sina.com.cn/s/blog_7ffb8dd501013qas.html 一.阿里巴巴FastJson是一个Json处理工具包,包括“序列化”和“反序列化”两部分,它具 ...
-
AsyncTask简单入门
关系: java.lang.Object ↳ android.os.AsyncTask<Params, Progress, Result> 概述: AsyncTask是Andr ...
-
VHD进阶:差分VHD备份系统
VHD进阶:差分VHD备份系统 一.创建虚拟磁盘 方法1:图形界面创建 1.打开磁盘管理器(运行diskmgmt.msc),在“磁盘管理”上点击右键,“创建VHD”,类型选择VHD,动态扩展或者固定大 ...
-
Python tutorial阅读之Python基本运算与基本变量
将 Python 当做计算器 除法运算 用/表示除法运算时,一般得到的是浮点数,如果我们需要得到整数,可以用运算符// 余数计算 % 幂乘方 系统内置变量_ 内置变量_,存储了最近的结果.如图 字符串 ...
-
centos7.4下离线安装CDH5.7
(一)安装前的规划 (1)操作系统版本:centos7.4(64bit) [root@hadoop22 etc]# more /etc/centos-release CentOS Linux rele ...
-
centos7下kubernetes(4.kubernetes组件)
Kubenetes cluster 由master和node组成 Master是kubenetes的大脑.运行着以下进程:kube-apiserver.kube-scheduler.kube-cont ...
-
[3] TensorFlow 深层神经网络
深层神经网络简称为深度学习有两个非常重要的特性1. 多层2. 非线性 线性模型的局限性 :例如前面的神经网络有两层(不算输入层),但是它和单层的神经网络井没有区别,任意线性模型的组合仍然还是线性模型, ...