Подготовка к алгоритмическим задачам

Хеш-таблица простым языком: как работает HashMap и почему она быстрая

16 мин чтения

структуры данных

хеш-таблица

HashMap

собеседование

алгоритмы

Что такое хеш-таблица?

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

Простая аналогия: Представьте библиотеку. Вместо того чтобы искать книгу на всех полках, вы знаете: "Книги автора на букву 'П' — на полке №16". Хеш-функция — это правило, по которому вы мгновенно находите нужную полку.

// В JavaScript это объект или Map
const user = {
    name: "Анна",
    age: 25
};
console.log(user.name); // "Анна" — мгновенно, O(1)

// В Python это словарь (dict)
// user = {"name": "Анна", "age": 25}
// print(user["name"])  # "Анна"

Почему хеш-таблица такая быстрая?

Сравнение с другими структурами

Операция	Массив	Связный список	Хеш-таблица
Поиск по значению	O(n)	O(n)	O(1)
Вставка	O(n)	O(1)	O(1)
Удаление	O(n)	O(n)	O(1)
Поиск по индексу	O(1)	O(n)	—

Секрет скорости: хеш-функция

Хеш-функция преобразует ключ в индекс массива:

Ключ "name" → хеш-функция → индекс 42 → значение "Анна"

// Упрощенная хеш-функция
function simpleHash(key, arraySize) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
        hash += key.charCodeAt(i);
    }
    return hash % arraySize;
}

console.log(simpleHash("name", 100)); // Например, 17
console.log(simpleHash("age", 100));  // Например, 42

# То же на Python
def simple_hash(key, array_size):
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    return hash_value % array_size

print(simple_hash("name", 100))  # Например, 17

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

Индекс    Значение
┌─────┬──────────────────┐
│  0  │  null            │
├─────┼──────────────────┤
│  1  │  null            │
├─────┼──────────────────┤
│  2  │  "age" → 25      │  ← hash("age") = 2
├─────┼──────────────────┤
│  3  │  null            │
├─────┼──────────────────┤
│  4  │  "name" → "Анна" │  ← hash("name") = 4
├─────┼──────────────────┤
│ ... │  ...             │
└─────┴──────────────────┘

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

Вставка: hash("name") → индекс 4 → сохраняем "Анна" в ячейку 4
Поиск: hash("name") → индекс 4 → возвращаем значение из ячейки 4
Удаление: hash("name") → индекс 4 → очищаем ячейку 4

Проблема коллизий

Коллизия — когда разные ключи дают одинаковый хеш:

hash("abc") → 6
hash("bca") → 6  // Коллизия! Тот же индекс

Решение 1: Метод цепочек (Chaining)

Каждая ячейка хранит связный список:

Индекс    Значение
┌─────┬─────────────────────────────────┐
│  6  │  ["abc" → 1] → ["bca" → 2]     │
└─────┴─────────────────────────────────┘

class HashTableChaining {
    constructor(size = 53) {
        this.buckets = new Array(size);
        this.size = size;
    }

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

    set(key, value) {
        const index = this.hash(key);
        if (!this.buckets[index]) {
            this.buckets[index] = [];
        }

        // Проверяем, есть ли уже такой ключ
        for (let i = 0; i < this.buckets[index].length; i++) {
            if (this.buckets[index][i][0] === key) {
                this.buckets[index][i][1] = value;
                return;
            }
        }

        this.buckets[index].push([key, value]);
    }

    get(key) {
        const index = this.hash(key);
        const bucket = this.buckets[index];

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

    delete(key) {
        const index = this.hash(key);
        const bucket = this.buckets[index];

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

// Использование
const table = new HashTableChaining();
table.set("name", "Анна");
table.set("age", 25);
console.log(table.get("name")); // "Анна"

class HashTableChaining:
    def __init__(self, size=53):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def _hash(self, key):
        hash_value = 0
        for char in str(key):
            hash_value = (hash_value * 31 + ord(char)) % self.size
        return hash_value

    def set(self, key, value):
        index = self._hash(key)

        for i, (k, v) in enumerate(self.buckets[index]):
            if k == key:
                self.buckets[index][i] = (key, value)
                return

        self.buckets[index].append((key, value))

    def get(self, key):
        index = self._hash(key)

        for k, v in self.buckets[index]:
            if k == key:
                return v
        return None

    def delete(self, key):
        index = self._hash(key)

        for i, (k, v) in enumerate(self.buckets[index]):
            if k == key:
                del self.buckets[index][i]
                return True
        return False

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Использование

table = HashTableChaining() table.set("name", "Анна") table.set("age", 25) print(table.get("name")) # "Анна"


### Решение 2: Открытая адресация (Open Addressing)

Ищем следующую свободную ячейку:

hash("abc") → 6 (занято) → 7 (занято) → 8 (свободно!) ✓


```javascript
class HashTableOpenAddressing {
    constructor(size = 53) {
        this.keys = new Array(size);
        this.values = new Array(size);
        this.size = size;
    }

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

    set(key, value) {
        let index = this.hash(key);

        while (this.keys[index] !== undefined && this.keys[index] !== key) {
            index = (index + 1) % this.size;
        }

        this.keys[index] = key;
        this.values[index] = value;
    }

    get(key) {
        let index = this.hash(key);

        while (this.keys[index] !== undefined) {
            if (this.keys[index] === key) {
                return this.values[index];
            }
            index = (index + 1) % this.size;
        }

        return undefined;
    }
}

Map vs Object в JavaScript

// Object — только строковые ключи
const obj = {};
obj[1] = "число";
obj["1"] = "строка";
console.log(obj[1]); // "строка" — ключ преобразовался!

// Map — любые типы ключей
const map = new Map();
map.set(1, "число");
map.set("1", "строка");
console.log(map.get(1));   // "число"
console.log(map.get("1")); // "строка"

// Map сохраняет порядок вставки
const orderedMap = new Map();
orderedMap.set("c", 3);
orderedMap.set("a", 1);
orderedMap.set("b", 2);

for (const [key, value] of orderedMap) {
    console.log(key); // c, a, b — в порядке добавления
}

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

Ключи не строки (числа, объекты)
Важен порядок вставки
Часто добавляете/удаляете элементы
Нужен метод .size

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

Простые данные с строковыми ключами
JSON-совместимость
Не нужны методы Map

Set — хеш-таблица без значений

Set хранит только уникальные ключи:

const set = new Set();
set.add(1);
set.add(2);
set.add(1); // Игнорируется, уже есть

console.log(set.has(1)); // true — O(1)
console.log(set.size);   // 2

// Удаление дубликатов из массива
const arr = [1, 2, 2, 3, 3, 3];
const unique = [...new Set(arr)];
console.log(unique); // [1, 2, 3]

# В Python это set
s = {1, 2, 3}
s.add(1)  # Игнорируется

print(1 in s)  # True — O(1)

# Удаление дубликатов
arr = [1, 2, 2, 3, 3, 3]
unique = list(set(arr))
print(unique)  # [1, 2, 3]

Задачи на собеседованиях

Задача 1: Two Sum (классика!)

Найти два числа, дающих в сумме target:

// O(n²) — наивное решение
function twoSumNaive(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
}

// O(n) — с хеш-таблицей!
function twoSum(nums, target) {
    const map = new Map();

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (map.has(complement)) {
            return [map.get(complement), i];
        }

        map.set(nums[i], i);
    }
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

def two_sum(nums, target):
    seen = {}

    for i, num in enumerate(nums):
        complement = target - num

        if complement in seen:
            return [seen[complement], i]

        seen[num] = i

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

Задача 2: Проверка дубликатов

// O(n) с Set
function containsDuplicate(nums) {
    const seen = new Set();

    for (const num of nums) {
        if (seen.has(num)) return true;
        seen.add(num);
    }

    return false;
}

// Или ещё короче
function containsDuplicateShort(nums) {
    return new Set(nums).size !== nums.length;
}

console.log(containsDuplicate([1, 2, 3, 1])); // true

def contains_duplicate(nums):
    return len(set(nums)) != len(nums)

print(contains_duplicate([1, 2, 3, 1]))  # True

Задача 3: Подсчет частоты элементов

function frequencyCount(arr) {
    const freq = new Map();

    for (const item of arr) {
        freq.set(item, (freq.get(item) || 0) + 1);
    }

    return freq;
}

console.log(frequencyCount(['a', 'b', 'a', 'c', 'a']));
// Map { 'a' => 3, 'b' => 1, 'c' => 1 }

from collections import Counter

def frequency_count(arr):
    return Counter(arr)

print(frequency_count(['a', 'b', 'a', 'c', 'a']))
# Counter({'a': 3, 'b': 1, 'c': 1})

Задача 4: Группировка анаграмм

function groupAnagrams(strs) {
    const map = new Map();

    for (const str of strs) {
        // Сортируем буквы — анаграммы дадут одинаковый ключ
        const key = str.split('').sort().join('');

        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key).push(str);
    }

    return [...map.values()];
}

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

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)

    for s in strs:
        key = ''.join(sorted(s))
        groups[key].append(s)

    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

Задача 5: Первый неповторяющийся символ

function firstUniqChar(s) {
    const count = new Map();

    // Считаем частоту
    for (const char of s) {
        count.set(char, (count.get(char) || 0) + 1);
    }

    // Находим первый с частотой 1
    for (let i = 0; i < s.length; i++) {
        if (count.get(s[i]) === 1) {
            return i;
        }
    }

    return -1;
}

console.log(firstUniqChar("leetcode")); // 0 (символ 'l')
console.log(firstUniqChar("aabb"));     // -1

Когда НЕ использовать хеш-таблицу

Нужен порядок по значению — используйте дерево или отсортированный массив
Мало данных — накладные расходы не оправданы
Нужен диапазонный поиск — "все ключи от A до B"
Критична память — хеш-таблицы потребляют больше памяти

Советы для собеседования

Думайте о хеш-таблице когда нужно:
- Быстро искать элементы
- Подсчитать частоту
- Найти дубликаты
- Сгруппировать данные
Озвучивайте сложность:
- "С хеш-таблицей это будет O(n) вместо O(n²)"
Упоминайте компромиссы:
- "Мы тратим O(n) памяти, но получаем O(1) поиск"
Знайте встроенные реализации:
- JavaScript: Object, Map, Set
- Python: dict, set, Counter, defaultdict

Заключение

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

Поиск, вставка, удаление за O(1)
Основа для Object, Map, Set в JS и dict, set в Python
Решает множество задач на собеседованиях
Компромисс: скорость за счёт памяти

Когда видите задачу с поиском или подсчётом — сразу думайте о хеш-таблице!

Попробуй решить популярные задачи

Массивы и Хеширование