Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:总结大家Hash的方法In Reply To:总结大家Hash的方法 Posted by:archerstarlee at 2009-03-28 11:46:13 > 1. 直接相加, 把(总和%大质数)为key. > 2. 平方和相加, 把(总和%大质数)为key. > 3. 从小到大的顺序, 对v[i]<<(i*3)依次异或, 然后模一个大质数作为key.(by hust07p43) > 4. 六个数中非零数的积再乘上一个大质数,然后模一个100w上下的数。 > 自己拿随机数据测下来110w左右的效果最好,随机情况下数据量是10w的时候hash值相同的情况只有6k多个,几乎可以忽略。(by killertom) > 5. 依次对每个数异或所得的数作为key. (by archerstarlee) > 6. (a[0] + a[2] + a[4])&(a[1] + a[3] + a[5]), 再模一个大质数. 中间的&还可以改成'|' 或者'^'.非常巧妙! 我采用'^'得到最快的719ms. (只对本题适用的hash方法) > > 其实最关键的就是要开放式寻址解决hash冲突, 不要以为hash就能解决问题了. > 最后就是用getchar和gets来进行输入转换更为快速. G++比GCC快一些. > 欢迎大家补充自己更为快速的Hash方法. 链地址法哈希代码一篇: #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; struct node { int data; node *next; }head[100010]; int mp[100010][6]; int main() { int n,js; bool flag = false; memset(head,0,sizeof(head)); scanf("%d",&n); for(int i = 0;i < n;i++) { for(int j = 0;j < 6;j++) { scanf("%d",&mp[i][j]); } if(flag) continue; sort(mp[i],mp[i] + 6); int zh = mp[i][0] % 100000; node *p = (&head[zh])->next; node *q = &(head[zh]); while(p) { js = 0; for(int j = 0;j < 6;j++) { if(mp[p->data][j] == mp[i][j]) js++; else break; } if(js == 6) { flag = true; break; } q = p; p = p->next; } if(!p) { node *r = new node; r->data = i; r->next = NULL; q->next = r; } } if(flag) printf("Twin snowflakes found.\n"); else printf("No two snowflakes are alike.\n"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator