Ключ и значение в хеш-таблице

Тип ключа в хеш-таблице

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

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

«Какими типами могут быть ключи в хеш-таблице?» Этот вопрос часто задают на собеседованиях для специалистов уровня junior и middle. Ответ зависит от языка программирования, поэтому изучи правила для своего языка:

# Любой не изменяемый тип может быть ключом. Например:
# - int
# - tuple
# - bool
# - str
# - ...

Что чаще всего является ключом, а что значением

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

Ключ	Значение
Число/строка/символ	Индекс массива
Число/строка/символ	Число повторений
Координата точки	Число точек в этой координате
Номер строки/столбца/диагонали в 2D массиве	Число элементов/сами элементы
ID пользователя	Сколько раз встречался
Точка отправления	Точка прибытия

Таблица содержит не все возможное варианты, но точно поможет, если ты только начинаешь изучение этой структуры данных!

Паттерны построения хеш-таблицы

Существует два основных способа построения хеш-таблицы из входных данных:

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

Первый подход чаще подходит, если нужно найти предыдущий элемент с определёнными свойствами. Второй — когда данные нужны для предварительного анализа.

С практикой ты научишься выбирать подходящий способ! Читай дальше и скорее переходи к решению задач, чтобы закрепить знания на практике.

Пример задачи с собеседования

Условие

Дан массив точек points. Нужно вернуть true, если существует такая прямая, параллельная оси Y, которая симметрично отражает данные точки и false, если такой прямой нет.

ВАЖНО: точки могут повторяться, но число симметричных точек не обязательно должно совпадать (см. пример 1).

Другими словами, требуется ответить, существует ли прямая, относительно которой, если отразить все точки, множество исходных точек останется таким же, как и множество отражённых точек.

Пример 1

Ввод: points = [[1,2],[3,1],[4,2],[2,1],[2,1]]
Вывод: true
Объяснение: Мы можем выбрать прямую x = 2.5

Пример 2

Ввод: points = [[1,2],[3,1]]
Вывод: false
Объяснение: Мы не можем найти линию, удовлетворяющую условию.

Оптимальное решение

using System;
using System.Collections.Generic;

//Время: O(n), где n — количество точек.
//Память: O(n), где n — количество точек.
class Solution {
    public bool IsReflected(int[][] points) {
        if (points == null || points.Length == 0) return true;
        
        // Находим минимальный и максимальный X
        int minX = points[0][0], maxX = points[0][0];
        foreach (var point in points) {
            minX = Math.Min(minX, point[0]);
            maxX = Math.Max(maxX, point[0]);
        }
        
        // Создаем HashSet для хранения уникальных точек
        HashSet<(int, int)> pointSet = new HashSet<(int, int)>();
        foreach (var point in points) {
            pointSet.Add((point[0], point[1]));
        }
        
        // Проверяем, существует ли отраженная точка для каждой данной точки
        foreach (var point in points) {
            int symX = maxX + minX - point[0]; // координата симметричной точки
            if (!pointSet.Contains((symX, point[1]))) {
                return false;
            }
        }
        return true;
    }
}

//Время: O(n), где n — количество точек.
//Память: O(n), где n — количество точек.
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

struct PointHash {
    size_t operator()(const pair<int, int>& p) const {
        return hash<int>()(p.first) ^ hash<int>()(p.second);
    }
};

bool isSymmetric(const vector<vector<int>>& points) {
    // находим минимальный и максимальный X
    int maxX = points[0][0];
    int minX = points[0][0];
    for (const auto& point : points) {
        maxX = max(maxX, point[0]);
        minX = min(minX, point[0]);
    }

    // в сете храним позиции точек, чтобы проверять наличие симметричной точки за O(1)
    unordered_set<pair<int, int>, PointHash> pointsSet;
    for (const auto& point : points) {
        pointsSet.insert({point[0], point[1]});
    }

    for (const auto& point : points) {
        int x = point[0], y = point[1];
        // формула: maxX + minX - x
        //  позволяет находить значение по оси X симметричной точки

        // проверяем наличие симметричной точки
        if (pointsSet.find({maxX + minX - x, y}) == pointsSet.end()) {
            return false;
        }
    }
    return true;
}

//Время: O(n), где n — количество точек.
//Память: O(n), где n — количество точек.
func isReflected(points [][]int) bool {
    // находим минимальный и максимальный X
    maxX := points[0][0]
    minX := points[0][0]
    for _, point := range points {
        if point[0] > maxX {
            maxX = point[0]
        }
        if point[0] < minX {
            minX = point[0]
        }
    }

    // сделали хеш-таблицу, чтобы проверять наличие точки за O(1)
    pointSet := make(map[[2]int]bool)
    for _, point := range points {
        pointSet[[2]int{point[0], point[1]}] = true
    }

    for _, point := range points {
        // symX = maxX + minX - x
        // symX - координата точки по оси X симметричной x
        symX := maxX + minX - point[0]
        if !pointSet[[2]int{symX, point[1]}] {
            return false
        }
    }
    return true
}

import java.util.HashSet;
import java.util.Set;

//Время: O(n), где n — количество точек.
//Память: O(n), где n — количество точек.
class Solution {
    record Point(int x, int y) {}

    public boolean isReflected(int[][] points) {
        // находим минимальный и максимальный X
        int maxX = points[0][0];
        int minX = points[0][0];
        for (int[] point : points) {
            maxX = Math.max(maxX, point[0]);
            minX = Math.min(minX, point[0]);
        }

        // сделали HashSet для хранения точек
        Set<Point> pointSet = new HashSet<>();
        for (int[] point : points) {
            pointSet.add(new Point(point[0], point[1]));
        }

        for (int[] point : points) {
            // symX = maxX + minX - x
            // symX - координата точки по оси X симметричной x
            int symX = maxX + minX - point[0];
            if (!pointSet.contains(new Point(symX, point[1]))) {
                return false;
            }
        }
        return true;
    }
}

#Время: O(n), где n — количество точек.
#Память: O(n), где n — количество точек.
class Solution:
    def isReflected(self, points: List[List[int]]) -> bool:
        # находим минимальный и максимальный X
        maxX = max(x for x, _ in points)
        minX = min(x for x, _ in points)

        # в сете храним позиции точек, чтобы проверять наличие симметричной точки за O(1)
        points_set = {(x, y) for x, y in points}
        for x, y in points:
            # symX = maxX + minX - x
            # symX - координата точки по оси X симметричной x
            if (maxX + minX - x, y) not in points_set:
                return False
        return True

//Время: O(n), где n — количество точек.
//Память: O(n), где n — количество точек.
function isReflected(points) {
    // находим минимальный и максимальный X
    let maxX = points[0][0];
    let minX = points[0][0];
    for (const point of points) {
        maxX = Math.max(maxX, point[0]);
        minX = Math.min(minX, point[0]);
    }

    // сделали сет, чтобы проверять наличие точки за O(1)
    const pointSet = new Set();
    for (const [x, y] of points) {
        pointSet.add(`${x},${y}`);
    }

    for (const [x, y] of points) {
        // symX = maxX + minX - x
        // symX - координата точки по оси X симметричной x
        const symX = maxX + minX - x;
        if (!pointSet.has(`${symX},${y}`)) {
            return false;
        }
    }
    return true;
}

Для решения задачи нам нужно проверить, существует ли вертикальная ось симметрии, которая отражает все точки на плоскости. Процесс можно разделить на несколько этапов:

Найти максимальное и минимальное значение по оси x у точек.
Для каждой точки из исходного массива вычисляется её симметричная точка относительно линии симметрии: symX=maxX+minX−x.
Затем проверяется, содержится ли симметричная точка в множестве pointSet. Если хотя бы одна симметричная точка отсутствует, возвращается false.

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

Эту задачу также можно решить, вычислив ось симметрии: symmetryLine = (minX + maxX) / 2. Однако важно учитывать, что эта ось симметрии может быть числом с плавающей точкой, поэтому необходимо аккуратно обращаться с приведением типов.

Как получилась формула нахождения симметричной точки?

Формула symX=minX+maxX−x основана на свойстве отражения точки относительно вертикальной линии симметрии, которая проходит через середину между minX и maxX. Симметричная точка symX находится на таком же расстоянии от линии, но с противоположной стороны.

Возьмем первый пример и точку [1, 2], подставим ее в формулу. Исходя из входных данных, minX = 1, maxX = 4. Тогда: 1 + 4 - 1 = 4. Это означает, что симметричная точка должна иметь координаты [4, 2].

Заключение

В этой лекции мы узнали, какие данные чаще всего используются как ключи, а какие — как значения. Рассмотрели паттерны заполнения хеш-таблиц и применили новые знания для решения достаточно сложной задачи. Теперь самое время закрепить материал на практике — переходи к решению задач!