hash算法一直被我认为成一种处理大数据量的高效算法(时间复杂度)。
从一道百度面试题开始。
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
好。首先想暴力解决下，看看内存够不够。大约255X10^8B内存，2.4G的样子。。超内存了。。汗。。300万，那就是0.8G，刚刚好。很自然的，我们可以想到，如果每次向内存读一个字符串，然后把那个字符串出现的次数和字符串存起来，这样，就可以在不超过1G的情况下搞定。编程珠玑上面有这道题目的int版本，大概就是问10亿个整数（从1到10亿，缺一个），不超过多少内存，要求最快找出缺少的数。那个题目也是利用hash的思想，不过它的hash函数就是它自己就是了。开一个10亿比特的内存，然后把flag[num]设置一下，最后再统计一下。好吧，这个题目是不是可以利用类似的思想呢？好吧，hash吧。
hash算法的基本步骤是：把数据存放到key(data[i])里面。如此简单。就是建立data[i]和i的映射关系，然后利用数组可以随机访问的特点，使得在O(1)的时间复杂度再次找到数据(理想情况，可能冲突)！hash最直接的利用就是lookup table,查找表。建立一个hash表，然后可以进行快速查找。（如果出现访问冲突怎么办呢？大致分为两种办法：开散列和闭散列。开散列就是找到了这个位置被别人占了，好，找个规则换地方。闭散列就是这个地方被别人站着，我跟在他后面(链表)。高深的玩意研究不懂，MARK之，以后慢慢看）。
hash解决此题：网上找一个字符串hash函数看看先(看不懂，直接用。哪位大神可以告诉我为什么或者详细资料??)。建立一个空的hash表，每次读一个字符串。找到这个字符串的key（就是用hash函数对它XXX）,返回一个位置。看看那个位置是不是被别人占了。如果被别人占了，我就往后走，直到找到一个空位子。坐下。当然这个过程也许会找到和自己一样的，那样就把它的访问次数+1。好了，hash表建好了，里面有300万个字符串，每一个字符串的搜索次数也统计出来了。
问题完成了第一步。
第二部是，统计TOP K字符串。这个。。可以排个序，qsort,O(N*logN),太挫了。果断用个小顶堆，把复杂度降到O(N*log(K))，K 很小，这个很划算啊。
关于堆的问题就不详细阐述了，实现简单(siftdown(int),siftup(int))，目的明确(取最值，增加删除元素)。下面是测试的代码。当然我没有那么大的数据量，写的代码也仅供测试之用。
#include <stdio.h>
#include <string.h>
#define MAXN 47
#define NUM 10
typedef struct
{
char str[256];
int time;
}node;
node data[MAXN];
node heap[NUM];//小顶堆
int hcount = 0;
void swap(node& a,node& b)
{
node tmp;
tmp = a;
a = b;
b = tmp;
}
void siftdown(int i)
{
int minst = i;
if(2*i<=hcount&&heap[i].time>heap[2*i].time)
minst = 2*i;
if(2*i+1<=hcount&&heap[minst].time>heap[2*i+1].time)
minst = 2*i+1;
swap(heap[i],heap[minst]);
if(i!=minst)
{
siftdown(minst);
}
}
void siftup(int i)
{
while(heap[i].time<heap[i/2].time)
{
swap(heap[i],heap[i/2]);
siftup(i);
}
}
void pop()
{
if(hcount<=0)
return;
swap(heap[1],heap[hcount]);
hcount--;
siftdown(1);
}
void add(node n)
{
if(hcount<NUM)
{
data[hcount++] = n;
siftup(hcount);
return;
}
if(heap[0].time<n.time)
{
pop();
data[hcount++] = n;
siftup(hcount);
return;
}
}
int strhash(char* str)
{
//BKDRHash
int seed = 131;
int hash = 0;
while(*str)
{
hash = hash *seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}
void init()
{
int i;
for(i=0;i<MAXN;i++)
data[i].time=-1;
}
void solve()
{
int i;
for(i=0;i<MAXN;i++)
{
if(data[i].time>=0)
{
add(data[i]);
}
}
//输出heap
for(i=0;i<NUM;i++)
{
printf("%s %d\n",data[i].str,data[i].time);
}
}
int main()
{
init();
int index;
char str[256];
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while(scanf("%s",str)!=EOF)
{
index = strhash(str);
index = index%MAXN;
//找一个没放的或者和它相同的
while(data[index].time != -1 && strcmp(data[index].str,str) != 0)
{
index++;
index%=MAXN;
}
if(data[index].time == -1)
{
strcpy(data[index].str,str);
data[index].time = 1;
}
else
{
data[index].time++;
}
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define DEBUG
#define MAXN 7997997
typedef struct _node
{
int num;
int time;
struct _node* next;
}node;
node zhash[MAXN],fhash[MAXN];
int A[5000],B[5000],C[5000],D[5000];
void init(int n)
{
int i;
for(i=0;i<n;i++)
{
zhash[i].time = -1;
fhash[i].time = -1;
zhash[i].next = NULL;
fhash[i].next = NULL;
}
}
void insert(int num)
{
node* h;
if(num >= 0)
h = zhash;
else
h = fhash;
int index = abs(num)%MAXN;
if(h[index].time==-1)
{
h[index].time = 1;
h[index].num = num;
}
else
{
node* p = &h[index];
while(p!=NULL && p->num!=num)
p = p->next;
if(p != NULL)
{
p->time++;
}
else
{
p = (node*)malloc(sizeof(node));
p->num = num;
p->time = 1;
p->next =NULL;
}
}
}
int getres(int num)
{
node* h;
if(num <= 0)
h = zhash;
else
h = fhash;
int index = abs(num)%MAXN;
node* p = &h[index];
while(p!=NULL && p->num!=(num*(-1)))
{
p = p->next;
}
if(p == NULL)
return 0;
else
return p->time;
}
int main()
{
int i,j,count,res=0,tmp;
scanf("%d",&count);
init(MAXN);
for(i=0;i<count;i++)
{
scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
}
for(i=0;i<count;i++)
for(j=0;j<count;j++)
{
tmp = A[i]+B[j];
insert(tmp);
}
for(i=0;i<count;i++)
for(j=0;j<count;j++)
{
tmp = C[i]+D[j];
res += getres(tmp);
}
printf("%d\n",res);
#ifdef DEBUG
scanf("%d",&i);
#endif
return 0;
}
solve();
return 0;
}
继续hash算法。
其实本来是想搞ACM的hash的，苦于各种找不到资料。
POJ2785。
http://poj.org/problem?id=2785
下面代码没AC。
题目自己看吧，思路是正数一个hash表，负数一个hash表，然后把O(N^4)复杂度搞成O(N^2)。上面玩的是开散列。下面是闭散列。无代码规范代码。