Продолжаю конспекты "Golang для профи" Михалиса Цукалоса. Ниже конспект основных мыслей по нескольким темам из главы про структуры данных.

Пользовательские хеш-таблицы.
Хеш-таблица - стуктура данных, хранящая пары вида ключ-значение, где ключ определяется функцией, вычисляющей местоположение очередного добавляемого элемента.
Реализация, предложенная автором - https://github.com/PacktPublishing/Mastering-Go-Second-Edition/blob/master/ch05/hashTable.go
Одно из преимуществ хеш-таблиц - ключом может быть что угодно, в отличии от массива или слайса, где ключом может быть только положительное целое число.
Основное преимущество пользовательских хеш-таблиц - ассимптотика поиска: если хеш-таблица имеет n ключей и k блоков, то скорость поиска будет О(n/k), вместо обычной линейной О(n). Это кажется незначительным, но для массива хешей, состоящего из 20 блоков, время поиска сократится в 20 раз, что даёт очень хороший выигрыш для приложений-словарей и приложений, где нужно искать большие объёмы данных.

Реализацию пользовательского связного и двусвязного списка, очереди и стека я пропущу, и перейду сразу к интересному: стандартному go-пакету container, предоставляющему три стуктуры данных: кучу, список и кольцо. Для справки: кольцо - циклический список, где последний элемент ссылается на первый.

Пакет container/heap реализует кучу - дерево, где значение каждого узла является наименьшим элементом в его поддереве. Но, чтобы реализовать дерево кучи в go, необходимо определить операцию сравнения, чтобы понять, какой из двух элементов меньше (т.к. элементом может быть что угодно, не только числа). Для реализации такой возможности пакет container/heap предоставляет интерфейс container/heap.Interface, который опеределяется как:

type Interface struct {
  sort.Interface
  Push(x interface{})
  Pop() interface{}
}  

Для интерфейса sort.Interface, в свою очередь, требуется реализовать методы Len(), Less() и Swap().
И, кажется, это очень удобно: реализовав эти методы для наших структур или типов, мы получим возможность сортировать, менять местами и использовать элементы в рамках кучи.
Реализация, предложенная автором - https://github.com/PacktPublishing/Mastering-Go-Second-Edition/blob/master/ch05/conHeap.go
Пример показывает, что работы, которая требуется для реализации этого интерфейса, требуется проделать совсем немного.