lock free pointer free golang hash table implementation. DO NOT USE. UNTESTED.

lockfree.go

package main

import (
	"errors"
	"flag"
	"log"
	"os"
	"runtime"
	"strconv"
	"sync"
	"time"

	"github.com/spaolacci/murmur3"
)

type Record struct {
	Key   [35]byte
	Index int32
}

type MyHash struct {
	Table []Record
	Size  uint32
}

func (hash *MyHash) Init(size int) {
	hash.Size = uint32(size)
	hash.Table = make([]Record, hash.Size)
}

func (hash *MyHash) Keys() [][35]byte {
	var keys [][35]byte
	for i := 0; i < len(hash.Table); i++ {
		if hash.Table[i].Key != [35]byte{} {
			keys = append(keys, hash.Table[i].Key)
		}
	}
	return keys
}

func (hash *MyHash) Get(key [35]byte) int32 {
	offset := murmur3.Sum32(key[:]) % hash.Size
	nullkey := [35]byte{}
	for i := uint32(0); ; i++ {
		if hash.Table[(offset+i)%hash.Size].Key == key {
			return hash.Table[(offset+i)%hash.Size].Index
		} else if hash.Table[(offset+i)%hash.Size].Key == nullkey {
			return 0
		}
	}
}

func (hash *MyHash) Set(key [35]byte, value int32) (int32, error) {
	seen_zero := 0
	offset := murmur3.Sum32(key[:]) % hash.Size
	nullkey := [35]byte{}
	tries := 0
	for i := uint32(0); ; i++ {
		if (offset+i)%hash.Size == 0 {
			seen_zero++
		}
		if seen_zero > 1 {
			return int32(0), errors.New("Hash table full. We looked and looked, couldn't find a spot.")
		}
		if hash.Table[(offset+i)%hash.Size].Key == key {
			hash.Table[(offset+i)%hash.Size].Index = value
			return hash.Table[(offset+i)%hash.Size].Index, nil
		} else if hash.Table[(offset+i)%hash.Size].Key == nullkey {
		trySet:
			hash.Table[(offset+i)%hash.Size].Index = value
			hash.Table[(offset+i)%hash.Size].Key = key

			if key == hash.Table[(offset+i)%hash.Size].Key && value == hash.Table[(offset+i)%hash.Size].Index {
				// everything is awesome, we're done
				return hash.Table[(offset+i)%hash.Size].Index, nil
			} else if key != hash.Table[(offset+i)%hash.Size].Key {
				// someone clobbered our key. Be polite and try again.
				log.Println("Someone clobbered our key. We're going to try again. Try", tries, "nesting..for", string(key[:]), value)
				return hash.Set(key, value)
			} else if value != hash.Table[(offset+i)%hash.Size].Index && key == hash.Table[(offset+i)%hash.Size].Key {
				// this is our key. Fuck 'em.
				log.Println("Someone clobbered our value. This is OUR key. writing again for the ", tries, "time")
				tries += 1
				goto trySet
			}

			hash.Table[(offset+i)%hash.Size].Index = value
			hash.Table[(offset+i)%hash.Size].Key = key

			return hash.Table[(offset+i)%hash.Size].Index, nil
		}
	}

}

var (
	pressure  = flag.Int("pressure", 5, "Amount of write pressure to apply.")
	tablesize = flag.Int("size", 3e7, "Hash Table Size")
	numkeys   = flag.Int("keys", 2.5e7, "Number of Keys. Go larger than tablesize to check full table behaviour.")
	maxprocs  = flag.Int("maxprocs", runtime.NumCPU()*6, "Max threads. Defaults to 6 * core")
)

func main() {
	flag.Parse()
	log.Println("Commencing test with pressure", *pressure, "table size", *tablesize, "keys", *numkeys)
	very_start := time.Now()
	runtime.GOMAXPROCS(*maxprocs)
	myhash := MyHash{}
	myhash.Init(*tablesize)
	numthreads := runtime.NumCPU() * 6
	numsets := *numkeys / numthreads
	var wg sync.WaitGroup
	start := time.Now()

	for threadnum := 0; threadnum < numthreads; threadnum++ {
		wg.Add(1)
		//log.Println("goroutine for", threadnum, "with numsets", numsets)
		go func(i int) {
			var mykey [35]byte
			for counter := (numsets * i); counter < numsets*(i+1+*pressure); counter++ {
				mykey = [35]byte{}
				copy(mykey[:], "heyy"+strconv.Itoa(counter))
				_, err := myhash.Set(mykey, int32(counter))
				if err != nil {
					log.Println("Error setting:", err)
					os.Exit(1)
				}
			}
			wg.Done()
		}(threadnum)
	}
	wg.Wait()
	log.Println("Done filling hashtable with ", numsets*numthreads, "items. Took", time.Since(start), "to fill")
	var mykey [35]byte
	for i := int32(*tablesize / 2); i < int32(*tablesize/2)+5; i++ {
		mykey = [35]byte{}
		start = time.Now()
		copy(mykey[:], "heyy"+strconv.Itoa(int(i)))
		_ = myhash.Get(mykey)
		log.Println("Lookup took", time.Since(start))
	}
	start = time.Now()
	log.Println("Commencing Garbage Collection.")
	runtime.GC()
	log.Println("Done. Took", time.Since(start))

	start = time.Now()
	log.Println("Commencing Second Garbage Collection.")
	runtime.GC()
	log.Println("Done. Took", time.Since(start))

	log.Println("All done with test hash containing", len(myhash.Table), ". Total runtime", time.Since(very_start))
}

On further thinking, I believe it's necessary to use a Compare and Swap on key setting to ensure that only one thread has the slot. In go, that means you'll probably be using numeric keys. You could use pointers, but for a large table you will end up with significant GC worries as the number of pointers grows.