有关字符串的hash表

gridbird

有几万个基于某字符集的字符串，长度为30。为了便于另外几万个字符串和这个集合的比较，想把这个字符集合建立一个hash表，但是建立字符串集合的hash表，用什么来做hash函数呢？ 比如拿前10个字符的ASCII码等来做，各位有什么好的办法来建立hash表以使得这个比较操作更快，谢谢！

lenovo

请参考gperf。

hightman

贴一个我用的，呵好像php中也是用这个，我是参考自cdb

static unsigned int _xdb_hasher(const char *s, int len)
{
        unsigned int h = 0xf422f;
        while (len--)
        {
                h += (h<<5);
                h ^= (unsigned char) s[len];
                h &= 0x7fffffff;
        }
        return h;
}

MMMIX

原帖由 gridbird 于 2007-6-15 16:34 发表
有几万个基于某字符集的字符串，长度为30。为了便于另外几万个字符串和这个集合的比较，想把这个字符集合建立一个hash表，但是建立字符串集合的hash表，用什么来做hash函数呢？ 比如拿前10个字符的ASCII码等来做， ...

The Practice of Programming 中给出了一个，据称是最好的（对 ASCII 字符串来说）。

[ 本帖最后由 MMMIX 于 2007-6-15 17:38 编辑 ]

cugb_cat

原帖由 gridbird 于 2007-6-15 16:34 发表
有几万个基于某字符集的字符串，长度为30。为了便于另外几万个字符串和这个集合的比较，想把这个字符集合建立一个hash表，但是建立字符串集合的hash表，用什么来做hash函数呢？ 比如拿前10个字符的ASCII码等来做， ...

google一下吧  很多进行hash操作的实现啊
比如 关键词：字符串哈希

converse

贴一个现在项目用到的hash函数，可以把传入的一个字符串hash出一个整数，保证了大致平均分配，具体的数学原理我也不太清楚。

1. 
   
2. #define API_Mix(a,b,c) \
   
3. { \
   
4.   a -= b; a -= c; a ^= (c >> 13); \
   
5.   b -= c; b -= a; b ^= (a << 8); \
   
6.   c -= a; c -= b; c ^= (b >> 13); \
   
7.   a -= b; a -= c; a ^= (c >> 12);  \
   
8.   b -= c; b -= a; b ^= (a << 16); \
   
9.   c -= a; c -= b; c ^= (b >> 5); \
   
10.   a -= b; a -= c; a ^= (c >> 3);  \
    
11.   b -= c; b -= a; b ^= (a << 10); \
    
12.   c -= a; c -= b; c ^= (b >> 15); \
    
13. }
    
14. 
    
15. 
    
16. unsigned int bobhash(void *val, unsigned int length)
    
17. {
    
18.         char *k = (char *)val;
    
19.         unsigned long a,b,c,len;
    
20. 
    
21.         /* Set up the internal state */
    
22.        
    
23.         len = length;
    
24.         a = b = c = 0x9e3779b9;         /* the golden ratio; an arbitrary value */
    
25. 
    
26.         /* Handle most of the key */
    
27.        
    
28.         while ( len >= 12 )
    
29.         {
    
30.                 a += (k[0] +((unsigned long)k[1] << 8) +((unsigned long)k[2] << 16) +((unsigned long)k[3] << 24));
    
31.                 b += (k[4] +((unsigned long)k[5] << 8) +((unsigned long)k[6] << 16) +((unsigned long)k[7] << 24));
    
32.                 c += (k[8] +((unsigned long)k[9] << 8) +((unsigned long)k[10]<< 16)+((unsigned long)k[11] << 24));
    
33.                 API_Mix(a,b,c);
    
34.                 k += 12; len -= 12;
    
35.         }
    
36. 
    
37.         /* Handle the last 11 bytes */
    
38.        
    
39.         c += length;
    
40.         switch ( len )                                /* all the case statements fall through */
    
41.         {
    
42.                 case 11: c+=((unsigned long)k[10] << 24);
    
43.                 case 10: c+=((unsigned long)k[9]  << 16);
    
44.                 case 9 : c+=((unsigned long)k[8]  << 8);
    
45.                         /* the first byte of c is reserved for the length */
    
46.                 case 8 : b+=((unsigned long)k[7] << 24);
    
47.                 case 7 : b+=((unsigned long)k[6] << 16);
    
48.                 case 6 : b+=((unsigned long)k[5] << 8);
    
49.                 case 5 : b+=k[4];
    
50.                 case 4 : a+=((unsigned long)k[3] << 24);
    
51.                 case 3 : a+=((unsigned long)k[2] << 16);
    
52.                 case 2 : a+=((unsigned long)k[1] << 8);
    
53.                 case 1 : a+=k[0];
    
54.         }
    
55.        
    
56.         API_Mix(a,b,c);
    
57.         return c;
    
58. }
    

复制代码

传入要进行hash的字符串和hash表的大小即可。

MMMIX

原帖由 converse 于 2007-6-15 22:36 发表
贴一个现在项目用到的hash函数，可以把传入的一个字符串hash出一个整数，保证了大致平均分配，具体的数学原理我也不太清楚。

[code]
#define API_Mix(a,b,c) \
{ \
  a -= b; a -= c; a ^= (c >> 13) ...

这种代码最好在注释中说明一下从什么资料中可以得到算法的具体描述。

converse

原帖由 MMMIX 于 2007-6-15 23:24 发表

这种代码最好在注释中说明一下从什么资料中可以得到算法的具体描述。

出处不详

MMMIX

原帖由 converse 于 2007-6-15 23:25 发表


出处不详

呃……我指定是写这段代码的人应该在注释中说明一下。

lenovo

原帖由 converse 于 2007-6-15 22:36 发表
贴一个现在项目用到的hash函数，可以把传入的一个字符串hash出一个整数，保证了大致平均分配，具体的数学原理我也不太清楚。

[code]
#define API_Mix(a,b,c) \
{ \
  a -= b; a -= c; a ^= (c >> 13) ...

你的算法太复杂了。
好得hash算法哪有这么复杂的。