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 PJQ at 2014-08-05 16:44:45 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方法.

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