| ||||||||||
| 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