Думаете, хеш-карты нельзя отсортировать? Еще как можно!

Хеш-карты  —  невероятно полезная структура данных. Сопоставляя уникальные ключи с потенциально неуникальными значениями, они имеют постоянное время поиска O(1) и применяются в самых разных ситуациях.

Но есть и недостаток: обычно их нельзя сортировать. В современных языках программирования эту проблему решают по-разному. Так, в Python (начиная с версии 3.7) появилась сортировка хеш-карты с помощью лямбда-функции.

А на Go используют обычные интерфейсы и пакет sort. Интерфейс sort работает с различными структурами данных, в том числе хеш-картами: получается элегантная сортировка в несколько простых этапов.

1. Создаем пользовательские типы для представления пар и их списков

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

В структуре Pair свойства Key (ключ) и Value (значение) соответствуют базовым типам, находящимся в хеш-карте. Например, если хеш-карта инициализирована как map[string]bool{}, то ее Key будет с базовым типом string, а Value  —  с базовым типом bool.

В нашем случае Key и Value будут одного базового типа int:

type Pair struct {
    Key int
    Value int
}

type PairList []Pair

Затем определим type PairList, т. е. просто массив структур Pair.

2. В структуре данных «pair list» реализуем «sort.Interface»

Определив пользовательские структуры, реализуем в структуре PairList интерфейс sort.Interface. Согласно документации Golang, у него три открытых метода для реализации: Len(), Less() и Swap().

type Interface interface {
	// Len — это количество элементов в коллекции.
	Len() int

	// Less сообщает, должен ли элемент с индексом i
	// выполнять сортировку раньше элемента с индексом j.
	//
	// Когда Less(i, j) и Less(j, i) дают false,
	// элементы с индексами i и j считаются эквивалентными.
	// При сортировке Sort эквивалентные элементы в конечном результате располагаются в любом порядке,
	// при Stable исходный порядок ввода эквивалентных элементов сохраняется.
	//
	// Less должен описывать транзитивное упорядочение:
	//  - когда Less(i, j) и Less(j, k) дают true, то Less(i, k) тоже должен быть true.
	//  - когда Less(i, j) и Less(j, k) дают false, то Less(i, k) тоже должен быть false.
	//
	// Обратите внимание: сравнение значений с плавающей запятой (оператор < в значениях float32 или float64)
	// не является транзитивным упорядочением, когда задействуются нечисловые значения (NaN).
	// Для корректной реализации значений с плавающей запятой см. Float64Slice.Less.
	Less(i, j int) bool

	// Swap меняет местами элементы с индексами i и j.
	Swap(i, j int)
}

Чтобы добавить сортировку к любому объекту, реализуем в нем эти три метода и вызываем sort.Sort().

В нашем случае реализуем их в структуре PairList:

func (p PairList) Len() int { return len(p) }
func (p PairList) Less(i, j int) bool { return p[i].Value < p[j].Value }
func (p PairList) Swap(i, j int){ p[i], p[j] = p[j], p[i] }

Реализации простые, но их всегда можно настроить под себя. Хотите отсортировать по Key, а не по Value? Просто внесите соответствующее изменение в реализацию метода Less(). А хотите отсортировать в порядке убывания? Тогда поменяйте местами i и j. Все возможно благодаря интерфейсам Go.

3. Преобразуем карту в «pair list», отсортировываем и возвращаем «pair list»

Для примера сортировки инициализируем someMap и определяем pairList новым экземпляром PairList, равным по длине с someMap.

Перебираем someMap и присваиваем индекс для каждой пары ключ (k)  —  значение (v) нового экземпляра Pair внутри someMap.

Вызываем sort.Sort() в pairList.

someMap := map[int]int{
    0: 2,
    3: 7,
    9: 3,
    1: 5,
    7: 6,
}
pairList := make(PairList, len(someMap))

pairListIdx := 0
for k, v := range(someMap) {
    pairList[pairListIdx] = Pair{k,v}
    pairListIdx++
}

fmt.Println(someMap)
fmt.Println("Unsorted PairList:", pairList)
sort.Sort(pairList)
fmt.Println("Sorted PairList:", pairList)

Запустив этот код в функции, получим вывод:

map[0:2 1:5 3:7 7:6 9:3]
Unsorted PairList: [{1 5} {7 6} {0 2} {3 7} {9 3}]
Sorted PairList: [{0 2} {9 3} {1 5} {7 6} {3 7}]

Теперь вы умеете реализовывать интерфейс sort.Sort в любой структуре данных как настоящий профессионал на Go.

Читайте также:

• WebAssembly на Golang с нуля
• Составные типы данных на Golang
• Обработка сигналов в операционных системах семейства Unix на Golang

Читайте нас в Telegram, VK и Яндекс.Дзен

---

Перевод статьи Israel Miles: Think You Can’t Sort a Hash Map? Think Again!