hashtable

Documentation

Index

• Variables
• func NextLog2(x uint32) uint32
• type Bucket
• type HashTable
  • func NewHashTable(size int, seed int64, extra int, pd, oa, prime bool) *HashTable
  • func (ht *HashTable) HashQuality() float64
  • func (ht *HashTable) Insert(ka []byte)
  • func (s *HashTable) Print()
• type Stats
• type TBS

Variables

var Ones = [16]int{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}

var Trace bool

var Zeros = [16]int{4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0}

Functions

func NextLog2

func NextLog2(x uint32) uint32

Henry Warren, "Hacker's Delight", ch. 5.3

Types

type Bucket

type Bucket struct {
	Key []byte
}

type HashTable

type HashTable struct {
	Buckets [][]Bucket
	Stats

	Seed uint64
	Tcnt int // trace counter
	// contains filtered or unexported fields
}

func NewHashTable

func NewHashTable(size int, seed int64, extra int, pd, oa, prime bool) *HashTable

func (*HashTable) HashQuality

func (ht *HashTable) HashQuality() float64

The theoretical metric from "Red Dragon Book" appears to be useless

func (*HashTable) Insert

func (ht *HashTable) Insert(ka []byte)

func (*HashTable) Print

func (s *HashTable) Print()

type Stats

type Stats struct {
	Inserts      int // number of elements inserted
	Cols         int // number of collisions
	Probes       int // number of probes
	Heads        int // number of chains > 1
	Dups         int // number of dup hashes on the same chain
	Dups2        int // number of dup hashes
	Nbuckets     int // number of new buckets added
	Entries      int
	LongestChain int // longest chain of entries
	Q            float64
	Dur          time.Duration
	//
	Lines    int
	Size     uint64
	SizeLog2 uint64
	SizeMask uint64
}

type TBS

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