hash算法一直被我認(rèn)為成一種處理大數(shù)據(jù)量的高效算法(時(shí)間復(fù)雜度)。
從一道百度面試題開(kāi)始。
搜索引擎會(huì)通過(guò)日志文件把用戶每次檢索使用的所有檢索串都記錄下來(lái)，每個(gè)查詢串的長(zhǎng)度為1-255字節(jié)。
假設(shè)目前有一千萬(wàn)個(gè)記錄（這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬(wàn)，但如果除去重復(fù)后，不超過(guò)3百萬(wàn)個(gè)。一個(gè)查詢串的重復(fù)度越高，說(shuō)明查詢它的用戶越多，也就是越熱門。），請(qǐng)你統(tǒng)計(jì)最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過(guò)1G。
好。首先想暴力解決下，看看內(nèi)存夠不夠。大約255X10^8B內(nèi)存，2.4G的樣子。。超內(nèi)存了。。汗。。300萬(wàn)，那就是0.8G，剛剛好。很自然的，我們可以想到，如果每次向內(nèi)存讀一個(gè)字符串，然后把那個(gè)字符串出現(xiàn)的次數(shù)和字符串存起來(lái)，這樣，就可以在不超過(guò)1G的情況下搞定。編程珠璣上面有這道題目的int版本，大概就是問(wèn)10億個(gè)整數(shù)（從1到10億，缺一個(gè)），不超過(guò)多少內(nèi)存，要求最快找出缺少的數(shù)。那個(gè)題目也是利用hash的思想，不過(guò)它的hash函數(shù)就是它自己就是了。開(kāi)一個(gè)10億比特的內(nèi)存，然后把flag[num]設(shè)置一下，最后再統(tǒng)計(jì)一下。好吧，這個(gè)題目是不是可以利用類似的思想呢？好吧，hash吧。
hash算法的基本步驟是：把數(shù)據(jù)存放到key(data[i])里面。如此簡(jiǎn)單。就是建立data[i]和i的映射關(guān)系，然后利用數(shù)組可以隨機(jī)訪問(wèn)的特點(diǎn)，使得在O(1)的時(shí)間復(fù)雜度再次找到數(shù)據(jù)(理想情況，可能沖突)！hash最直接的利用就是lookup table,查找表。建立一個(gè)hash表，然后可以進(jìn)行快速查找。（如果出現(xiàn)訪問(wèn)沖突怎么辦呢？大致分為兩種辦法：開(kāi)散列和閉散列。開(kāi)散列就是找到了這個(gè)位置被別人占了，好，找個(gè)規(guī)則換地方。閉散列就是這個(gè)地方被別人站著，我跟在他后面(鏈表)。高深的玩意研究不懂，MARK之，以后慢慢看）。
hash解決此題：網(wǎng)上找一個(gè)字符串hash函數(shù)看看先(看不懂，直接用。哪位大神可以告訴我為什么或者詳細(xì)資料??)。建立一個(gè)空的hash表，每次讀一個(gè)字符串。找到這個(gè)字符串的key（就是用hash函數(shù)對(duì)它XXX）,返回一個(gè)位置。看看那個(gè)位置是不是被別人占了。如果被別人占了，我就往后走，直到找到一個(gè)空位子。坐下。當(dāng)然這個(gè)過(guò)程也許會(huì)找到和自己一樣的，那樣就把它的訪問(wèn)次數(shù)+1。好了，hash表建好了，里面有300萬(wàn)個(gè)字符串，每一個(gè)字符串的搜索次數(shù)也統(tǒng)計(jì)出來(lái)了。
問(wèn)題完成了第一步。
第二部是，統(tǒng)計(jì)TOP K字符串。這個(gè)。。可以排個(gè)序，qsort,O(N*logN),太挫了。果斷用個(gè)小頂堆，把復(fù)雜度降到O(N*log(K))，K 很小，這個(gè)很劃算啊。
關(guān)于堆的問(wèn)題就不詳細(xì)闡述了，實(shí)現(xiàn)簡(jiǎn)單(siftdown(int),siftup(int))，目的明確(取最值，增加刪除元素)。下面是測(cè)試的代碼。當(dāng)然我沒(méi)有那么大的數(shù)據(jù)量，寫的代碼也僅供測(cè)試之用。
#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;
//找一個(gè)沒(méi)放的或者和它相同的
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;
}
繼續(xù)hash算法。
其實(shí)本來(lái)是想搞ACM的hash的，苦于各種找不到資料。
POJ2785。
http://poj.org/problem?id=2785
下面代碼沒(méi)AC。
題目自己看吧，思路是正數(shù)一個(gè)hash表，負(fù)數(shù)一個(gè)hash表，然后把O(N^4)復(fù)雜度搞成O(N^2)。上面玩的是開(kāi)散列。下面是閉散列。無(wú)代碼規(guī)范代碼。