Simple implementaion of a Hashtable based on java.util.Hashtable.java

hashtable.go

package hashtable

type Key interface {
	HashCode() int
	Equals(Key) bool
}

type entry struct {
	hashCode int
	key      Key
	value    interface{}
	next     *entry
}

type entries []*entry

type Hash interface {
	Put(Key, interface{}) bool
	Get(Key) interface{}
	Keys() []Key
}

type hash struct {
	table      entries
	threshold  int
	count      int
	loadFactor float32
}

func (h *hash) Get(k Key) interface{} {
	hashCode := k.HashCode()
	index := (hashCode & 0x7FFFFFFF) % len(h.table)

	for entry := h.table[index]; entry != nil; entry = entry.next {
		if entry.hashCode == hashCode && entry.key.Equals(k) {
			return entry.value
		}
	}
	return nil
}

func (h *hash) Put(k Key, v interface{}) bool {
	hashCode := k.HashCode()
	index := (hashCode & 0x7FFFFFFF) % len(h.table)

	for entry := h.table[index]; entry != nil; entry = entry.next {
		if entry.hashCode == hashCode && entry.key.Equals(k) {
			entry.value = v
			return true
		}
	}

	h.addEntry(hashCode, k, v, index)
	return true
}

func (h *hash) addEntry(hashCode int, k Key, v interface{}, index int) {
	if h.count >= h.threshold {
		h.rehash()
		hashCode := k.HashCode()
		index = (hashCode & 0x7FFFFFFF) % len(h.table)
	}

	e := h.table[index]
	h.table[index] = &entry{
		hashCode: hashCode,
		key:      k,
		value:    v,
		next:     e,
	}
	h.count++
}

func (h *hash) rehash() {
	oldTable := h.table
	oldCapacity := len(oldTable)
	newCapacity := (oldCapacity << 1)
	h.threshold = int(float32(newCapacity) * h.loadFactor)
	h.table = make(entries, newCapacity)

	for i := oldCapacity - 1; i >= 0; i-- {
		for old := oldTable[i]; old != nil; {
			entry := old
			old = old.next
			index := (entry.hashCode & 0x7FFFFFFF) % newCapacity
			entry.next = h.table[index]
			h.table[index] = entry
		}
	}
}

func (h *hash) Keys() []Key {
	var keys []Key

	for _, entry := range h.table {
		if entry == nil {
			continue
		}

		keys = append(keys, entry.key)
	}

	return keys
}