Хеш-множество / словарь

Хеш-множество / словарь: как это работает?

Хеш-функция превращает ключ в номер ячейки. Значение кладётся именно туда.

Поиск запускает ту же функцию заново. Он сразу попадает в ячейку, без перебора.

Два ключа могут дать одну ячейку. Структура хранит оба и сравнивает сами ключи.

Множество хранит только ключи. Оно отвечает на вопрос, видел ли я это.

Словарь хранит рядом с ключом значение. Он держит счётчики, индексы или последнюю позицию.

Вставка, поиск и удаление стоят в среднем O(1). Плата за это O(n) памяти.

Источники: Википедия: Хеш-таблица, MDN (англ.): Map

1. seen = {}Ищем первое повторяющееся значение в [3, 1, 3, 4].
2. seen = {3}Тройка раньше не встречалась. Она попадает в множество.
3. seen = {3, 1}Единица тоже новая. В множестве уже два ключа.
4. seen = {3, 1}Тройка приходит второй раз. Множество её уже содержит.
5. ответ = 3Ответ возвращается сразу. Последний элемент так и не прочитан.

function firstDuplicate(arr) {
    const seen = new Set();
    for (const x of arr) {
        if (seen.has(x)) return x;
        seen.add(x);
    }
    return null;
}

function firstDuplicate(arr: number[]): number | null {
    const seen = new Set<number>();
    for (const x of arr) {
        if (seen.has(x)) return x;
        seen.add(x);
    }
    return null;
}

def first_duplicate(arr):
    seen = set()
    for x in arr:
        if x in seen:
            return x
        seen.add(x)
    return None

function firstDuplicate(array $arr) {
    $seen = [];
    foreach ($arr as $x) {
        if (isset($seen[$x])) return $x;
        $seen[$x] = true;
    }
    return null;
}

    public static Integer firstDuplicate(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        for (int x : arr) {
            if (seen.contains(x)) return x;
            seen.add(x);
        }
        return null;
    }

    public static int? FirstDuplicate(int[] arr) {
        var seen = new HashSet<int>();
        foreach (int x in arr) {
            if (seen.Contains(x)) return x;
            seen.Add(x);
        }
        return null;
    }

Хеш-множество / словарь: разбор примера

Сумма двух на неотсортированных данных

Дан неотсортированный массив и число-цель. Верните индексы двух значений, дающих эту сумму.

Сортировка сломала бы исходные индексы. Значит массив трогать нельзя.

Пройдите массив один раз. Для каждого значения посчитайте, какого дополнения не хватает.

Если дополнение уже в словаре, пара найдена. Иначе положите значение вместе с индексом.

function twoSum(nums, target) {
    const seen = new Map(); // value -> index

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

        if (seen.has(need)) {
            return [seen.get(need), i];
        }

        // stored after the lookup, so a value never pairs with itself
        seen.set(nums[i], i);
    }

    return [];
}

Хеш-множество / словарь: когда применять?

Паттерн «Хеш-множество / словарь» нужен, когда в условии есть слова «встречалось ли это раньше», «посчитать сколько каждого» или «найти дубликаты». Решение на нём обычно укладывается в O(n).

• •встречалось ли это раньше
• •посчитать сколько каждого
• •найти дубликаты
• •есть ли подходящее/дополняющее значение
• •данные в любом порядке / не отсортированы

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Хеш-множество / словарь: с чем путают?

Паттерн «Хеш-множество / словарь» чаще всего путают с этими паттернами: Два указателя (с концов), Скользящее окно (переменное), Сортировка без сравнений (подсчётом / поразрядная), Trie (префиксное дерево) и Префиксные суммы.

• Два указателя (с концов) (Two pointers (opposite ends)): Двум указателям нужен отсортированный массив, зато лишней памяти нет. Хеш нужен, когда сортировать нельзя.
• Скользящее окно (переменное) (Sliding window (variable)): Окно отвечает на вопрос про один непрерывный отрезок. У словаря понятия отрезка нет вообще.
• Сортировка без сравнений (подсчётом / поразрядная) (Non-comparison sort (counting / radix)): Сортировка подсчётом тоже считает частоты, но ей нужны маленькие целые ключи. Словарь берёт любой ключ.
• Trie (префиксное дерево) (Trie (prefix tree)): Trie делит общие префиксы, поэтому отвечает на запросы по префиксу. Словарь сравнивает только целые ключи.
• Префиксные суммы (Prefix sums): Префиксные суммы отвечают про диапазоны в исходном порядке. Хеш порядок не хранит.

Хеш-множество / словарь: частые ошибки

• Кладут в словарь до проверки

  Вставляйте значение только после поиска. Иначе значение составит пару само с собой.

• Берут обычный объект вместо Map

  Объект молча делает из любого ключа строку, и 1 совпадает с "1". Используйте Map.

• Считают без значения по умолчанию

  Чтение отсутствующего ключа даёт undefined, а undefined плюс один это NaN. Начинайте счёт с нуля.

• Платят памятью там, где не нужно

  Если данные уже отсортированы, два указателя обойдутся без памяти. Хеш нужен, когда порядок бесполезен.

Хеш-множество / словарь: задачи с собеседований

Паттерн «Хеш-множество / словарь» решает такие задачи с собеседований: Сумма двух, Есть ли дубликаты, Проверка анаграммы, Группировка анаграмм, K самых частых элементов, Самая длинная последовательность подряд и Подмассив с суммой k.

• Сумма двух: Кладите каждое значение с индексом и ищите дополнение.
• Есть ли дубликаты: Множество, которое отвергает повтор, отвечает за один проход.
• Проверка анаграммы: Посчитайте буквы одного слова, потом вычтите буквы второго.
• Группировка анаграмм: Ключ это отсортированное слово. Значение это группа.
• K самых частых элементов: Посчитайте словарём, потом возьмите k наибольших счётчиков.
• Самая длинная последовательность подряд: Множество позволяет спросить, есть ли x минус один.
• Подмассив с суммой k: Храните, сколько раз встречалась каждая накопленная сумма.

Хеш-множество / словарь: сложность по времени и памяти

У паттерна «Хеш-множество / словарь» целевая сложность O(n).

n до 1e6 неотсортированных значений даёт O(n) времени. Память O(n), потому что хранится каждый ключ.