hashfunctions

commit 1c7caabcb5b454e0228fdd33742c28f9b5133a9d
parent 165c16127dbb1a25de99062b0c36d981804c6ab2
Author: Remy Noulin <loader2x@gmail.com>
Date:   Tue, 25 Dec 2018 05:44:46 -0500

add jump consistent hash

hashfunctions.c | 42 ++++++++++++++++++++++++++++++++++++++++++
hashfunctions.h |  2 ++
main.c          |  4 ++++
package.yml     |  7 +++----
4 files changed, 51 insertions(+), 4 deletions(-)

Diffstat:
M
hashfunctions.c
 | 
42
++++++++++++++++++++++++++++++++++++++++++
M
hashfunctions.h
 | 
2
++
M
main.c
 | 
4
++++
M
package.yml
 | 
7
+++----

4 files changed, 51 insertions(+), 4 deletions(-)
diff --git a/hashfunctions.c b/hashfunctions.c
@@ -86,3 +86,45 @@ u32 murmur2hash(const unsigned char *b, size_t len)
   return h;
 }
 
+/**
+ * Jump consistent hashing
+ *
+ * From the paper "A Fast, Minimal Memory, Consistent Hash Algorithm" by John Lamping, Eric Veach (2014, Google).
+ * http://arxiv.org/abs/1406.2294
+ */
+/* Original from paper in C style - added () around double */
+/* 128 bit key version? > hash key to 64bit */
+/*
+int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
+  int64_t b = -1, j = 0;
+  while (j < num_buckets) {
+    b = j;
+    key = key * 2862933555777941757ULL + 1;
+    j = (b + 1) * ((double)(1LL << 31) / (double)((key >> 33) +1));
+  }
+  return b;
+}
+*/
+
+/**
+ * jump consistent hash
+ *
+ * \param
+ *   key key to store in a bucket
+ * \param
+ *   bucketCount number of buckets in the hashring
+ * \return
+ *   bucket number
+ *   -1 error
+ */
+i32 jumpConsistentHash(u64 key, i32 bucketCount) {
+  /* b for bucket, j for jump */
+  i64 b = -1, j = 0;
+  while (j < bucketCount) {
+    b = j;
+    /* PRNG with key as seed */
+    key = key * 2862933555777941757ULL + 1;
+    j = (b + 1) * ((f64)(1LL << 31) / (f64)((key >> 33) +1));
+  }
+  return b;
+}
diff --git a/hashfunctions.h b/hashfunctions.h
@@ -10,3 +10,5 @@ u32 u32Hash(u32 k);
 u64 u64Hash(u64 k);
 
 u32 murmur2hash(const unsigned char *b, size_t len);
+
+i32 jumpConsistentHash(u64 key, i32 bucketCount);
diff --git a/main.c b/main.c
@@ -48,4 +48,8 @@ int main(int ARGC, char** ARGV) {
   murmurHash3_x64_128("the key", strlen("the key"), seed, hash);
   logI("murmurHash3_x64_128: %lu %lu", hash[0], hash[1]);
 
+  // jump consistent hash
+  i32 jumpHash = jumpConsistentHash(10863919174838991 /* key */, 11 /* bucket count */);
+
+  logVarG(jumpHash);
 }
diff --git a/package.yml b/package.yml
@@ -1,15 +1,14 @@
 ---
   name: hashfunctions
-  version: 0.0.5
-  description: "generic hash functions and PRFs: Jenkins, FNV, siphash, murmur2, murmur3, md5"
+  version: 0.0.6
+  description: "generic hash functions and PRFs: Jenkins, FNV, siphash, murmur2, murmur3, md5, jump consistent hash"
   bin: ./hashfunctions.c
   cflags: -O3 -std=gnu11 -fPIC -pipe
   repository:
     type: git
     url: git+https://github.com/RemyNoulin/hashfunctions.git
   keywords:
-   #- utility
-    - command
+    - hashing
   author: Anonymous
   license: MIT
   bugs: