Хеш-таблицы: секретное оружие, которое делает ваш код в 1000 раз быстрее

Что такое хеш-таблица и зачем она нужна?

Хеш-таблица (hash table, или hash map) — это структура данных, которая хранит пары "ключ-значение" и обеспечивает очень быстрый доступ к данным. В среднем, операции поиска, вставки и удаления выполняются за O(1) — константное время. Это означает, что независимо от того, хранится в таблице 10 или 10 миллионов элементов, доступ к любому из них займёт примерно одинаковое время.

Простой пример из жизни:

const userAges = {
    "Алексей": 28,
    "Мария": 25,
    "Дмитрий": 32
};

console.log(userAges["Мария"]); // 25 - мгновенный доступ!

В большинстве современных языков программирования хеш-таблицы встроены: dict в Python, Map в JavaScript, HashMap в Java, map в Go.

Как устроена хеш-таблица

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

Процесс работы:

1. Хеширование ключа: Ключ (например, "Алексей") пропускается через хеш-функцию, которая возвращает число (например, 42)

2. Вычисление индекса: Результат хеширования преобразуется в индекс массива с помощью операции остатка от деления: index = hash % array.length

3. Сохранение значения: Значение сохраняется в ячейку массива с этим индексом

"Алексей" → hash("Алексей") → 1892374 → 1892374 % 10 → индекс 4 Массив: [_, _, _, _, {key: "Алексей", value: 28}, _, _, _, _, _]

Хеш-функции: сердце системы

Хорошая хеш-функция должна обладать несколькими свойствами:

• Детерминированность — один и тот же ключ всегда даёт один и тот же хеш

• Равномерность — хеши должны равномерно распределяться по всему диапазону значений

• Быстрота — вычисление хеша должно быть быстрым

• Минимизация коллизий — разные ключи должны давать разные хеши

Пример простой хеш-функции для строк:

function simpleHash(str, tableSize) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
        hash = (hash + str.charCodeAt(i) * (i + 1)) % tableSize;
    }
    return hash;
}

console.log(simpleHash("Алексей", 100)); // например, 67
console.log(simpleHash("Мария", 100));   // например, 23

В реальных системах используются более сложные функции, такие как MurmurHash, CityHash или криптографические функции вроде SHA-256 (для специальных случаев).

Коллизии: когда два ключа хотят одно место

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

"Алексей" → индекс 4 "Дмитрий" → индекс 4 ← Коллизия!

Метод цепочек (Chaining)

Самый популярный способ разрешения коллизий. В каждой ячейке массива хранится не одно значение, а список (цепочка) всех значений с одинаковым индексом.

class HashTable {
    constructor(size = 50) {
        this.table = new Array(size);
        this.size = size;
    }

    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * (i + 1)) % this.size;
        }
        return hash;
    }

    set(key, value) {
        const index = this._hash(key);
        
        if (!this.table[index]) {
            this.table[index] = [];
        }
        
        // Проверяем, есть ли уже такой ключ
        for (let item of this.table[index]) {
            if (item[0] === key) {
                item[1] = value; // Обновляем значение
                return;
            }
        }
        
        // Добавляем новую пару ключ-значение
        this.table[index].push([key, value]);
    }

    get(key) {
        const index = this._hash(key);
        const bucket = this.table[index];
        
        if (!bucket) return undefined;
        
        for (let item of bucket) {
            if (item[0] === key) {
                return item[1];
            }
        }
        
        return undefined;
    }

    remove(key) {
        const index = this._hash(key);
        const bucket = this.table[index];
        
        if (!bucket) return false;
        
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket.splice(i, 1);
                return true;
            }
        }
        
        return false;
    }
}

// Использование
const users = new HashTable();
users.set("Алексей", { age: 28, city: "Москва" });
users.set("Мария", { age: 25, city: "Санкт-Петербург" });
users.set("Дмитрий", { age: 32, city: "Новосибирск" });

console.log(users.get("Мария")); // { age: 25, city: "Санкт-Петербург" }
users.remove("Алексей");
console.log(users.get("Алексей")); // undefined

Открытая адресация (Open Addressing)

Вместо создания цепочек, при коллизии мы ищем другую свободную ячейку в массиве по определённому алгоритму:

Линейное пробирование — проверяем следующие ячейки подряд: index, index+1, index+2...

class HashTableOpenAddressing {
    constructor(size = 50) {
        this.table = new Array(size);
        this.size = size;
        this.count = 0;
    }

    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * (i + 1)) % this.size;
        }
        return hash;
    }

    set(key, value) {
        if (this.count / this.size > 0.7) {
            this._resize(); // Увеличиваем размер при заполнении >70%
        }

        let index = this._hash(key);
        let i = 0;

        while (this.table[index] !== undefined && this.table[index].key !== key) {
            i++;
            index = (this._hash(key) + i) % this.size; // Линейное пробирование
        }

        if (this.table[index] === undefined) {
            this.count++;
        }

        this.table[index] = { key, value };
    }

    get(key) {
        let index = this._hash(key);
        let i = 0;

        while (this.table[index] !== undefined) {
            if (this.table[index].key === key) {
                return this.table[index].value;
            }
            i++;
            index = (this._hash(key) + i) % this.size;
        }

        return undefined;
    }

    _resize() {
        const oldTable = this.table;
        this.size *= 2;
        this.table = new Array(this.size);
        this.count = 0;

        for (let item of oldTable) {
            if (item !== undefined) {
                this.set(item.key, item.value);
            }
        }
    }
}

Квадратичное пробирование — проверяем: index, index+1², index+2², index+3²...

Двойное хеширование — используем вторую хеш-функцию для вычисления шага.

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

Load Factor (коэффициент заполнения) = количество элементов / размер массива

При load factor > 0.7 обычно выполняется rehashing — создание нового массива большего размера и перемещение всех элементов.

Реальные кейсы использования

1. Кэширование результатов

class Cache {
    constructor() {
        this.cache = new Map();
    }

    async fetchUser(userId) {
        // Проверяем кэш
        if (this.cache.has(userId)) {
            console.log('Получено из кэша');
            return this.cache.get(userId);
        }

        // Загружаем данные
        const user = await api.getUser(userId);
        
        // Сохраняем в кэш
        this.cache.set(userId, user);
        
        return user;
    }
}

2. Подсчёт частоты элементов

function countWords(text) {
    const wordCount = new Map();
    const words = text.toLowerCase().split(/\s+/);

    for (let word of words) {
        wordCount.set(word, (wordCount.get(word) || 0) + 1);
    }

    return wordCount;
}

const text = "JavaScript это язык программирования JavaScript популярен";
console.log(countWords(text));
// Map { 'javascript' => 2, 'это' => 1, 'язык' => 1, ... }

3. Поиск дубликатов

function hasDuplicates(arr) {
    const seen = new Set();
    
    for (let item of arr) {
        if (seen.has(item)) {
            return true;
        }
        seen.add(item);
    }
    
    return false;
}

console.log(hasDuplicates([1, 2, 3, 4, 5])); // false
console.log(hasDuplicates([1, 2, 3, 2, 5])); // true

4. Индексация в базах данных

Базы данных используют хеш-индексы для быстрого поиска записей по ключу:

-- В PostgreSQL
CREATE INDEX users_email_hash ON users USING HASH (email);

-- Теперь поиск по email молниеносный
SELECT * FROM users WHERE email = 'alex@example.com';

5. Уникальные идентификаторы пользователей

class Session {
    constructor() {
        this.sessions = new Map();
    }

    createSession(userId) {
        const sessionId = this.generateSessionId();
        this.sessions.set(sessionId, {
            userId,
            createdAt: Date.now(),
            data: {}
        });
        return sessionId;
    }

    getSession(sessionId) {
        return this.sessions.get(sessionId);
    }

    destroySession(sessionId) {
        this.sessions.delete(sessionId);
    }

    generateSessionId() {
        return Math.random().toString(36).substring(2);
    }
}

6. Роутинг в веб-фреймворках

class Router {
    constructor() {
        this.routes = new Map();
    }

    addRoute(path, handler) {
        this.routes.set(path, handler);
    }

    handleRequest(path) {
        const handler = this.routes.get(path);
        
        if (handler) {
            return handler();
        }
        
        return 'Not Found';
    }
}

const router = new Router();
router.addRoute('/home', () => 'Home Page');
router.addRoute('/about', () => 'About Page');

console.log(router.handleRequest('/home')); // Home Page - O(1)!

7. Анаграммы и группировка строк

function groupAnagrams(words) {
    const groups = new Map();

    for (let word of words) {
        // Сортируем буквы как ключ
        const key = word.split('').sort().join('');
        
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        
        groups.get(key).push(word);
    }

    return Array.from(groups.values());
}

console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']));
// [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Map vs Object в JavaScript: что выбрать?

JavaScript предлагает два способа работы с хеш-таблицами:

Object:

const obj = {};
obj.name = "Алексей";
obj['age'] = 28;

Map:

const map = new Map();
map.set('name', 'Алексей');
map.set('age', 28);

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

• Ключи не строки (объекты, числа, функции)

• Нужна итерация в порядке добавления

• Частые добавления/удаления элементов

• Нужно знать точное количество элементов (map.size)

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

• Ключи всегда строки

• Нужен JSON.stringify/parse

• Простая структура конфигурации

Практические советы

1. Выбирайте правильный начальный размер

// Если знаете, что будет ~1000 элементов
const map = new Map(); // По умолчанию маленький размер
// vs
const users = new HashTable(2000); // Избегаем rehashing

2. Осторожно с объектами как ключами

const map = new Map();
const key1 = { id: 1 };
const key2 = { id: 1 };

map.set(key1, 'value1');
console.log(map.get(key2)); // undefined! Разные объекты

3. Чистите неиспользуемые данные

// Используйте WeakMap для автоматической очистки
const cache = new WeakMap();
let user = { name: 'Алексей' };

cache.set(user, 'some data');
user = null; // Данные автоматически удалятся из WeakMap

Заключение

Хеш-таблицы — это фундаментальная структура данных, которая используется повсеместно: от баз данных до веб-фреймворков, от компиляторов до поисковых систем. Понимание их устройства, способов разрешения коллизий и производительности делает вас более эффективным разработчиком.

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

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

Растём вместе! 🚀