测试哈希函数Hash性能评测(2)

1unsigned int RSHash(const char *str)
2/**//*
3A simple hash function from Robert Sedgwicks Algorithms in C book.
4*/
5{
6    unsigned int b = 378551;
7    unsigned int a = 63689;
8    unsigned int hash = 0;
9
10    while (*str)
11    {
12        hash = hash * a + (*str++);
13        a *= b;
14    }
15
16    return (hash & 0x7FFFFFFF);
17}
18
19unsigned int PJWHash(const char *str)
20/**//*
21This hash algorithm is based on work by Peter J. Weinberger of AT&T Bell Labs. The book Compilers (Principles, Techniques
22and Tools) by Aho, Sethi and Ulman, recommends the use of hash functions that employ the hashing methodology found in this
23particular algorithm.
24*/
25{
26    unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
27    unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);
28    unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / 8);
29    unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
30    unsigned int hash    = 0;
31    unsigned int test    = 0;
32
33    while (*str)
34    {
35        hash = (hash << OneEighth) + (*str++);
36        if ((test = hash & HighBits) != 0)
37        {
38            hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
39        }
40    }
41
42    return (hash & 0x7FFFFFFF);
43}
44
45
46unsigned int JSHash(const char *str)
47/**//*
48A simple hash function from Robert Sedgwicks Algorithms in C book.
49*/
50{
51    unsigned int hash = 1315423911;
52
53    while (*str)
54    {
55        hash ^= ((hash << 5) + (*str++) + (hash >> 2));
56    }
57
58    return (hash & 0x7FFFFFFF);
59}
60
61unsigned int BKDRHash(const char *str)
62{
63    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
64    unsigned int hash = 0;
65
66    while (*str)
67    {
68        hash = hash * seed + (*str++);
69    }
70
71    return (hash & 0x7FFFFFFF);
72}
73
74unsigned int FNV_1_Hash(const char* str)
75/**//*
76Famous hash algorithm in Unix system, also used by Microsoft in their hash_map implementation for VC++ 2005
77detail can be found in :http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param
78*/
79{
80    unsigned int hash = 2166136261;//offset_basis
81    unsigned int prime = 16777619; //FNV_PRIME_32
82    while(*str!='\0')
83    {
84        hash *= prime;
85        hash ^= *str++;
86    }
87    return (hash & 0x7FFFFFFF);
88}
89
90unsigned int FNV_1a_Hash(const char* str)
91/**//*
92Famous hash algorithm in Unix system, also used by Microsoft in their hash_map implementation for VC++ 2005
93detail can be found in :http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param
94*/
95{
96    unsigned int hash = 2166136261;//offset_basis
97    unsigned int prime = 16777619; //FNV_PRIME_32
98    while(*str!='\0')
99    {
100        hash ^= *str++;
101        hash *= prime;
102    }
103    return (hash & 0x7FFFFFFF);
104}
105
106unsigned int DJBHash(const char *str)
107/**//*
108An algorithm produced by Professor Daniel J. Bernstein and shown first to the world on the
109usenet newsgroup comp.lang.c. It is one of the most efficient hash functions ever published.
110*/
111{
112    unsigned int hash = 5381;
113
114    while (*str)
115    {
116        hash += (hash << 5) + (*str++);
117    }
118
119    return (hash & 0x7FFFFFFF);
120}
121
122unsigned int DJB_2_Hash(const char* s)
123{
124    unsigned int hashvalue = 5381;
125    while(*s!='\0')
126    {
127        hashvalue = hashvalue * 33^(*s);
128        s++;
129    }
130    return (hashvalue & 0x7FFFFFFF);
131}
132
133unsigned int SDBM_Hash(const char *str)
134/**//*
135This is the algorithm of choice which is used in the open source SDBM project.
136The hash function seems to have a good overall distribution for many different data
137sets. It seems to work well in situations where there is a high variance in the MSBs of the
138elements in a data set.
139*/
140{
141    unsigned int hash = 0;
142
143    while (*str)
144    {
145        // equivalent to: hash = 65599*hash + (*str++);
146        hash = (*str++) + (hash << 6) + (hash << 16) - hash;
147    }
148
149    return (hash & 0x7FFFFFFF);
150}
151
152unsigned int APHash(const char *str)
153/**//*
154An algorithm produced by me Arash Partow.
155*/
156{
157    unsigned int hash = 0;
158    for (int i=0; *str; i++)
159    {
160        if ((i & 1) == 0)
161        {
162            hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
163        }
164        else
165        {
166            hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
167        }
168    }
169
170    return (hash & 0x7FFFFFFF);
171}