Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:总结大家Hash的方法

Posted by 13110572081 at 2015-01-29 14:47:03 on Problem 3349
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator