Простейшая реализация HashMap на Go

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

Об устройстве хэш карты

В данном примере мы будем рассматривать хэш-карту на базе функции хеширования Пирсона. Данная функция имеет на выходе число типа uint8, как следствие мы можем использовать 256 ячеек памяти для хранения результата на базе ключа. Однако есть такой недостаток хэш-функций как коллизии. Тут в дело вступают связные списки. Условимся, что наша структура хэш-карты будет иметь в себе массив длинною 256, а каждый из элементов будет являться связным списком.

Разберёмся на примере

Начнём с хэш-функции.
Краткими словами эта функция получающая на вход любое количество байт и возвращающая при этом 1 байт. Её реализация базируется на наборе инструкций (в данном случае сдвиг элемента на номер символа в таблицы ASCII), а так же на 256-байтной таблицы поиска, содержащей перестановку значений от 0 до 255.

var table[256]int = func()[256]int {
  var data [256]int
  rand.Seed(time.Now().Unix())
  for index, _ := range(data) { data[index] = index }
  for index, _ := range(data) {
    rv := rand.Intn(256)
    data[index], data[rv] = data[rv], data[index]
  }
  return data
}()

В начале мы создаём массив из 256 элементов, каждый из которых имеет значение, равное своему индексу, а затем перемешиваем эти элементы в рандомном порядке.

func hash8(message string) int {
  // using global table
  var hash int = len(message)%256

  for _, value := range(message) {
    hash = table[(hash + int(value))%256]
  }

  return hash
}

А вот и реализация алгоритма :)
Рассмотрим её поподробнее. Получая на вход строку, мы декларируем переменную hash равную (длина строки) mod 256, она же и будет служить результатом хэш-функции. Далее итерируя по строке мы присваиваем hash значение равное значение элемента таблицы поиска по индексу (hash + номер в ASCII) mod 256.

Разобравшись с хэш-функцией рассмотрим реализацию самой хэш-карты.

type Node struct {
  key   string
  value string
  next  *Node
}

type List struct {
  head 	*Node
}

type Map struct {
  map_list  [256]*List
  len       int64
}

Как и писалось выше хэш-карта базируется на массиве длинною 256 элементов. Каждый элемент это начало/голова связного списка List, состоящего из узлов Node, которые в свою очередь имеют переменные ключ key и значение value. Помимо того Map имеет переменную len, которая нужна для подсчёта длины карты.

Теперь перейдём к методам. Для начала надо реализовать метода работы связного списка:
1. Вставка элемента
2. Удаление элемента
3. Вывод элементов (в частность ключей)

func (l *List) add(key, val string, m *Map) {
  new_data := &Node{value: val, key: key}
  if l.head == nil {
    l.head = new_data
    m.len++
  } else {
    current := l.head
    for current.next != nil {
      if key == current.key {
        current.value = val
        return
      }
      current = current.next
    }
    if key == current.key {
      current.value = val
      return
    }
    current.next = new_data
    m.len++
  }
}

Для вставки элемента мы проходим по связному списку, при нахождении такого же ключа, как и входного, изменяем значение, в ином случае добавляем в конец новый элемент и увеличиваем счётчик длины на 1.

func (l *List) delete(key string, m *Map) {
  current := l.head
  if current.key == key {
    l.head = l.head.next
    m.len--
    return
  }
  for current.next != nil {
    if current.next.key == key {
      current.next = current.next.next
      m.len--
      return
    }
    current = current.next
  }
  panic("Key is missing!!")
}

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

func (l *List) print() []string {
  var result []string
  current := l.head
  if current != nil {
    result = append(result, current.key)
  }
  for current.next != nil {
    result = append(result, current.next.key)
    current = current.next
  }

  return result
}

Для получения ключей списка мы проходим по нему и собираем все ключи в массив result, а затем возвращаем его.

Следующим шагом необходимо реализовать методы самой структуры Map:
1. Вставка
2. Удаление
3. Получение значения по ключу
4. Получение всех ключей

func (m *Map) insert(key, val string) {
  if m.map_list[hash8(key)] == nil {
    m.map_list[hash8(key)] = &List{}
  }
  m.map_list[hash8(key)].add(key, val, m)
}

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

func (m *Map) delete(key string) {
  elem := m.map_list[hash8(key)]
  if elem == nil { panic("Map is nil!!") }
  if elem.head.key == key && elem.head.next == nil {
    m.map_list[hash8(key)]  = nil
    m.len--
    fmt.Println("+")
  } else if elem.head.next != nil {
    elem.delete(key, m)
  } else {
    panic("Key is missing!!")
  }
}

Для реализации удаления элемента проверяем наличие элемента в массиве по индексу результата хэш-функции:

• Если элемент пустой, то возвращаем ошибку.

• Если есть элемент, но следующего за ним нет, то присваиваем элементу массива nil.

• Если есть элемент и последующий за ним, то вызываем метод delete у элемента массива (который имеет тип *List).

• В ином случае возвращаем ошибку о том, что ключ отсутствует.

func (m *Map) get_value(key string) string {
  if m.map_list[hash8(key)] == nil { panic("Map is nil!!") }

  current := m.map_list[hash8(key)].head
  if current != nil && current.key == key { return current.value }
  for current.next != nil {
    if current.next.key == key { return  current.next.value }
    current = current.next
  }
  panic("Key is missing!!")
}

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

func (m *Map) keys() []string {
  var answer [] string
  for _, data := range(m.map_list) {
    if data != nil { answer = append(answer, data.print()...)}
  }

  return answer
}

Для выгрузки всех ключей мы проходим по всему массиву. Если в элементе есть данные, то дополняем слайс answer результативным слайсом функции print у структуры List.

Итоги

Мы разобрались, как реализовать простую хэш-карту на основе 8-битной хэш-функции Пирсона с помощью языка Go. Рассмотрели краевые случаи всех описанных методов, а так же возникновение коллизии. Сложность данной структуры (как на чтение, так и на запись) я бы оценил в наилучшем случает, как O(1), в наихудшем же случае она доходит до O(n), при возникновении коллизии и формировании связного списка длинною > 1.

Исходный код