summaryrefslogtreecommitdiffstats
path: root/hashfuncs.c
diff options
context:
space:
mode:
Diffstat (limited to 'hashfuncs.c')
-rw-r--r--hashfuncs.c163
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;
+}
+