package hashtable
import "bitbucket.org/ww/hashtable"

Various hash table implementations.
By William Waites <ww@styx.org> in 2011.

Direct support is only basically for Get/Set/Del operations. Key-value
storage is simple, just define a type that implements the Hashable
interface and has an extra value. For example to have dictionary with
a string index to some complex value one might write,

    type HashableKeyValue struct {
        Key string
        Value *SomeComplexType

    func (hkv *HashableKeyValue) Hash uint64 {
        /// some hash function on Key string

    func (hkv *HashableKeyValue) Equals(other Hashable) bool {
        /// equality only defined on compatible types, a more
        /// elaborate equality might be implemented with the help
        /// of the reflect package
        others := other.(HashableKeyValue)
        return hkv.Key == others.Key

To retrieve such a value, you could just do

     entry := ht.Get(HashableKeyValue{"somestring", nil})
     kv := entry.(HashableKeyValue)


type Dummy uint64
a really silly hashable object with a pathologically bad hashing
algorithm this is mostly useful for testing

func (d *Dummy) Equals(other Hashable) bool

func (d *Dummy) Hash() uint64

type HashTable interface {
    Set(item Hashable)
    Get(item Hashable) Hashable
    Has(item Hashable) bool
    Del(item Hashable)
    Size() int
    // Iterate over all values and output over the channel
    // the iteration happens in a goroutine.
    Items() chan Hashable
Hash table interface

func NewMapHash(args ...interface{}) HashTable

type HashTableFactory func(...interface{}) HashTable
Factory interface for use  in places where the higher level code
may not care about which hash table implementation is used.

type Hashable interface {
    Hash() uint64
    Equals(Hashable) bool
To be useable as an entry in a hash table a type must
define a hash operator that should output some suitable
output evenly distributed over uint64 and an equality

func NewHashableInt(value int) Hashable

type HashableInt struct {
    Int int
    // contains unexported fields

func (hi *HashableInt) Equals(other Hashable) bool

func (hi *HashableInt) Hash() uint64

type MapHash struct {
    // contains unexported fields
A simple hash table built on the Go runtime's maps

func (m *MapHash) Del(item Hashable)

func (m *MapHash) Get(item Hashable) Hashable

func (m *MapHash) Has(item Hashable) bool

func (m *MapHash) Items() (out chan Hashable)

func (m *MapHash) Set(item Hashable)
basically linear probing in case of collisions

func (m *MapHash) Size() int