Множина через map[T]struct{} і лічильники

1. Два патерни для map: множина та лічильник

Коли ви вперше бачите map, хочеться сприймати його буквально: «ключ → значення». Але в реальному коді map часто працює як універсальний механізм обліку. Він швидко відповідає на запитання «чи бачив я це раніше?» і «скільки разів це траплялося?». Саме тому в Go на мапах будують багато речей, які в інших мовах винесені в окремі структури.

Уявіть, що ви пишете невелику консольну утиліту: користувач вводить слова або теги, а програма має: (а) показати список унікальних значень і (б) порахувати частоти. Можна, звісно, зберігати все в зрізі (slice) і щоразу лінійно шукати збіг, але тоді програма почне гальмувати вже на сотнях елементів. map розв’язує обидва завдання елегантно, і сьогодні ми навчимося впевнено читати й писати такий код.

Для орієнтира — коротка таблиця «що ми хочемо отримати»:

map[string]struct{}

_, ok := set[x]

map[string]int

counts[x]

v, ok := counts[x]

2. Множина: map[T]struct{}

Якщо ви зі світу мов, де є готовий Set, то Go спочатку може здатися «жадібним»: мовляв, чому мені знову все робити самому? Насправді Go не жадібний, а мінімалістичний. Базовий map настільки зручний, що з нього виходить чудова множина без магії та без нових правил. Ви отримуєте структуру даних, яку вже вмієте створювати, обходити й очищати.

Ідея множини проста: нам не потрібно зберігати значення, нам потрібен лише факт — елемент присутній чи ні. Отже, як значення (V) можна використати тип, який нічого не зберігає. У Go такий тип є: порожня структура struct{}. У неї немає полів, і її часто використовують як маркер «просто щоб було».

Мінімальний приклад множини

package main

import "fmt"

func main() {
	set := make(map[string]struct{})
	set["go"] = struct{}{}
	set["map"] = struct{}{}

	fmt.Println(len(set)) // 2
}

Тут struct{}{} — це «порожнє значення». Ми кладемо його лише тому, що map вимагає значення, але сенс несе ключ.

Операції множини: add/has/remove/size

Коли ви бачите map[string]struct{} у чужому коді, не намагайтеся шукати, що там зберігається. Там зберігається «нічого», і в цьому весь сенс. Думайте про це як про таблицю «присутній/відсутній». Тоді операції множини читаються майже як у звичайній мові: «додай», «перевір», «видали», «порахуй».

Ось компактний набір операцій, який ви будете писати постійно:

package main

import "fmt"

func main() {
	tags := make(map[string]struct{})

	tags["urgent"] = struct{}{}     // додати
	_, ok := tags["urgent"]         // перевірити
	delete(tags, "urgent")          // видалити
	fmt.Println(ok, len(tags))      // true 0
}

Зверніть увагу: delete(tags, "urgent") безпечний навіть тоді, коли ключа немає: він просто нічого не зробить. Це дуже зручно — менше перевірок, менше місць, де можна помилитися.

Чому не map[string]bool

Логічне запитання новачка: «А чому множину не зробити як map[string]bool?» Адже можна зберігати true/false. Можна. Але це менш виразно й іноді гірше читається. Головна проблема в тому, що false — звичайне значення, і його легко сплутати із ситуацією, коли ключа немає.

Подивіться на приклад: він компілюється, але логічно може заплутати вас через тиждень або навіть через дві години.

package main

import "fmt"

func main() {
	m := map[string]bool{"featureA": false}

	fmt.Println(m["featureA"]) // false (ключ є, значення false)
	fmt.Println(m["featureB"]) // false (ключа немає, нульове значення)
}

Обидва рази друкується false, але сенс різний. Ви, звісно, можете застосовувати ok-ідіому й тут, але тоді виникає питання: навіщо взагалі bool? Якщо ми будуємо множину, то map[string]struct{} прямо каже читачеві: «я — множина», і зменшує шанс, що хтось напише if m[x] { ... } та випадково переплутає «немає ключа» з «ключ є, але false».

3. Лічильники й частоти: map[string]int

Ще один дуже корисний патерн для map — це лічильник. Він настільки поширений, що трапляється в задачах з алгоритмів, в обробці логів, в аналітиці, під час імпорту даних і навіть у найзвичайніших CLI-програмах. І тут нам допомагає те, що ми вже знаємо: якщо ключа немає, читання повертає нульове значення (zero value).

У int нульове значення — це 0. Отже, запис counts[word]++ працює навіть тоді, коли word трапляється вперше: спочатку береться 0, потім додається 1, а потім значення записується назад у map.

Мініприклад частот

package main

import "fmt"

func main() {
	words := []string{"go", "map", "go"}

	counts := make(map[string]int)
	for _, w := range words {
		counts[w]++
	}

	fmt.Println(counts["go"])   // 2
	fmt.Println(counts["java"]) // 0
}

І тут важливо не зробити неправильний висновок: 0 не означає «ключ точно був». Це означає: або ключа не було, або значення дорівнює 0. Якщо вам потрібно розрізняти ці випадки, повертаємося до ok-ідіоми.

Коли все-таки потрібен ok

У простому лічильнику частот 0 майже завжди підходить. Але бувають ситуації, коли 0 — це реальне значення. Наприклад, ви зберігаєте поточний баланс бонусів, і він може стати нульовим після списання. Або ви зберігаєте кількість доступних спроб, і 0 означає: «ключ є, але спроб немає». У таких випадках корисно вміти відрізняти відсутність ключа.

Короткий приклад з ok-ідіомою для map[string]int:

package main

import "fmt"

func main() {
	counts := map[string]int{"go": 0}

	v1, ok1 := counts["go"]
	v2, ok2 := counts["java"]

	fmt.Println(v1, ok1) // 0 true
	fmt.Println(v2, ok2) // 0 false
}

Ця перевірка особливо допомагає, коли ви пишете код «видалити ключ, якщо значення стало 0». Це не обов’язкове правило, але іноді воно робить дані охайнішими: менше ключів із нульовими значеннями.

4. Приклад: мініутиліта TagStats

Зараз ми зберемо все в одну невелику консольну програму. Вона буде простою: ми ще не вміємо зручно зчитувати рядки з пробілами цілком, тому зчитуємо «токени». Зате дуже чесною: користувач вводить n, потім n тегів. Програма виводить кількість унікальних тегів і частоти кожного тега.

Читаємо введення в []string

Спочатку прочитаємо введення в []string. Зверніть увагу: ми заздалегідь виділяємо місткість зрізу — ви вже робили це в темі про make і append.

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	tags := make([]string, 0, n)
	for i := 0; i < n; i++ {
		var t string
		fmt.Scan(&t)
		tags = append(tags, t)
	}

	fmt.Println(tags) // приклад: [go map go]
}

Будуємо set і лічильник поверх одних даних

Тепер поверх цих даних побудуємо одночасно і множину унікальних тегів, і лічильник:

unique := make(map[string]struct{})
counts := make(map[string]int)

for _, t := range tags {
	unique[t] = struct{}{}
	counts[t]++
}

fmt.Println("унікальних:", len(unique)) // унікальних: 2

Поки що ми вивели лише кількість унікальних тегів. Але хочеться ще показати самі частоти.

Стабільний вивід: сортуємо ключі

Порядок у map не гарантується, тому для красивого й повторюваного результату ми збираємо ключі та сортуємо їх.

package main

import (
	"fmt"
	"sort"
)

func main() {
	counts := map[string]int{"go": 2, "map": 1}

	keys := make([]string, 0, len(counts))
	for k := range counts {
		keys = append(keys, k)
	}
	sort.Strings(keys)

	for _, k := range keys {
		fmt.Println(k, counts[k])
	}
	// go 2
	// map 1
}

Якщо зібрати все разом, вийде маленький застосунок, який у наступних темах справді можна буде розширювати: наприклад, зберігати завдання і теги завдань. Поки що без структур ми обмежені в моделюванні даних, але вже зараз можемо робити корисну аналітику на основі рядків.

Схема потоку даних

Невелика схема потоку даних, щоб мозок не вдавав із себе nil-мапу:

flowchart TD
    A[Читаємо n тегів] --> B[Для кожного тега t]
    B --> C["unique[t] = struct{}{}"]
    B --> D["counts[t]++"]
    C --> E["Кількість унікальних = len(unique)"]
    D --> F[Ключі counts -> sort -> друк]

5. Обмеження ключів: що можна класти в map і set

Іноді здається, що map — це магічний мішок, куди можна покласти будь-які ключі: рядки, числа, будь-які речі. Але в map є важливе обмеження: ключ має бути таким, щоб його можна було порівнювати й хешувати. Людською мовою це означає: ключ має бути порівнюваним і підтримувати ==/!= без сюрпризів. Тому, наприклад, зрізи не можна використовувати як ключі.

Є навіть сценарії, де ключ на вигляд підходить, але під час спроби використати непорівнюваний тип програма падає з повідомленням на кшталт "hash of unhashable type []int". У межах нашого курсу достатньо запам’ятати просте правило: для множин і лічильників із сьогоднішньої лекції беріть ключами string або int — і матимете спокійне життя без несподіваних panic.

6. Типові помилки

Помилка №1: робити множину як map[string]bool і перевіряти через if set[x] { ... }.
Такий код інколи «працює», але його важко читати, і він легко ламається, якщо хтось почне зберігати false як осмислене значення. Якщо ви справді хочете множину, map[string]struct{} краще виражає намір: наявність елемента перевіряють через _, ok := set[x], і це не плутається зі значеннями.

Помилка №2: намагатися перевіряти відсутність ключа в лічильнику через if counts[k] == 0.
Для частот це часто допустимо, але логічно це означає не «ключа немає», а «значення зараз 0». Якщо вам важливо розрізняти «не було взагалі» і «було, але стало 0», використовуйте v, ok := counts[k]. Це ж правило рятує в ситуаціях, коли ви хочете видаляти ключі з нулем і не впевнені, чи вони взагалі були присутні.

Помилка №3: забути make і писати в nil-map.
var set map[string]struct{} виглядає нормально, і читання з такої мапи не впаде. Але щойно ви зробите set["x"] = struct{}{}, програма впаде під час виконання. Тому практичне правило просте: якщо ви збираєтеся додавати елементи, створюйте мапу через make(...) до першого запису.

Помилка №4: очікувати «гарний порядок» під час виведення лічильника через for k, v := range counts.
Порядок обходу map не є контрактом; він може змінюватися. Через це тести, порівняння виводів і навіть проста перевірка очима стають мукою. Якщо ви виводите результати користувачеві й хочете стабільності, використовуйте вже знайомий рецепт: зібрати ключі в зріз, відсортувати й друкувати за ключами.

Помилка №5: зберігати в множині не те, що перевіряєте.
Звучить смішно, але трапляється часто: ви додаєте в множину рядки в одному форматі (наприклад, з різним регістром: "Go" і "go"), а перевіряєте в іншому — і «чомусь не знаходиться». Якщо ви будуєте множину за рядками, приведіть їх до єдиного вигляду заздалегідь (хоча б strings.ToLower) і лише потім кладіть у map[string]struct{}.

1

Опитування

Map, рівень 15, лекція 4

Недоступний

Map

Map: ok‑ідіома, set‑патерн

Відкрити