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

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

Теория

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

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

Реализация

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

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

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

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

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

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

Для метода получения будем возвращать найденное значение, а также флаг, указывающий на то, было ли что-нибудь найденно. Для этого, получим индекс через XORHash функцию, реализованную ранее, и проитерируемся по бакету, содержащиму список из пар ключ/значение, при нахождении совпадения ключей, вернем результат с флагом 'найденно', в противном случае, установим флаг в false.

func (h *HashMap) Get(key string) (string, bool) {
  index := h.XORHash([]byte(key))
  if len(h.buckets[index]) == 0 { 
    return "", false
  }

  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))

  if len(h.buckets[index]) == 0 { 
    return false
  }

  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
}

Результат, как и всегда, можно пощупать тут