Реализация хеш таблицы на golang.

Достаточно частый вопрос на собеседованиях: “Как реализовать hash таблицу?”. Вопрос также может звучать следующим образом: “Что делать, если в языке нет данной структуры данных, как реализовать?”. Ну и кроме того, всегда интересно разобраться, как же оно работает под капотом. Итак, начнем с теории.

Теория #

Хеш-функция — это функция, принимающая на вход данные произвольной длины и отдающая данные фиксированной длины. В идеале выходные значения также должны быть уникальными. Случай, когда выходное значение функции с разными входными аргументами совпадает, называется коллизией.

В общем случае для реализации хеш-таблицы нам необходимо создать структуру данных, содержащую бакеты (список из элементов ключ-значение, для того чтобы разрешать коллизии). Индекс текущего элемента высчитывается в хеш-функции. Мы будем использовать простой XOR, однако в реальных системах эта функция реализуется сложнее.

Реализация #

Определим структуру нашего хешмапа. Будем хранить его размерность, а также список бакетов. Каждый бакет, в свою очередь, будет слайсом, содержащим элементы со структурой [ключ, значение].

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

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

Реализуем функцию, находящую по ключу индекс. Реализовывать будем через XOR. Результат возьмем по модулю от размера массива, чтобы индекс не вышел за пределы.

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

Реализуем метод добавления. Для этого рассчитаем хеш-сумму, затем полученную пару ключ/значение добавим в бакет по найденному индексу.

func (h *HashMap) Set(key string, value string) {
    index := h.XORHash([]byte(key))
    insertedKeyVal := []string{key, 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)
}

Для метода получения будем возвращать найденное значение, а также флаг, указывающий на то, было ли что-нибудь найдено. Для этого получим индекс через XORHash функцию и проитерируемся по бакету, содержащему список из пар ключ/значение. При нахождении совпадения ключей вернем результат с флагом true, в противном случае — 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
}

Метод удаления очень похож на метод получения, отличается лишь операция: делаем удаление элемента (слайса) по индексу из бакета.

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

    for i, kv := range h.buckets[index] {
        if kv[0] == key {
            // Удаляем элемент из слайса, сохраняя порядок (или нет, здесь не важно)
            h.buckets[index] = append(h.buckets[index][:i], h.buckets[index][i+1:]...)
            return true
        }
    }

    return false
}

Результат можно пощупать в песочнице Go Playground (код может отличаться).