jump

Documentation

Overview

Package jump implements the jump consistent hash algorithm as described in "A Fast, Minimal Memory, Consistent Hash Algorithm"[1]. As the paper notes: "In comparison to the algorithm of Karger et al., jump consistent hash requires no storage, is faster, and does a better job of evenly dividing the key space among the buckets and of evenly dividing the workload when the number of buckets changes. Its main limitation is that the buckets must be numbered sequentially, which makes it more suitable for data storage applications than for distributed web caching."

[1] http://arxiv.org/pdf/1406.2294v1.pdf

Index

• func Hash(key uint64, numBuckets int64) int64

Examples

• Hash

Functions

func Hash

func Hash(key uint64, numBuckets int64) int64

Hash maps a uint64 to a bucket in the range [0, numBuckets).

Example

package main

import (
	"fmt"
	"hash/fnv"
	"log"

	"github.com/m3db/m3/src/x/hash/jump"
)

func main() {
	var (
		numBuckets int64 = 10
		key              = []byte("foo")
		hasher           = fnv.New64()
	)

	// Create hash of the key using whatever hash function you wish.
	if _, err := hasher.Write(key); err != nil {
		log.Fatal(err)
	}
	keyHash := hasher.Sum64()

	// Get which bucket the key is assigned to.
	bucket := jump.Hash(keyHash, numBuckets)

	fmt.Printf("Key '%s' is assigned to bucket %d.\n", string(key), bucket)
}

Output:

Key 'foo' is assigned to bucket 9.