Implementing a Hash Map in Golang

A fairly frequent interview question is: “How to implement a hash table?”. The question might also sound like this: “What to do if the language doesn’t have this data structure, how to implement it?”. And besides, it’s always interesting to figure out how it works under the hood. So, let’s start with theory.

Theory #

A Hash Function is a function that takes data of arbitrary length as input and outputs data of fixed length. Ideally, the output values should also be unique. The case where the output value of a function matches for different input arguments is called a collision.

In general, to implement a hash table, we need to create a data structure containing buckets (a list of key-value elements to resolve collisions). The index of the current element is calculated in the hash function. We will use a simple XOR, however, in real systems, this function is implemented more complexly.

Implementation #

Let’s define the structure of our hashmap. We will store its size, as well as a list of buckets. Each bucket, in turn, will be a slice containing elements with the structure [key, value].

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

func NewHashMap(size int) *HashMap {
    return &HashMap{
        buckets: make([][][]string, size),
        size:    size,
    }
}

Let’s implement a function that finds an index by key. We will implement it via XOR. We will take the result modulo the array size so that the index does not go out of bounds.

func (h *HashMap) XORHash(src []byte) int {
    hash := 0
    for _, c := range src {
        hash = hash ^ int(c)
    }
    return hash % h.size
}

Let’s implement the add method. To do this, we calculate the hash sum, then add the received key/value pair to the bucket at the found index.

func (h *HashMap) Set(key string, value string) {
    index := h.XORHash([]byte(key))
    insertedKeyVal := []string{key, value}

    // Check if such a key already exists to update the value
    for i, kv := range h.buckets[index] {
        if kv[0] == key {
            h.buckets[index][i] = insertedKeyVal
            return
        }
    }

    h.buckets[index] = append(h.buckets[index], insertedKeyVal)
}

For the get method, we will return the found value, as well as a flag indicating whether anything was found. To do this, we get the index via the XORHash function and iterate through the bucket containing the list of key/value pairs. If a key match is found, we return the result with the true flag, otherwise — false.

func (h *HashMap) Get(key string) (string, bool) {
    index := h.XORHash([]byte(key))

    for _, kv := range h.buckets[index] {
        if kv[0] == key {
            return kv[1], true
        }
    }

    return "", false
}

The delete method is very similar to the get method, only the operation differs: we delete the element (slice) by index from the bucket.

func (h *HashMap) Del(key string) bool {
    index := h.XORHash([]byte(key))

    for i, kv := range h.buckets[index] {
        if kv[0] == key {
            // Delete the element from the slice, preserving order (or not, it doesn't matter here)
            h.buckets[index] = append(h.buckets[index][:i], h.buckets[index][i+1:]...)
            return true
        }
    }

    return false
}

The result can be touched in the sandbox Go Playground (code may differ).