hash

Documentation

Overview

Package hash implements a hash table.

Hash table

    hashKey(key) ────────┐
                         │
                         ↓
┌────┬─────┬─────┬────┬─────┬─────┬─────┬─────┐
│    │     │     │    │     │     │     │     │  ←── bucket
└────┴─────┴─────┴────┴─────┴─────┴─────┴─────┘
         │               │
         ↓               ↓
   ┌─────────────┐  ┌─────────────┐
   │ key │ value │  │ key │ value │  ←── entry
   ├─────────────┤  ├─────────────┤
   │ key │ value │  │ key │ value │
   ├─────────────┤  └─────────────┘
   │ key │ value │
   ├─────────────┤
   │ key │ value │
   ├─────────────┤
   │ key │ value │
   └─────────────┘

• hashKey(key) returns a number between 0 to len(buckets)-1
• We use a slice of entries as a bucket to handles cases where two or more keys are hashed to the same bucket
• See more at https://en.wikipedia.org/wiki/Hash_table

Package hash implements a hash table.

Index

• type Hash
  • func New() *Hash
  • func (h *Hash) Delete(key string) error
  • func (h *Hash) Do(fn func(key string, value int) bool)
  • func (h *Hash) Len() int
  • func (h *Hash) Retrieve(key string) (int, error)
  • func (h *Hash) Store(key string, value int)

Types

type Hash

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

Hash is a simple Hash table implementation.

func New

func New() *Hash

New returns a new hash table.

func (*Hash) Delete

func (h *Hash) Delete(key string) error

Delete deletes an entry from the hash table.

func (*Hash) Do

func (h *Hash) Do(fn func(key string, value int) bool)

Do calls fn on each key/value. If fn return false stops the iteration.

func (*Hash) Len

func (h *Hash) Len() int

Len return the number of elements in the hash. This function currently uses a linear traversal but could be improved with meta-data.

func (*Hash) Retrieve

func (h *Hash) Retrieve(key string) (int, error)

Retrieve extracts a value from the hash table based on the key.

func (*Hash) Store

func (h *Hash) Store(key string, value int)

Store adds a value in the hash table based on the key.