By yusijia

Updated:

Contents
  1. 1. 最常用的两个
  2. 2. 常见的8个

转：http://blog.csdn.net/chenguolinblog/article/details/7833794

最常用的两个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unsigned long long hash;   
// hash使用unsigned long long，超过了unsigned long long就相当于取模  
//常用1  
1  SDBMHash  
int SDBMHash(char *str)  
{  
    hash = 0;  
    while (*str) hash = (*str++) + (hash << 6) + (hash << 16) - hash;  
    return hash;  
}  
//常用2   
int BKDRHash(char *str)  
{  
    int seed = 131;   
    int hash = 0;  
    while (*str) hash = hash * seed + (*str++);  
    return hash;  
}

常见的8个

1
2
3
4
5
6
7
8
9
10
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
const int MAXN = 1000003;  
  
//常用 1  
1  SDBMHash  
unsigned int SDBMHash(char *str)  
{  
    unsigned int hash = 0;  
    while (*str)  
    {  
        // equivalent to: hash = 65599*hash + (*str++);  
        hash = (*str++) + (hash << 6) + (hash << 16) - hash;  
    }  
    return (hash & 0x7FFFFFFF)%MAXN;  
}  
   
2  RS Hash Function  
unsigned int RSHash(char *str)  
{  
    unsigned int b = 378551;  
    unsigned int a = 63689;  
    unsigned int hash = 0;  
   
    while (*str)  
    {  
        hash = hash * a + (*str++);  
        a *= b;  
    }  
    return (hash & 0x7FFFFFFF)%MAXN;  
}  
   
3 JS Hash Function  
unsigned int JSHash(char *str)  
{  
    unsigned int hash = 1315423911;  
   
    while (*str)  
    {  
        hash ^= ((hash << 5) + (*str++) + (hash >> 2));  
    }  
    return (hash & 0x7FFFFFFF)%MAXN;  
}  
   
4 P. J. Weinberger Hash Function  
unsigned int PJWHash(char *str)  
{  
    unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);  
    unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);  
    unsigned int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);  
    unsigned int HighBits         = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);  
    unsigned int hash             = 0;  
    unsigned int test             = 0;  
    while (*str)  
    {  
        hash = (hash << OneEighth) + (*str++);  
        if ((test = hash & HighBits) != 0)  
        {  
            hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));  
        }  
    }  
    return (hash & 0x7FFFFFFF)%MAXN;  
}  
   
5 ELF Hash Function  
unsigned int ELFHash(char *str)  
{  
    unsigned int hash = 0;  
    unsigned int x    = 0;  
    while (*str)  
    {  
        hash = (hash << 4) + (*str++);  
        if ((x = hash & 0xF0000000L) != 0)  
        {  
            hash ^= (x >> 24);  
            hash &= ~x;  
        }  
    }  
    return (hash & 0x7FFFFFFF)%MAXN;  
}  
   
//常用2   
6 BKDR Hash Function  
unsigned int BKDRHash(char *str)  
{  
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..  
    unsigned int hash = 0;  
    while (*str)  
    {  
        hash = hash * seed + (*str++);  
    }  
    return (hash & 0x7FFFFFFF)%MAXN;  
}  
   
7 DJB Hash Function  
unsigned int DJBHash(char *str)  
{  
    unsigned int hash = 5381;  
    while (*str)  
    {  
        hash += (hash << 5) + (*str++);  
    }  
    return (hash & 0x7FFFFFFF)%MAXN;  
}  
   
8 AP Hash Function  
unsigned int APHash(char *str)  
{  
    unsigned int hash = 0;  
    int i;  
    for (i=0; *str; i++)  
    {  
        if ((i & 1) == 0)  
        {  
            hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));  
        }  
        else  
        {  
            hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));  
        }  
    }  
    return (hash & 0x7FFFFFFF)%MAXN;  
}
Contents
  1. 1. 最常用的两个
  2. 2. 常见的8个