HashMap и HashSet

Коллекции со структурным равенством.

Теория

Проблема нативных коллекций

JavaScript Set и Map сравнивают объекты по ссылке, а не по значению:

// Нативный Set — reference equality
const set = new Set()
set.add({ name: "Alice", age: 30 })
set.add({ name: "Alice", age: 30 })
console.log(set.size) // 2 — два "разных" объекта!

// Нативный Map — reference equality для ключей
const map = new Map()
const key1 = { id: 1 }
const key2 = { id: 1 }
map.set(key1, "first")
map.set(key2, "second")
console.log(map.size) // 2 — два "разных" ключа!

Решение в Effect

Effect предоставляет хеш-коллекции с поддержкой structural equality:

Нативные                    Effect

Set (reference eq)    →    HashSet (value eq)
Map (reference eq)    →    HashMap (value eq)

  { name: "Alice" }  ===  { name: "Alice" }    ← false (JS)
  { name: "Alice" }  eq   { name: "Alice" }    ← true  (Effect)

Иммутабельные vs Мутабельные варианты

┌──────────────────┬────────────────────┬────────────────────────┐
│                  │   Immutable        │   Mutable              │
├──────────────────┼────────────────────┼────────────────────────┤
│ Set              │ HashSet<A>         │ MutableHashSet<A>      │
│ Map              │ HashMap<K, V>      │ MutableHashMap<K, V>   │
├──────────────────┼────────────────────┼────────────────────────┤
│ Операции         │ Возвращают новую   │ Изменяют на месте      │
│ Thread-safety    │ Безопасно          │ Нужна осторожность     │
│ Предыдущее сост. │ Сохраняется        │ Теряется               │
│ Подходит для     │ ФП, конкурентность │ Локальные мутации      │
└──────────────────┴────────────────────┴────────────────────────┘

Structural Equality и Hash

Для корректной работы HashSet и HashMap элементы должны реализовывать интерфейсы Equal и Hash. Самый простой способ — использовать модуль Data:

// Data.struct создаёт объекты с Equal и Hash
const alice1 = Data.struct({ name: "Alice", age: 30 })
const alice2 = Data.struct({ name: "Alice", age: 30 })

// Разные ссылки, но равны по значению
console.log(Object.is(alice1, alice2))  // false
console.log(Equal.equals(alice1, alice2)) // true

// HashSet корректно определяет дубликаты
const set = HashSet.empty().pipe(
  HashSet.add(alice1),
  HashSet.add(alice2)
)
console.log(HashSet.size(set)) // 1 — один уникальный элемент

Для примитивных типов (number, string, boolean) structural equality работает автоматически:

const set = HashSet.make(1, 2, 2, 3, 3, 3)
console.log(HashSet.size(set)) // 3 — дубликаты отброшены

HashSet

Создание

// Пустой HashSet
const empty = HashSet.empty<number>()

// Из значений
const set = HashSet.make(1, 2, 3, 4, 5)

// Из Iterable
const fromArray = HashSet.fromIterable([1, 2, 2, 3, 3])
// HashSet(1, 2, 3) — дубликаты убраны

Операции над элементами

const set = HashSet.make(1, 2, 3)

// Добавление (возвращает НОВЫЙ HashSet)
const withFour = HashSet.add(set, 4)
// HashSet(1, 2, 3, 4)

// Удаление
const withoutTwo = HashSet.remove(set, 2)
// HashSet(1, 3)

// Toggle — добавить если нет, убрать если есть
const toggled = HashSet.toggle(set, 2)
// HashSet(1, 3) — 2 был убран

const toggledBack = HashSet.toggle(toggled, 2)
// HashSet(1, 2, 3) — 2 был добавлен обратно

// Проверка наличия
HashSet.has(set, 2) // true
HashSet.has(set, 5) // false

// Размер
HashSet.size(set) // 3

Операции над множествами

const a = HashSet.make(1, 2, 3, 4)
const b = HashSet.make(3, 4, 5, 6)

// Объединение (union): A ∪ B
const union = HashSet.union(a, b)
// HashSet(1, 2, 3, 4, 5, 6)

// Пересечение (intersection): A ∩ B
const intersection = HashSet.intersection(a, b)
// HashSet(3, 4)

// Разность (difference): A - B
const difference = HashSet.difference(a, b)
// HashSet(1, 2)

// Подмножество
HashSet.isSubset(HashSet.make(1, 2), a) // true

Визуализация операций над множествами:

  A = {1, 2, 3, 4}    B = {3, 4, 5, 6}

  Union:        {1, 2, 3, 4, 5, 6}
  Intersection: {3, 4}
  A - B:        {1, 2}
  B - A:        {5, 6}

      ┌───────────┬───────────┐
      │  A only   │  B only   │
      │  {1, 2}   │  {5, 6}   │
      │     ┌─────┤─────┐     │
      │     │ A∩B │     │     │
      │     │{3,4}│     │     │
      │     └─────┤─────┘     │
      └───────────┴───────────┘

Трансформации

// filter
const evens = pipe(
  HashSet.make(1, 2, 3, 4, 5, 6),
  HashSet.filter((n) => n % 2 === 0)
)
// HashSet(2, 4, 6)

// map
const doubled = pipe(
  HashSet.make(1, 2, 3),
  HashSet.map((n) => n * 2)
)
// HashSet(2, 4, 6)

// flatMap
const expanded = pipe(
  HashSet.make(1, 2, 3),
  HashSet.flatMap((n) => HashSet.make(n, n * 10))
)
// HashSet(1, 10, 2, 20, 3, 30)

// partition
const [odds, evenSet] = pipe(
  HashSet.make(1, 2, 3, 4, 5),
  HashSet.partition((n) => n % 2 === 0)
)

// reduce
const sum = HashSet.reduce(
  HashSet.make(1, 2, 3, 4, 5),
  0,
  (acc, n) => acc + n
)
// 15

// forEach
HashSet.forEach(HashSet.make(1, 2, 3), (n) => {
  console.log(n)
})

Получение значений

const set = HashSet.make(1, 2, 3)

// Как Iterator
const iter = HashSet.values(set)

// Как Array
const arr = HashSet.toValues(set)
// [1, 2, 3]

// Iterable протокол — работает с for...of и spread
for (const value of set) {
  console.log(value)
}
const spread = [...set]

some / every — предикаты

const set = HashSet.make(2, 4, 6, 8)

HashSet.some(set, (n) => n > 5)     // true
HashSet.every(set, (n) => n % 2 === 0) // true

Chaining с pipe

const result = pipe(
  HashSet.make(1, 2, 2, 3, 4, 5, 5),
  HashSet.filter((n) => n % 2 === 0),
  HashSet.map((n) => n * 2),
  HashSet.toValues
)
// [4, 8]

MutableHashSet

Мутабельный вариант для случаев, когда нужна производительность при множественных модификациях:

// Создание
const set = MutableHashSet.make(1, 2, 3)

// Добавление — мутирует на месте
MutableHashSet.add(set, 4)
console.log([...set]) // [1, 2, 3, 4]

// Удаление — мутирует на месте
MutableHashSet.remove(set, 1)
console.log([...set]) // [2, 3, 4]

// Очистка
MutableHashSet.clear(set)
console.log(MutableHashSet.size(set)) // 0

Гибридный подход — HashSet.mutate

Для batch-операций можно использовать HashSet.mutate, который создаёт временный мутабельный контекст:

const original = HashSet.make(1, 2, 3)

// Временная мутабельность — оригинал не изменяется
const modified = HashSet.mutate(original, (draft) => {
  HashSet.add(draft, 4)
  HashSet.add(draft, 5)
  HashSet.remove(draft, 1)
})

console.log(HashSet.toValues(original))
// [1, 2, 3] — не изменился

console.log(HashSet.toValues(modified))
// [2, 3, 4, 5]

HashMap

Создание

// Пустой HashMap
const empty = HashMap.empty<string, number>()

// Из пар ключ-значение
const map = HashMap.make(
  ["alice", 30],
  ["bob", 25],
  ["charlie", 35]
)

// Из Iterable пар
const fromEntries = HashMap.fromIterable([
  ["x", 1],
  ["y", 2],
  ["z", 3]
] as const)

Операции CRUD

const map = HashMap.make(
  ["alice", 30],
  ["bob", 25]
)

// GET — возвращает Option
const aliceAge = HashMap.get(map, "alice")
// Some(30)

const unknownAge = HashMap.get(map, "unknown")
// None

// SET — возвращает новый HashMap
const updated = HashMap.set(map, "charlie", 35)
// HashMap(alice→30, bob→25, charlie→35)

// Оригинал не изменён
HashMap.size(map)     // 2
HashMap.size(updated) // 3

// REMOVE
const withoutBob = HashMap.remove(map, "bob")
// HashMap(alice→30)

// HAS
HashMap.has(map, "alice")   // true
HashMap.has(map, "unknown") // false

// SIZE
HashMap.size(map) // 2

Обновление значений

const map = HashMap.make(
  ["alice", 30],
  ["bob", 25]
)

// modify — обновить существующее значение
const modified = HashMap.modify(map, "alice", (age) => age + 1)
// HashMap(alice→31, bob→25)

// modifyHash — обновить с пользовательским хешем

// Условное обновление
const conditionalUpdate = HashMap.modifyAt(map, "charlie", {
  onNone: () => Option.some(0),    // если нет — создать с 0
  onSome: (v) => Option.some(v + 1) // если есть — инкрементировать
})

Трансформации

const scores = HashMap.make(
  ["alice", 85],
  ["bob", 92],
  ["charlie", 78]
)

// map — трансформировать значения
const doubled = HashMap.map(scores, (score) => score * 2)

// filter — фильтровать записи
const highScores = HashMap.filter(scores, (score) => score >= 85)
// HashMap(alice→85, bob→92)

// filterWithIndex — фильтрация с доступом к ключу
const filtered = HashMap.filterWithIndex(scores, (score, name) =>
  name.startsWith("a") && score > 80
)

// reduce — свёртка
const total = HashMap.reduce(scores, 0, (acc, score) => acc + score)
// 255

// forEach
HashMap.forEach(scores, (score, name) => {
  console.log(`${name}: ${score}`)
})

Получение ключей, значений и записей

const map = HashMap.make(
  ["alice", 30],
  ["bob", 25]
)

// Ключи
const keys = HashMap.keys(map)     // IterableIterator<string>
const keyArr = HashMap.keySet(map)  // HashSet<string>

// Значения
const values = HashMap.values(map)  // IterableIterator<number>

// Записи (пары ключ-значение)
const entries = HashMap.toEntries(map)
// Array<[string, number]>

HashMap с объектами-ключами (Data)

// Ключи-объекты должны реализовывать Equal и Hash
const userScores = HashMap.empty<
  Data.Data<{ id: number; name: string }>,
  number
>().pipe(
  HashMap.set(Data.struct({ id: 1, name: "Alice" }), 95),
  HashMap.set(Data.struct({ id: 1, name: "Alice" }), 100) // перезапишет!
)

console.log(HashMap.size(userScores)) // 1

// Получение по значению ключа (а не по ссылке)
console.log(
  HashMap.get(userScores, Data.struct({ id: 1, name: "Alice" }))
)
// Some(100)

MutableHashMap

const map = MutableHashMap.empty<string, number>()

// Все операции мутируют на месте
MutableHashMap.set(map, "alice", 30)
MutableHashMap.set(map, "bob", 25)

console.log(MutableHashMap.size(map)) // 2

MutableHashMap.remove(map, "bob")
console.log(MutableHashMap.size(map)) // 1

Работа с Data модулем

Модуль Data — ключ к эффективному использованию hash-коллекций с объектами:

Data.struct

const person1 = Data.struct({ id: 1, name: "Alice", age: 30 })
const person2 = Data.struct({ id: 1, name: "Alice", age: 30 })

// Value equality
Equal.equals(person1, person2) // true

// В HashSet — один элемент
const set = HashSet.empty().pipe(
  HashSet.add(person1),
  HashSet.add(person2)
)
HashSet.size(set) // 1

Data.tuple

// Кортежи как ключи
const grid = HashMap.empty<Data.Data<readonly [number, number]>, string>().pipe(
  HashMap.set(Data.tuple(0, 0), "origin"),
  HashMap.set(Data.tuple(1, 1), "diagonal")
)

HashMap.get(grid, Data.tuple(0, 0))
// Some("origin")

Data.TaggedEnum

type Shape = Data.TaggedEnum<{
  readonly Circle: { readonly radius: number }
  readonly Square: { readonly side: number }
}>

const { Circle, Square } = Data.taggedEnum<Shape>()

const shapes = HashSet.make(
  Circle({ radius: 5 }),
  Circle({ radius: 5 }),  // дубликат — будет убран
  Square({ side: 10 })
)

HashSet.size(shapes) // 2

Производительность

┌─────────────────────┬──────────────┬────────────────┐
│ Операция            │ HashSet/Map  │ MutableHash*   │
├─────────────────────┼──────────────┼────────────────┤
│ Lookup (has/get)    │ O(1) avg     │ O(1) avg       │
│ Insert (add/set)    │ O(1) avg     │ O(1) avg       │
│ Remove              │ O(1) avg     │ O(1) avg       │
│ Iteration           │ O(n)         │ O(n)           │
│ Union/Intersection  │ O(n)         │ —              │
│ Size                │ O(1)         │ O(1)           │
├─────────────────────┼──────────────┼────────────────┤
│ Обновление          │ Новая копия  │ In-place       │
│ Memory per update   │ O(log n)*    │ O(1)           │
└─────────────────────┴──────────────┴────────────────┘

* Structural sharing снижает реальное потребление памяти

Когда что использовать

HashSet / HashMap:
  • Конкурентный доступ
  • Сохранение истории состояний
  • Функциональные пайплайны
  • Передача между функциями

MutableHashSet / MutableHashMap:
  • Локальное построение коллекции
  • Hot path с частыми обновлениями
  • Изолированный scope

Паттерны использования

Уникальные идентификаторы

const processedIds = HashSet.empty<string>()

const processEvent = (
  processed: HashSet.HashSet<string>,
  eventId: string
): { readonly processed: HashSet.HashSet<string>; readonly isNew: boolean } =>
  HashSet.has(processed, eventId)
    ? { processed, isNew: false }
    : { processed: HashSet.add(processed, eventId), isNew: true }

Инвертированный индекс

type InvertedIndex = HashMap.HashMap<string, HashSet.HashSet<string>>

const addToIndex = (
  index: InvertedIndex,
  docId: string,
  words: ReadonlyArray<string>
): InvertedIndex =>
  words.reduce(
    (acc, word) =>
      HashMap.modifyAt(acc, word, {
        onNone: () => HashSet.make(docId),
        onSome: (docs) => HashSet.add(docs, docId)
      }),
    index
  )

Кеширование с HashMap

type Cache<K, V> = HashMap.HashMap<K, V>

const cacheGet = <K, V>(
  cache: Cache<K, V>,
  key: K
): { readonly cache: Cache<K, V>; readonly hit: boolean; readonly value: V | undefined } => {
  const result = HashMap.get(cache, key)
  return result._tag === "Some"
    ? { cache, hit: true, value: result.value }
    : { cache, hit: false, value: undefined }
}

const cacheSet = <K, V>(
  cache: Cache<K, V>,
  key: K,
  value: V
): Cache<K, V> => HashMap.set(cache, key, value)

Упражнения

import { HashSet } from "effect"

const countUniqueWords = (text: string): number => {
  // Ваш код
}

// countUniqueWords("the cat sat on the mat") → 5

import { HashMap } from "effect"

const wordFrequency = (text: string): HashMap.HashMap<string, number> => {
  // Ваш код
}

// wordFrequency("a b a c b a") → HashMap(a→3, b→2, c→1)

import { HashMap, HashSet, Option, pipe } from "effect"

type Graph<V> = HashMap.HashMap<V, HashSet.HashSet<V>>

const emptyGraph = <V>(): Graph<V> => HashMap.empty()

// Добавить ребро (неориентированное)
const addEdge = <V>(graph: Graph<V>, from: V, to: V): Graph<V> => {
  // Ваш код
}

// Получить соседей
const neighbors = <V>(graph: Graph<V>, vertex: V): HashSet.HashSet<V> => {
  // Ваш код
}

// BFS — найти путь
const bfs = <V>(graph: Graph<V>, start: V, end: V): Option.Option<ReadonlyArray<V>> => {
  // Ваш код
}