doublejump

README

Overview

This is a revamped Google's jump consistent hash. It overcomes the shortcoming of the original implementation - not being able to remove nodes. Here is the main idea behind doublejump.

Benchmark

BenchmarkDoubleJump/10-nodes                     54723506           21.8 ns/op
BenchmarkDoubleJump/100-nodes                    31263981           38.6 ns/op
BenchmarkDoubleJump/1000-nodes                   24227624           48.5 ns/op

BenchmarkStathatConsistent/10-nodes              4053433           292.8 ns/op
BenchmarkStathatConsistent/100-nodes             3625465           333.8 ns/op
BenchmarkStathatConsistent/1000-nodes            3148849           389.5 ns/op

BenchmarkSerialxHashring/10-nodes                2357866           509.8 ns/op
BenchmarkSerialxHashring/100-nodes               2161783           531.3 ns/op
BenchmarkSerialxHashring/1000-nodes              1957911           628.4 ns/op

Example

h := NewHash()
for i := 0; i < 10; i++ {
    h.Add(fmt.Sprintf("node%d", i))
}

fmt.Println(h.Len())
fmt.Println(h.LooseLen())

fmt.Println(h.Get(1000))
fmt.Println(h.Get(2000))
fmt.Println(h.Get(3000))

h.Remove("node3")
fmt.Println(h.Len())
fmt.Println(h.LooseLen())

fmt.Println(h.Get(1000))
fmt.Println(h.Get(2000))
fmt.Println(h.Get(3000))

// Output:
// 10
// 10
// node9
// node2
// node3
// 9
// 10
// node9
// node2
// node0

Acknowledgements

The implementation of the original algorithm is credited to dgryski.

Documentation

Overview

Package doublejump provides a revamped Google's jump consistent hash.

Example

h := NewHash()
for i := 0; i < 10; i++ {
	h.Add(fmt.Sprintf("node%d", i))
}

fmt.Println(h.Len())
fmt.Println(h.LooseLen())

fmt.Println(h.Get(1000))
fmt.Println(h.Get(2000))
fmt.Println(h.Get(3000))

h.Remove("node3")
fmt.Println(h.Len())
fmt.Println(h.LooseLen())

fmt.Println(h.Get(1000))
fmt.Println(h.Get(2000))
fmt.Println(h.Get(3000))

Output:
10
10
node9
node2
node3
9
10
node9
node2
node0

Index

• type Hash
  • func NewHash() *Hash
  • func (this *Hash) Add(obj interface{})
  • func (this *Hash) All() []interface{}
  • func (this *Hash) Get(key uint64) interface{}
  • func (this *Hash) Len() int
  • func (this *Hash) LooseLen() int
  • func (this *Hash) Random() interface{}
  • func (this *Hash) Remove(obj interface{})
  • func (this *Hash) Shrink()

Examples

• Package

Types

type Hash

type Hash struct {
	// contains filtered or unexported fields
}

Hash is a revamped Google's jump consistent hash. It overcomes the shortcoming of the original implementation - not being able to remove nodes.

func NewHash

func NewHash() *Hash

NewHash creates a new doublejump hash instance, which does NOT threadsafe.

func (*Hash) Add

func (this *Hash) Add(obj interface{})

Add adds an object to the hash.

func (*Hash) All

func (this *Hash) All() []interface{}

All returns all the objects in this Hash.

func (*Hash) Get

func (this *Hash) Get(key uint64) interface{}

Get returns an object according to the key provided.

func (*Hash) Len

func (this *Hash) Len() int

Len returns the number of objects in the hash.

func (*Hash) LooseLen

func (this *Hash) LooseLen() int

LooseLen returns the size of the inner loose object holder.

func (*Hash) Random

func (this *Hash) Random() interface{}

Random returns a random object.

func (*Hash) Remove

func (this *Hash) Remove(obj interface{})

Remove removes an object from the hash.

func (*Hash) Shrink

func (this *Hash) Shrink()

Shrink removes all empty slots from the hash.