libamxc  1.10.3
C Generic Data Containers
Functions
Hash functions

Functions

unsigned int amxc_RS_hash (const char *str, const unsigned int len)
 Calculate a hash from a string. More...
 
unsigned int amxc_JS_hash (const char *str, const unsigned int len)
 Calculate a hash from a string. More...
 
unsigned int amxc_PJW_hash (const char *str, const unsigned int len)
 Calculate a hash from a string. More...
 
unsigned int amxc_ELF_hash (const char *str, const unsigned int len)
 Calculate a hash from a string. More...
 
unsigned int amxc_BKDR_hash (const char *str, const unsigned int len)
 Calculate a hash from a string. More...
 
unsigned int amxc_SDBM_hash (const char *str, const unsigned int len)
 Calculate a hash from a string. More...
 
unsigned int amxc_DJB_hash (const char *str, const unsigned int len)
 Calculate a hash from a string. More...
 
unsigned int amxc_DEK_hash (const char *str, const unsigned int len)
 Calculate a hash from a string. More...
 
unsigned int amxc_BP_hash (const char *str, const unsigned int len)
 Calculate a hash from a string. More...
 
unsigned int amxc_FNV_hash (const char *str, const unsigned int len)
 Calculate a hash from a string. More...
 
unsigned int amxc_AP_hash (const char *str, const unsigned int len)
 Calculate a hash from a string. More...
 

Detailed Description

Function Documentation

◆ amxc_AP_hash()

unsigned int amxc_AP_hash ( const char *  str,
const unsigned int  len 
)

Calculate a hash from a string.

An algorithm produced by Arash Partow. He took ideas from all of the above hash functions making a hybrid rotative and additive hash function algorithm. There isn't any real mathematical analysis explaining why one should use this hash function instead of the others described above other than the fact that I tried to resemble the design as close as possible to a simple LFSR. An empirical result which demonstrated the distributive abilities of the hash algorithm was obtained using a hash-table with 100003 buckets, hashing The Project Gutenberg Etext of Webster's Unabridged Dictionary, the longest encountered chain length was 7, the average chain length was 2, the number of empty buckets was 4579.

Parameters
stra string that needs to be hashed
lenthe length that must be used of the string to calculate the hash
Returns
The calculated hash value

Definition at line 185 of file amxc_hash_func.c.

185  {
186  unsigned int hash = 0xAAAAAAAA;
187  unsigned int i = 0;
188 
189  for(i = 0; i < len; str++, i++) {
190  hash ^= ((i & 1) == 0) ? ((hash << 7) ^ (*str) * (hash >> 3)) :
191  (~((hash << 11) + ((*str) ^ (hash >> 5))));
192  }
193 
194  return hash;
195 }

◆ amxc_BKDR_hash()

unsigned int amxc_BKDR_hash ( const char *  str,
const unsigned int  len 
)

Calculate a hash from a string.

This hash function comes from Brian Kernighan and Dennis Ritchie's book "The C Programming Language". It is a simple hash function using a strange set of possible seeds which all constitute a pattern of 31....31...31 etc, it seems to be very similar to the DJB hash function.

Parameters
stra string that needs to be hashed
lenthe length that must be used of the string to calculate the hash
Returns
The calculated hash value

Definition at line 118 of file amxc_hash_func.c.

118  {
119  unsigned int seed = 131; /* 31 131 1313 13131 131313 etc.. */
120  unsigned int hash = 0;
121  unsigned int i = 0;
122 
123  for(i = 0; i < len; str++, i++) {
124  hash = (hash * seed) + (*str);
125  }
126 
127  return hash;
128 }

◆ amxc_BP_hash()

unsigned int amxc_BP_hash ( const char *  str,
const unsigned int  len 
)

Calculate a hash from a string.

An algorithm proposed by Donald E. Knuth in The Art Of Computer Programming Volume 3, under the topic of sorting and search chapter 6.4.

Parameters
stra string that needs to be hashed
lenthe length that must be used of the string to calculate the hash
Returns
The calculated hash value

Definition at line 162 of file amxc_hash_func.c.

162  {
163  unsigned int hash = 0;
164  unsigned int i = 0;
165  for(i = 0; i < len; str++, i++) {
166  hash = hash << 7 ^ (*str);
167  }
168 
169  return hash;
170 }

◆ amxc_DEK_hash()

unsigned int amxc_DEK_hash ( const char *  str,
const unsigned int  len 
)

Calculate a hash from a string.

A simple hash function from Robert Sedgwicks Algorithms in C book.

Parameters
stra string that needs to be hashed
lenthe length that must be used of the string to calculate the hash
Returns
The calculated hash value

Definition at line 152 of file amxc_hash_func.c.

152  {
153  unsigned int hash = len;
154  unsigned int i = 0;
155 
156  for(i = 0; i < len; str++, i++) {
157  hash = ((hash << 5) ^ (hash >> 27)) ^ (*str);
158  }
159  return hash;
160 }

◆ amxc_DJB_hash()

unsigned int amxc_DJB_hash ( const char *  str,
const unsigned int  len 
)

Calculate a hash from a string.

An algorithm produced by Professor Daniel J. Bernstein and shown first to the world on the usenet newsgroup comp.lang.c. It is one of the most efficient hash functions ever published.

Parameters
stra string that needs to be hashed
lenthe length that must be used of the string to calculate the hash
Returns
The calculated hash value

Definition at line 141 of file amxc_hash_func.c.

141  {
142  unsigned int hash = 5381;
143  unsigned int i = 0;
144 
145  for(i = 0; i < len; str++, i++) {
146  hash = ((hash << 5) + hash) + (*str);
147  }
148 
149  return hash;
150 }

◆ amxc_ELF_hash()

unsigned int amxc_ELF_hash ( const char *  str,
const unsigned int  len 
)

Calculate a hash from a string.

Similar to the PJW Hash function, but tweaked for 32-bit processors. Its the hash function widely used on most UNIX systems.

Parameters
stra string that needs to be hashed
lenthe length that must be used of the string to calculate the hash
Returns
The calculated hash value

Definition at line 102 of file amxc_hash_func.c.

102  {
103  unsigned int hash = 0;
104  unsigned int x = 0;
105  unsigned int i = 0;
106 
107  for(i = 0; i < len; str++, i++) {
108  hash = (hash << 4) + (*str);
109  if((x = hash & 0xF0000000L) != 0) {
110  hash ^= (x >> 24);
111  }
112  hash &= ~x;
113  }
114 
115  return hash;
116 }

◆ amxc_FNV_hash()

unsigned int amxc_FNV_hash ( const char *  str,
const unsigned int  len 
)

Calculate a hash from a string.

A simple hash function from Robert Sedgwicks Algorithms in C book.

Parameters
stra string that needs to be hashed
lenthe length that must be used of the string to calculate the hash
Returns
The calculated hash value

Definition at line 172 of file amxc_hash_func.c.

172  {
173  const unsigned int fnv_prime = 0x811C9DC5;
174  unsigned int hash = 0;
175  unsigned int i = 0;
176 
177  for(i = 0; i < len; str++, i++) {
178  hash *= fnv_prime;
179  hash ^= (int) (*str);
180  }
181 
182  return hash;
183 }

◆ amxc_JS_hash()

unsigned int amxc_JS_hash ( const char *  str,
const unsigned int  len 
)

Calculate a hash from a string.

A bitwise hash function written by Justin Sobel TODO: What happens if str is NULL?

Parameters
stra string that needs to be hashed
lenthe length that must be used of the string to calculate the hash
Returns
The calculated hash value

Definition at line 71 of file amxc_hash_func.c.

71  {
72  unsigned int hash = 1315423911;
73  unsigned int i = 0;
74 
75  for(i = 0; i < len; str++, i++) {
76  hash ^= ((hash << 5) + (*str) + (hash >> 2));
77  }
78 
79  return hash;
80 }

◆ amxc_PJW_hash()

unsigned int amxc_PJW_hash ( const char *  str,
const unsigned int  len 
)

Calculate a hash from a string.

This hash algorithm is based on work by Peter J. Weinberger of AT&T Bell Labs. The book Compilers (Principles, Techniques and Tools) by Aho, Sethi and Ulman, recommends the use of hash functions that employ the hashing methodology found in this particular algorithm.

Parameters
stra string that needs to be hashed
lenthe length that must be used of the string to calculate the hash
Returns
The calculated hash value

Definition at line 82 of file amxc_hash_func.c.

82  {
83  const unsigned int BitsInUnsignedInt = (unsigned int) (sizeof(unsigned int) * 8);
84  const unsigned int ThreeQuarters = (unsigned int) ((BitsInUnsignedInt * 3) / 4);
85  const unsigned int OneEighth = (unsigned int) (BitsInUnsignedInt / 8);
86  const unsigned int HighBits = (unsigned int) (0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
87  unsigned int hash = 0;
88  unsigned int test = 0;
89  unsigned int i = 0;
90 
91  for(i = 0; i < len; str++, i++) {
92  hash = (hash << OneEighth) + (*str);
93 
94  if((test = hash & HighBits) != 0) {
95  hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
96  }
97  }
98 
99  return hash;
100 }

◆ amxc_RS_hash()

unsigned int amxc_RS_hash ( const char *  str,
const unsigned int  len 
)

Calculate a hash from a string.

A simple hash function from Robert Sedgwicks Algorithms in C book. TODO: What happens if str is NULL?

Parameters
stra string that needs to be hashed
lenthe length that must be used of the string to calculate the hash
Returns
The calculated hash value

Definition at line 57 of file amxc_hash_func.c.

57  {
58  unsigned int b = 378551;
59  unsigned int a = 63689;
60  unsigned int hash = 0;
61  unsigned int i = 0;
62 
63  for(i = 0; i < len; str++, i++) {
64  hash = hash * a + (*str);
65  a = a * b;
66  }
67 
68  return hash;
69 }

◆ amxc_SDBM_hash()

unsigned int amxc_SDBM_hash ( const char *  str,
const unsigned int  len 
)

Calculate a hash from a string.

This is the algorithm of choice which is used in the open source SDBM project. The hash function seems to have a good over-all distribution for many different data sets. It seems to work well in situations where there is a high variance in the MSBs of the elements in a data set.

Parameters
stra string that needs to be hashed
lenthe length that must be used of the string to calculate the hash
Returns
The calculated hash value

Definition at line 130 of file amxc_hash_func.c.

130  {
131  unsigned int hash = 0;
132  unsigned int i = 0;
133 
134  for(i = 0; i < len; str++, i++) {
135  hash = (*str) + (hash << 6) + (hash << 16) - hash;
136  }
137 
138  return hash;
139 }