القواميس و Map في TypeScript

Введение: Почему словари — это суперсила программиста

Представьте, что вы — библиотекарь, и вам нужно найти книгу «Война и мир». Если книги расставлены в алфавитном порядке по фамилии автора, вы быстро найдете нужную полку. А если книги свалены в кучу? Придется перебирать каждую — это медленно и утомительно. В программировании мы постоянно сталкиваемся с такой задачей: нужно хранить данные и быстро их находить по какому-то ключу (имени, ID, номеру).

Для этого существуют словари (они же ассоциативные массивы или Map). В TypeScript и JavaScript мы используем встроенный объект Map, а также обычные объекты {} в роли словарей. Под капотом большинства современных языков программирования (включая Node.js) словари реализованы через хеш-таблицы — гениальную структуру данных, которая позволяет находить элементы за постоянное время O(1) в среднем случае.

В этой статье мы разберем, как работают словари и хеш-таблицы, научимся использовать Map в TypeScript 5, напишем свою упрощенную хеш-таблицу и рассмотрим практические примеры для Node.js.

Основные концепции: Ключи, значения и магия хеширования

Что такое словарь (ассоциативный массив)?

Словарь — это коллекция, которая хранит пары «ключ — значение». Каждый ключ уникален. Вы «просите» словарь дать значение по ключу, и он мгновенно его возвращает (если такой ключ есть).

Хеш-таблица: как она работает?

Хеш-таблица — это массив (обычный список), но с хитрым способом индексации. Когда мы добавляем пару "ключ" → "значение", происходит следующее:

1. Хеш-функция принимает ключ (строку, число, объект) и вычисляет для него целое число — хеш-код. Хорошая хеш-функция для разных ключей дает разные числа (минимизирует коллизии).
2. Хеш-код преобразуется в индекс массива (обычно через операцию остатка от деления на размер массива).
3. По этому индексу в массиве сохраняется наша пара (или ссылка на нее).

Когда мы хотим получить значение по ключу, хеш-функция снова вычисляет хеш, мы получаем тот же индекс и мгновенно извлекаем данные. Никакого перебора!

Коллизии: что делать, если два ключа дали один индекс?

Идеальных хеш-функций не существует. Рано или поздно два разных ключа дадут одинаковый индекс. Это называется коллизией. Самый распространенный способ решения — метод цепочек: в каждой ячейке массива хранится не одно значение, а связный список (или массив) всех пар, попавших в этот индекс. При поиске мы проходим по цепочке и сравниваем ключи.

В современных движках JavaScript (V8 в Node.js) хеш-таблицы реализованы гораздо сложнее: они динамически расширяются, используют открытую адресацию и оптимизированы под реальные сценарии. Но базовая идея остается той же.

Словари в TypeScript 5: Map и Object

В TypeScript (и JavaScript) есть два основных способа создать словарь: обычный объект {} и специализированная структура Map.

Объект как словарь (Record)

Объекты в JS исторически использовались как словари. В TypeScript для этого есть тип Record.

// Объект как словарь: ключи — строки, значения — числа
const scores: Record<string, number> = {
    "Alice": 95,
    "Bob": 82,
    "Charlie": 91
};

// Доступ по ключу
console.log(scores["Alice"]); // 95

// Добавление нового ключа
scores["Diana"] = 88;

// Проверка существования ключа
if ("Bob" in scores) {
    console.log("Bob есть в списке");
}

// Удаление
delete scores["Charlie"];

Минусы объекта как словаря:

• Ключи могут быть только строками или символами (числа автоматически преобразуются в строки).
• Объект имеет прототип, поэтому есть «опасные» ключи вроде toString, constructor.
• Нет встроенного метода для получения количества элементов (нужно Object.keys(obj).length).
• Итерация не гарантирует порядок (хотя в ES6+ порядок строковых ключей сохраняется в порядке добавления).

Map — правильный словарь

Map — это специализированная коллекция для хранения пар ключ-значение, лишенная недостатков объекта.

// Создание Map
const userRoles = new Map<string, string>();

// Добавление элементов
userRoles.set("user1", "admin");
userRoles.set("user2", "editor");
userRoles.set("user3", "viewer");

// Получение значения
const role = userRoles.get("user1"); // "admin"

// Проверка наличия ключа
if (userRoles.has("user2")) {
    console.log("user2 существует");
}

// Количество элементов
console.log(userRoles.size); // 3

// Удаление
userRoles.delete("user3");

// Перебор всех пар
userRoles.forEach((value, key) => {
    console.log(`${key}: ${value}`);
});

// Очистка всего Map
userRoles.clear();

Преимущества Map:

• Ключи могут быть любого типа: строки, числа, объекты, функции.
• Гарантированный порядок вставки (при итерации элементы идут в том порядке, в котором были добавлены).
• Нет прототипных ключей.
• Встроенное свойство size.
• Лучшая производительность при частых добавлениях/удалениях.

Когда использовать Object, а когда Map?

• Object — когда ключи — строки, структура фиксирована (например, конфигурация), нужен синтаксис obj.key.
• Map — когда ключи динамические, нестроковые, нужен частый перебор или операции с размером.

Примеры кода: от простого к сложному

Пример 1: Подсчет частоты слов (классическая задача)

function countWords(text: string): Map<string, number> {
    const wordCount = new Map<string, number>();
    const words = text.toLowerCase().split(/\s+/);

    for (const word of words) {
        // Если слово уже есть — увеличиваем счетчик, иначе устанавливаем 1
        wordCount.set(word, (wordCount.get(word) || 0) + 1);
    }

    return wordCount;
}

const text = "hello world hello TypeScript world hello";
const result = countWords(text);
console.log(result);
// Map(3) { 'hello' => 3, 'world' => 2, 'typescript' => 1 }

Пример 2: Кеширование результатов (мемоизация)

Хеш-таблицы идеальны для кеширования. Допустим, у нас есть дорогая функция вычисления факториала:

function createCachedFactorial(): (n: number) => number {
    const cache = new Map<number, number>();

    return function factorial(n: number): number {
        if (n <= 1) return 1;

        if (cache.has(n)) {
            console.log(`Извлекаем из кеша: ${n}!`);
            return cache.get(n)!;
        }

        const result = n * factorial(n - 1);
        cache.set(n, result);
        console.log(`Вычисляем и кешируем: ${n}!`);
        return result;
    };
}

const cachedFactorial = createCachedFactorial();
console.log(cachedFactorial(5)); // Вычисляем и кешируем: 5! -> 120
console.log(cachedFactorial(5)); // Извлекаем из кеша: 5! -> 120 (мгновенно)

Пример 3: Работа с объектами в качестве ключей

В Map можно использовать объекты как ключи — это невозможно с обычными объектами:

interface User {
    id: number;
    name: string;
}

const userCache = new Map<User, string>();

const user1: User = { id: 1, name: "Alice" };
const user2: User = { id: 2, name: "Bob" };

userCache.set(user1, "Активен");
userCache.set(user2, "В ожидании");

// Поиск по объекту (по ссылке)
console.log(userCache.get(user1)); // "Активен"

// Важно: два одинаковых по структуре объекта — это разные ключи!
const user1Copy: User = { id: 1, name: "Alice" };
console.log(userCache.get(user1Copy)); // undefined (другая ссылка)

Практика: Создаем свою хеш-таблицу в TypeScript

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

class SimpleHashTable<K, V> {
    private buckets: Array<Array<[K, V]>>;
    private capacity: number;
    private _size: number = 0;

    constructor(capacity: number = 10) {
        this.capacity = capacity;
        this.buckets = new Array(capacity).fill(null).map(() => []);
    }

    // Простая хеш-функция для строк и чисел
    private hash(key: K): number {
        let hash = 0;
        const keyStr = String(key);
        for (let i = 0; i < keyStr.length; i++) {
            hash = (hash * 31 + keyStr.charCodeAt(i)) % this.capacity;
        }
        return hash;
    }

    // Добавление или обновление пары
    set(key: K, value: V): void {
        const index = this.hash(key);
        const bucket = this.buckets[index];

        // Ищем, есть ли уже такой ключ в цепочке
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket[i][1] = value; // Обновляем значение
                return;
            }
        }

        // Если ключа нет — добавляем новую пару
        bucket.push([key, value]);
        this._size++;
    }

    // Получение значения по ключу
    get(key: K): V | undefined {
        const index = this.hash(key);
        const bucket = this.buckets[index];

        for (const [storedKey, storedValue] of bucket) {
            if (storedKey === key) {
                return storedValue;
            }
        }
        return undefined;
    }

    // Проверка наличия ключа
    has(key: K): boolean {
        return this.get(key) !== undefined;
    }

    // Удаление по ключу
    delete(key: K): boolean {
        const index = this.hash(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket.splice(i, 1);
                this._size--;
                return true;
            }
        }
        return false;
    }

    get size(): number {
        return this._size;
    }
}

// Тестируем нашу хеш-таблицу
const ht = new SimpleHashTable<string, number>();
ht.set("apple", 5);
ht.set("banana", 3);
ht.set("cherry", 8);

console.log(ht.get("apple"));   // 5
console.log(ht.get("banana"));  // 3
console.log(ht.has("cherry"));  // true
console.log(ht.size);           // 3

ht.set("apple", 10);            // Обновляем
console.log(ht.get("apple"));   // 10

ht.delete("banana");
console.log(ht.has("banana"));  // false
console.log(ht.size);           // 2

Наша реализация проста, но она демонстрирует ключевые принципы: хеш-функцию, массив корзин (buckets) и цепочки для коллизий. В реальном Map из TypeScript/JavaScript все гораздо сложнее и эффективнее, но идея та же.

Итог: что нужно запомнить

• Словарь (Map) —