Hash Table implementation

table.go

package main

import (
	"crypto/rand"
	"fmt"
	"time"
)

const (
	keysize   = 35      // bytes
	tablesize = 1 << 21 // entries, must be a power of two
	tablemask = tablesize - 1

	emptyhash = 0
)

type Key [keysize]byte
type Data uint32

type entry struct {
	key  Key
	data Data
	hash uint32
}

type Table [tablesize]entry

func (t *Table) get(k *Key) (e *entry, empty bool) {
	h := hash(k)
	off := int(h & tablemask)
	for i := off; i < off+tablesize; i += 1 {
		e := &(*t)[i&tablemask]
		if e.hash == emptyhash {
			return e, true
		}
		if e.hash == h && e.key == *k {
			return e, false
		}
	}
	return nil, true
}

func (t *Table) Set(key *Key, data Data) {
	e, empty := t.get(key)
	if e == nil {
		panic("table is full")
	}
	if empty {
		e.hash, e.key = hash(key), *key
	}
	e.data = data
}

func (t *Table) Get(key *Key) (r Data, ok bool) {
	e, empty := t.get(key)
	if empty {
		return r, false
	}
	return e.data, true
}

func hash(k *Key) (r uint32) {
	for _, v := range k {
		r = uint32(v) + r<<6 + r<<16 - r
	}
	if r == emptyhash {
		return 1
	}
	return
}

func main() {
	var t Table
	keys := make([]Key, 1000000)

	// note in case of random generates duplicate keys the test may fail
	for i := range keys {
		rand.Read(keys[i][:])
	}

	start := time.Now()
	for i, key := range keys {
		t.Set(&key, Data(i))
	}
	for i, key := range keys {
		v, ok := t.Get(&key)
		if !ok {
			panic("entry missing")
		}
		if v != Data(i) {
			panic(fmt.Sprintf("found %v expected %v", v, i))
		}
	}
	fmt.Println(time.Since(start))
}

table2.go

package main

import (
	"crypto/rand"
	"fmt"
	"time"
)

const (
	keysize   = 35      // bytes
	tablesize = 1 << 21 // entries, must be a power of two

	bucketbits  = 4
	bucketsize  = 1 << bucketbits
	bucketcount = tablesize / bucketsize
	bucketmask  = bucketcount - 1

	emptyhash = 0
)

type Key [keysize]byte
type Data uint32

type entry struct {
	data Data
	key  Key
}

type bucket struct {
	hashes  [bucketsize]uint32
	entries [bucketsize]entry
}

type Table [bucketcount]bucket

func (t *Table) get(key *Key) (b *bucket, i int, empty bool) {
	h := hash(key)
	boff := int(h & bucketmask)
	for i := boff; i < boff+bucketcount; i += 1 {
		b := &(*t)[i&bucketmask]
		for i, eh := range b.hashes {
			if eh == emptyhash {
				return b, i, true
			}
			if eh == h && b.entries[i].key == *key {
				return b, i, false
			}
		}
	}
	return nil, -1, true
}

func (t *Table) Set(key *Key, data Data) {
	b, i, empty := t.get(key)
	if b == nil {
		panic("table is full")
	}
	if empty {
		b.hashes[i] = hash(key)
		b.entries[i].key = *key
	}
	b.entries[i].data = data
}

func (t *Table) Get(key *Key) (r Data, ok bool) {
	b, i, empty := t.get(key)
	if empty {
		return r, false
	}
	return b.entries[i].data, true
}

func hash(k *Key) (r uint32) {
	for _, v := range k {
		r = uint32(v) + r<<6 + r<<16 - r
	}
	if r == emptyhash {
		return 1
	}
	return
}

func main() {
	var t Table
	keys := make([]Key, 1000000)

	// note in case of random generates duplicate keys the test may fail
	for i := range keys {
		rand.Read(keys[i][:])
	}

	start := time.Now()
	for i, key := range keys {
		t.Set(&key, Data(i))
	}
	for i, key := range keys {
		v, ok := t.Get(&key)
		if !ok {
			panic("entry missing")
		}
		if v != Data(i) {
			panic(fmt.Sprintf("found %v expected %v", v, i))
		}
	}
	fmt.Println(time.Since(start))
}