有挑战 murmurhash 的没有？

[Moore]

挑战类型1： 运算速度， 2：碰撞率

贴个6年前的代码， 比murmurhash效率低，碰撞率还要高一点，不过碰撞率高不多。

运行时间比 murmur 1 : myHash 1.2 （数值越小效率越高）

HashIntTab 是一个随机证书二维向量表，

初始化时这样操作一把
#define M1LEN 39
#define M2LEN 0x400
#define MXM1 M1LEN*M1LEN

int **initM2table() {
int i,j,ranhp,rantmp;
int **m2table;

m2table = (int **)calloc(MXM1,sizeof(int *));
for (j = 0; j < MXM1; j++)
m2table[j] = (int *)calloc(M2LEN,sizeof(int));

for (j = 0; j < MXM1; j++)
for (i = 0; i < M2LEN; i++)
m2table[j][i] = i+j*MXM1;

for (j = 0; j < MXM1; j++)
for (i = 0; i < M2LEN; i++) {
ranhp = (int) random () & (M2LEN - 1);
rantmp = m2table[j][ranhp];
m2table[j][ranhp] = m2table[j][i];
m2table[j][i] = rantmp;
}

return(m2table);
}

ctable 是一个可显示的ascii 码表。
int ctable[] = { -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 39, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 37, 38, -1, 0, 1, 2,
3, 4, 5, 6, 7, 8, 9, 10, -1, -1,
-1, -1, -1, -1, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
27, 28, 29, 30, 31, 32, 33, 34, 35, 36,
-1, -1, -1, -1, 39, -1, 11, 12, 13, 14,
15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
35, 36, -1, -1, -1, -1, -1, -1, -1, -1
};

unsigned int iNameHash(char *s,int xlen)
{
unsigned int x, r, i,retval;
char c;
unsigned int first;
unsigned int ends;
StructDN *pre, *cur;

retval = FALSE;
i = x = r = 0;

if (s == NULL) return(retval);

first = (int) s[0] * (int) s[1];

for(i=0 ; i<xlen; i++) {
r = (x >> 27) & 0x7f;
x <<= 5;
x |= r;

c = (char) s[i];
if ((int) ctable[(int)c] >= 0)
x ^= (c & 0x7f);
i++;
}

first %= MXM1;

i = x ^ ((HashIntTab[first][x & 0x3ff]) & 0xffff);

return(i);
}

[Zhangming Niu]

。。。。这东西不是08年才有的吗 。。。

怎么弄出来了个·6年前·的代码。。。

2011/11/25 Moore <lyx...@gmail.com>

--
--------------------------------------------------------------------
Best Regards,

Zhangming Niu

[白志伟]

能不能讲下原理，没看出来为啥快！

[Zhangming Niu]

Performance results from Hsieh's test app -

CRC32           :  4.7810s
oneAtATimeHash  :  3.5470s
alphaNumHash    :  2.2500s
FNVHash         :  2.1870s
Jenkins lookup3 :  1.2650s
SuperFastHash   :  1.2970s
MurmurHash      :  0.9060s

2011/11/25 白志伟 <baizh...@gmail.com>

[Zhangming Niu]

运时间比应该不准确把。不然就排第2快了。

2011/11/25 Zhangming Niu <niuzha...@gmail.com>

[Ray Song]

操作少

[Moore]

我贴代码了撒，说实话，是elf hash 的变种，加了串首2字符 和 串长度 二个维度信息，这样可以减少碰撞的哈。

所以，效果好的撒。至于运行时间么，你可以测试一下看撒。

我一直藏着，直到有一天我测试了murmurhash 和 我的代码的效率，我知道，不用再藏着了。

晒出来让大家批判一下哈。

On Nov 25, 9:57 pm, Zhangming Niu <niuzhangm...@gmail.com> wrote:
> 运时间比应该不准确把。不然就排第2快了。
>

> 2011/11/25 Zhangming Niu <niuzhangm...@gmail.com>
>

[Zhangming Niu]

说实话，你那个测试时间太乐观了。

因为·性能·会比市面很多做内核或者cpu用的算法·好·。

这个几乎是不可能的。

可能是某类情况有不错的速度，还有bench mark, task complexity这些定量。

2011/11/25 Moore <lyx...@gmail.com>

[Moore]

本来就是放给你批判的，你提个更好的撒。