ht_hash_function.h (6973B)
1 #ifndef HT_HASH_FUNCTION_H 2 #define HT_HASH_FUNCTION_H 3 4 #include <stddef.h> 5 6 #ifdef _MSC_VER 7 /* `inline` only advisory anyway. */ 8 #pragma warning(disable: 4710) /* function not inlined */ 9 #endif 10 11 /* Avoid 0 special case in hash functions and allow for configuration with unguessable seed. */ 12 #ifndef HT_HASH_SEED 13 #define HT_HASH_SEED UINT32_C(0x2f693b52) 14 #endif 15 16 #ifndef HT_HASH_32 17 18 #include "cmetrohash.h" 19 20 static inline size_t ht_default_hash_function(const void *key, size_t len) 21 { 22 uint64_t out; 23 24 cmetrohash64_1((const uint8_t *)key, len, HT_HASH_SEED, (uint8_t *)&out); 25 return (unsigned int)out; 26 } 27 28 /* When using the pointer directly as a hash key. */ 29 static inline size_t ht_ptr_hash_function(const void *key, size_t len) 30 { 31 /* MurmurHash3 64-bit finalizer */ 32 uint64_t x; 33 34 (void)len; 35 36 x = ((uint64_t)(size_t)key) ^ (HT_HASH_SEED); 37 38 x ^= x >> 33; 39 x *= 0xff51afd7ed558ccdULL; 40 x ^= x >> 33; 41 x *= 0xc4ceb9fe1a85ec53ULL; 42 x ^= x >> 33; 43 return (size_t)x; 44 } 45 46 #else 47 48 #include "PMurHash.h" 49 50 static inline size_t ht_default_hash_function(const void *key, size_t len) 51 { 52 return (size_t)PMurHash32((HT_HASH_SEED), key, (int)len); 53 } 54 55 /* When using the pointer directly as a hash key. */ 56 static inline size_t ht_ptr_hash_function(const void *key, size_t len) 57 { 58 /* http://stackoverflow.com/a/12996028 */ 59 size_t x; 60 61 x = (size_t)key ^ (HT_HASH_SEED); 62 63 x = ((x >> 16) ^ x) * 0x45d9f3bUL; 64 x = ((x >> 16) ^ x) * 0x45d9f3bUL; 65 x = ((x >> 16) ^ x); 66 return x; 67 } 68 69 #endif /* HT_HASH_32 */ 70 71 72 /* This assumes the key points to a 32-bit aligned random value that is its own hash function. */ 73 static inline size_t ht_uint32_identity_hash_function(const void *key, size_t len) 74 { 75 (void)len; 76 return (size_t)*(uint32_t *)key; 77 } 78 79 /* This assumes the key points to a 64-bit aligned random value that is its own hash function. */ 80 static inline size_t ht_uint64_identity_hash_function(const void *key, size_t len) 81 { 82 (void)len; 83 return (size_t)*(uint64_t *)key; 84 } 85 86 /* This assumes the key points to a 32-bit aligned value. */ 87 static inline size_t ht_uint32_hash_function(const void *key, size_t len) 88 { 89 uint32_t x = *(uint32_t *)key + (uint32_t)(HT_HASH_SEED); 90 91 (void)len; 92 93 /* http://stackoverflow.com/a/12996028 */ 94 x = ((x >> 16) ^ x) * UINT32_C(0x45d9f3b); 95 x = ((x >> 16) ^ x) * UINT32_C(0x45d9f3b); 96 x = ((x >> 16) ^ x); 97 return x; 98 } 99 100 /* This assumes the key points to a 64-bit aligned value. */ 101 static inline size_t ht_uint64_hash_function(const void *key, size_t len) 102 { 103 uint64_t x = *(uint64_t *)key + UINT64_C(0x9e3779b97f4a7c15) + (uint64_t)(HT_HASH_SEED); 104 105 (void)len; 106 107 x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9); 108 x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb); 109 return (size_t)(x ^ (x >> 31)); 110 } 111 112 /* 113 * Suited for set operations of low-valued integers where the stored 114 * hash pointer is the key and the value. 115 * 116 * This function is especially useful for small hash tables (<1000) 117 * where collisions are cheap due to caching but also works for integer 118 * sets up to at least 1,000,000. 119 * 120 * NOTE: The multiplicative hash function by Knuth requires the modulo 121 * to table size be done by shifting the upper bits down, since this is 122 * where the quality bits reside. This yields significantly fewer 123 * collisions which is important for e.g. chained hashing. However, our 124 * interface does not provide the required information. 125 * 126 * When used in open hashing with load factors below 0.7 where the 127 * stored pointer is also the key, collision checking is very cheap and 128 * this pays off in a large range of table sizes where a more 129 * complicated hash simply doesn't pay off. 130 * 131 * When used with a pointer set where the pointer is also the key, it is 132 * not likely to work as well because the pointer acts as a large 133 * integer which works against the design of the hash function. Here a 134 * better mix function is probably worthwhile - therefore we also have 135 * ht_ptr_hash_function. 136 */ 137 static inline size_t ht_int_hash_function(const void *key, size_t len) 138 { 139 (void)len; 140 return ((size_t)key ^ (HT_HASH_SEED)) * 2654435761UL; 141 } 142 143 /* Bernsteins hash function, assumes string is zero terminated, len is ignored. */ 144 static inline size_t ht_str_hash_function(const void *key, size_t len) 145 { 146 const unsigned char *str = key; 147 size_t hash = 5381 ^ (HT_HASH_SEED); 148 size_t c; 149 150 (void)len; 151 152 while ((c = (size_t)*str++)) 153 hash = ((hash << 5) + hash) ^ c; /* (hash * 33) xor c */ 154 155 return hash; 156 } 157 158 /* Hashes at most len characters or until zero termination. */ 159 static inline size_t ht_strn_hash_function(const void *key, size_t len) 160 { 161 const unsigned char *str = key; 162 size_t hash = 5381 ^ (HT_HASH_SEED); 163 size_t c; 164 165 while (--len && (c = (size_t)*str++)) 166 hash = ((hash << 5) + hash) ^ c; /* (hash * 33) xor c */ 167 168 return hash; 169 } 170 171 static inline uint32_t ht_fnv1a32_hash_function(const void *key, size_t len) 172 { 173 #ifndef FNV1A_NOMUL 174 const uint32_t prime = UINT32_C(0x1000193); 175 #endif 176 uint32_t hash = UINT32_C(0x811c9dc5); 177 const uint8_t *p = key; 178 179 while (len--) { 180 hash ^= (uint64_t)*p++; 181 #ifndef FNV1A_NOMUL 182 hash *= prime; 183 #else 184 hash += (hash << 1) + (hash << 4) + (hash << 7) + 185 (hash << 8) + (hash << 24); 186 #endif 187 } 188 return hash; 189 } 190 191 static inline uint64_t ht_fnv1a64_hash_function(const void *key, size_t len) 192 { 193 #ifndef FNV1A_NOMUL 194 const uint64_t prime = UINT64_C(0x100000001b3); 195 #endif 196 uint64_t hash = UINT64_C(0xcbf29ce484222325); 197 const uint8_t *p = key; 198 199 while (len--) { 200 hash ^= (uint64_t)*p++; 201 #ifndef FNV1A_NOMUL 202 hash *= prime; 203 #else 204 hash += (hash << 1) + (hash << 4) + (hash << 5) + 205 (hash << 7) + (hash << 8) + (hash << 40); 206 #endif 207 } 208 return hash; 209 } 210 211 /* Hashes until string termination and ignores length argument. */ 212 static inline uint32_t ht_fnv1a32_str_hash_function(const void *key, size_t len) 213 { 214 #ifndef FNV1A_NOMUL 215 const uint32_t prime = UINT32_C(0x1000193); 216 #endif 217 uint32_t hash = UINT32_C(0x811c9dc5); 218 const uint8_t *p = key; 219 220 (void)len; 221 222 while (*p) { 223 hash ^= (uint64_t)*p++; 224 #ifndef FNV1A_NOMUL 225 hash *= prime; 226 #else 227 hash += (hash << 1) + (hash << 4) + (hash << 7) + 228 (hash << 8) + (hash << 24); 229 #endif 230 } 231 return hash; 232 } 233 234 /* Hashes until string termination and ignores length argument. */ 235 static inline uint64_t ht_fnv1a64_str_hash_function(const void *key, size_t len) 236 { 237 #ifndef FNV1A_NOMUL 238 const uint64_t prime = UINT64_C(0x100000001b3); 239 #endif 240 uint64_t hash = UINT64_C(0xcbf29ce484222325); 241 const uint8_t *p = key; 242 243 (void)len; 244 245 while (*p) { 246 hash ^= (uint64_t)*p++; 247 #ifndef FNV1A_NOMUL 248 hash *= prime; 249 #else 250 hash += (hash << 1) + (hash << 4) + (hash << 5) + 251 (hash << 7) + (hash << 8) + (hash << 40); 252 #endif 253 } 254 return hash; 255 } 256 257 258 #endif /* HT_HASH_FUNCTION_H */