0

Write a hashmap in Go

 2 years ago
source link: https://dannypsnl.github.io/blog/2019/04/04/cs/write-hashmap-in-go/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Write a hashmap in Go

Just a note

Hash map is a data structure that helps you associate a key type to a value type. For example, a string map to the boolean value.

I choose an easy way to create one, that's an array to a list. The type definition was:

type Node struct {
    key   string
    value interface{}
}

type HashMap struct {
    size    int
    buckets [][]Node
}

buckets stores a list of list of Node, Node is a key/value pair. The principle of this implementation is the hash function would uniform the index of the bucket, the reason for the bucket is a list is because if we have the same hash for a different key, then we append the new Node into the same bucket or update if it exists in the bucket, that's why we have to store the key/value pair.

size is the length of buckets, but we aren't going to count it every time, so we store it in the structure.

Jenkins Hash

reference: https://en.wikipedia.org/wiki/Jenkins_hash_function

// uint32 at here is very important,
// since Go using int to index slice([]T),
// at 64-bits system uint would be uint64 and would overflow while
// we convert hash value to int(would be int64 in this context).
// So we pick uint32 for 64-bits system(my test environment)
func JenkinsHash(key string) uint32 {
    var h uint32
    for _, c := range key {
        h += uint32(c)
        h += (h << 10)
        h ^= (h >> 6)
    }
    h += (h << 3)
    h ^= (h >> 11)
    h += (h << 15)
    return h
}

could try to extend the definition, using others type than string for hashing

Get and Set

// getIndex is a help function for Get and Set
func (h *HashMap) getIndex(k string) int {
    return int(JenkinsHash(k)) % h.size
}

func (h *HashMap) Get(k string) interface{} {
    index := h.getIndex(k)
    bucket := h.buckets[index]
    // linear searching the node in bucket,
    // because the bucket should be a small list,
    // so it should not take too long time.
    // This is why hash function and size of buckets does important
    for _, node := range bucket {
        if node.key == k {
            return node.value
        }
    }
    return nil
}

func (h *HashMap) Set(k string, v interface{}) {
    index := h.getIndex(k)
    bucket := h.buckets[index]
    for i := range bucket {
        n := &bucket[i]
        if n.key == k { // existed node
            n.value = v
            // early return while updated
            return
        }
    }
    // append into bucket
    h.buckets[index] = append(h.buckets[index], Node{key: k, value: v})
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK