diff options
Diffstat (limited to 'hashfuncs.c')
-rw-r--r-- | hashfuncs.c | 163 |
1 files changed, 163 insertions, 0 deletions
diff --git a/hashfuncs.c b/hashfuncs.c new file mode 100644 index 0000000..01a1be1 --- /dev/null +++ b/hashfuncs.c @@ -0,0 +1,163 @@ +/* hashfuncs.c + * + * Hash Functions + * + * notes: aphash may not be correct + * + */ + +#include "hashfuncs.h" + +/* does not mod by the size of the hash table, simple and clever, + * this allows seamless retrieval of collided elements */ +unsigned int defaulthash(const char *key) +{ + unsigned int hash = 0; + + for ( ; *key; key++) + hash += (unsigned char) *key; + + return hash; +} + +unsigned int rshash(const char *key) +{ + unsigned int b = 378551; + unsigned int a = 63689; + unsigned int hash = 0; + + for ( ; *key; key++) + { + hash = hash * a + (*key); + a = a * b; + } + + return hash; +} + +unsigned int jshash(const char *key) +{ + unsigned int hash = 1315423911; + + for ( ; *key; key++) + hash ^= ((hash << 5) + ((unsigned char) (*key)) + (hash >> 2)); + + return hash; +} + +unsigned int pjwhash(const char *key) +{ + const unsigned int BitsInUnsignedInt = (unsigned int) (sizeof(unsigned int) * 8); + const unsigned int ThreeQuarters = (unsigned int) ((BitsInUnsignedInt * 3) / 4); + const unsigned int OneEighth = (unsigned int) (BitsInUnsignedInt / 8); + const unsigned int HighBits = (unsigned int) (0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth); + unsigned int hash = 0; + unsigned int test = 0; + + for ( ; *key; key++) + { + hash = (hash << OneEighth) + (*key); + if ((test = hash & HighBits) != 0) + hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits)); + } + + return hash; +} + +unsigned int elfhash(const char *key) +{ + unsigned int hash = 0; + unsigned int x = 0; + + for ( ; *key; key++) + { + hash = (hash << 4) + (*key); + + if ((x = hash & 0xF0000000L) != 0) + hash ^= (x >> 24); + + hash &= ~x; + } + + return hash; +} + +unsigned int bkdrhash(const char *key) +{ + unsigned int seed = 131; /* 31 131 1313 13131 131313 etc.. */ + unsigned int hash = 0; + + for ( ; *key; key++) + hash = (hash * seed) + (*key); + + return hash; +} + +unsigned int sdbmhash(const char *key) +{ + unsigned int hash = 0; + + for ( ; *key; key++) + hash = (*key) + (hash << 6) + (hash << 16) - hash; + + return hash; +} + +unsigned int djbhash(const char *key) +{ + unsigned int hash = 5381; + + for ( ; *key; key++) + hash = ((hash << 5) + hash) + (*key); + + return hash; +} + +unsigned int dekhash(const char *key) +{ + unsigned int hash = strlen(key); + + for ( ; *key; key++) + hash = ((hash << 5) ^ (hash >> 27)) ^ (*key); + + return hash; +} + +unsigned int bphash(const char *key) +{ + unsigned int hash = 0; + + for ( ; *key; key++) + hash = hash << 7 ^ (*key); + + return hash; +} + +unsigned int fnvhash(const char *key) +{ + const unsigned int fnv_prime = 0x811C9DC5; + unsigned int hash = 0; + + for ( ; *key; key++) + { + hash *= fnv_prime; + hash ^= (*key); + } + + return hash; +} + +unsigned int aphash(const char *key) +{ + unsigned int hash = 0xAAAAAAAA; + unsigned int i = strlen(key); + + for ( ; *key; key++) + { + hash ^= ((i & 1) == 0) ? ( (hash << 7) ^ (*key) * (hash >> 3)) : + (~((hash << 11) + ((*key) ^ (hash >> 5)))); + } + + return hash; +} + |