JumpConsistentHash Scala

JumpConsistentHash.scala

def jumpConsistentHash(theKey: Long, bucketCount: Int): Int = {
  var b = -1L
  var j = 0L
  var key = theKey
  while (j < bucketCount && j >= 0) {
    b = j
    key = key * 2862933555777941757L + 1
    j = ((b + 1) * ((1L << 31).toDouble / ((key >> 33) + 1).toDouble)).toLong
  }
  return b.toInt
}

JumpConsistentHashTailrec.scala

def jumpConsistentHash(key: Long, bucketCount: Int): Int = {
  @annotation.tailrec
  def loop(key: Long, j: Long, bucket: Long): Int = {
    if (j < bucketCount && j >= 0) {
      val newKey = key * 2862933555777941757L + 1L
      loop(newKey,
        ((j + 1) * ((1L << 31).toDouble / (((newKey >> 33) + 1).toDouble))).toLong,
        j)
    } else {
      bucket.toInt
    }
  }
  loop(key, 0, -1)
}
val h = jumpConsistentHash _

See http://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf for the Jump Consistent Hash.

On old 1.6 GHz Atom, 20M hashes on cross product of keys (1,1000) and bucket sizes (1, 20000) was 8.9 seconds.