robinhood

README

Robin Hood Hashing

Robin Hood hashing is an algorithm for creating efficient hash table. This is a simple implementation of open addressing hash table in order to do experiment of comparison between linear probing and Robin Hood hashing.

Usage

Run load test

 $ go test github.com/Lewuathe/robinhood

The load result is stored in data/load_test.csv which keeps

• Test epoch
• Algorithm (Linear, RobinHood),
• Load factor
• Average value of DIB (Distance to Initial Bucket)
• Elapsed time in milliseconds

The test case is

• Create 10000 fixed size hash table (for simplicity it cannot be resized)
• Running Put and Get per each load factor target
• Run above operation 20 times (epoch)

This is the distribution of elapsed time in each algorithm. Robin Hood aims to avoid high variance of lookup time. Surely Robin Hood time of insert and lookup is smaller than the one of linear probing.

We can see low elapsed time even in high load factor case. The most efficient and stable case of Robin Hood hashing looks around 0.5~0.6 load factor.

Reference

• I Wrote The Fastest Hashtable
• Open Addressing
• Robin Hood Hashing should be your default Hash Table implementation

License

MIT License

Documentation

Index

• func FnvHash(s string) uint32
• type Entry
• type HashMap
• type Linear
  • func NewLinear(size int) *Linear
  • func (m *Linear) DibAverage() float32
  • func (m *Linear) Erase(k string)
  • func (m *Linear) Get(k string) interface{}
  • func (m *Linear) LoadFactor() float32
  • func (m *Linear) Put(k string, v interface{})
  • func (m Linear) Size() uint32
  • func (m *Linear) String() string
• type RobinHood
  • func NewRobinHood(size int) *RobinHood
  • func (m *RobinHood) DibAverage() float32
  • func (m *RobinHood) Erase(k string)
  • func (m *RobinHood) Get(k string) interface{}
  • func (m *RobinHood) LoadFactor() float32
  • func (m *RobinHood) Put(k string, v interface{})
  • func (m RobinHood) Size() uint32
  • func (m *RobinHood) String() string

Functions

func FnvHash

func FnvHash(s string) uint32

Types

type Entry

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

type HashMap

type HashMap interface {
	Size() uint32
	Get(string) interface{}
	Put(string, interface{})
	Erase(string)
	String() string
	LoadFactor() float32
	DibAverage() float32
}

type Linear

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

func NewLinear

func NewLinear(size int) *Linear

func (*Linear) DibAverage

func (m *Linear) DibAverage() float32

func (*Linear) Erase

func (m *Linear) Erase(k string)

func (*Linear) Get

func (m *Linear) Get(k string) interface{}

func (*Linear) LoadFactor

func (m *Linear) LoadFactor() float32

func (*Linear) Put

func (m *Linear) Put(k string, v interface{})

func (Linear) Size

func (m Linear) Size() uint32

func (*Linear) String

func (m *Linear) String() string

type RobinHood

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

func NewRobinHood

func NewRobinHood(size int) *RobinHood

func (*RobinHood) DibAverage

func (m *RobinHood) DibAverage() float32

func (*RobinHood) Erase

func (m *RobinHood) Erase(k string)

func (*RobinHood) Get

func (m *RobinHood) Get(k string) interface{}

func (*RobinHood) LoadFactor

func (m *RobinHood) LoadFactor() float32

func (*RobinHood) Put

func (m *RobinHood) Put(k string, v interface{})

func (RobinHood) Size

func (m RobinHood) Size() uint32

func (*RobinHood) String

func (m *RobinHood) String() string