706.Design HashMap

Ссылка на задачу: https://leetcode.com/problems/design-hashmap/description/

Описание

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

Имплементация класса MyHashMap:

• имеет конструктор MyHashMap(), который инициализирует пустую хеш-таблицу

• имеет метод void put(int key, int value), который вставляет ключ key с значением value в хеш-таблица; если key уже есть в таблице, то value обновляется

• имеет метод int get(key), который возвращает соответствующее значение value, если key есть в таблице и -1, если его нет

• имеет метод void remove(key), который удаляет пару key-value, если элемент есть в хеш-таблицае, не делает ничего, если пары нет

Примеры

Пример 1

Input:

Output:

Объяснение:

• первая операция MyHashMap - конструирование объекта

• put (1, 1) - добавление пары [1, 1]; хеш-таблица стала [1, 1]

• put (2, 2) - добавление пары [2, 2]; хеш-таблица стала [[1, 1], [2, 2]]

• get 1 - попытка взять значение по ключу 1; результат - 1 (такой ключ есть)

• get 3 - попытка взять значение по ключу 3; результат - -1 (такого ключа нет)

• put (2, 1) - обновление по ключу уже имеющейся двойки; хеш-таблица изменилась: [[1, 1], [2, 1]]

• get 2 - попытка взять значение по ключу 1; результат - 1 (такой ключ есть)

• remove 2 - удаление двойки, хеш-таблица стала [[1, 1]]

• get 2 - попытка взять значение по ключу 2; результат - -1 (такого ключа нет)

Ограничения

• 0 <= key, value <= 10^6

• максимальное количество вызовов put, remove и get составит 10^4.

Решение

Вспомним определение структуры данных хеш-таблица. Данная структура данных хранит только уникальные ключи, причем доступ до ключа, добавление соответствующего ему значения и удаление - операции, сложность которых О(1), то есть не зависимая от размера структуры. Строгость порядка элементов отсутствует, он не гарантирован.

Задача сводится к тому, чтобы придумать, как спроектировать класс MyHashMap, удовлетворяющий всем этим условиям. Интуитивно понятно, что нужно использовать какой-то фундаментальный контейнер “под капотом”. Но какой?

Будем идти по порядку условий:

• доступ до ключа за константное время: мы знаем, что обращение к элементу массива по его индексу происходит за константное время

• добавление соответствующего ключу значения за константное время: к массиву можно добавить элемент за О(1), но только в том случае, если его емкость позволяет нам это сделать

• удаление за константное время: здесь массив не подойдет, так как удаление элемента с произвольной позиции приведет к сдвигу всех элементов справа от удаленного на 1 влево

Как будто бы массив почти подходит. Два фактора мешают его использовать: необходимость иметь достаточную емкость для добавления элемента за О(1) и сдвиг элементов при удалении. Нужно как-то нивелировать эти недостатки.

Первую проблему можно решить, обратившись к ограничениям задачи. Сказано, что key лежит в диапазоне от 0 до 10^6 включительно. Так, если мы заранее выделим память под 1000001 целочисленных элементов, то нам всегда хватит емкости с 100%-ной гарантией. Действительно, если key принять за индекс массва, то максимальный индекс - это 10^6, значит размер массива должен быть 1000001, чтобы никогда не выйти за его границы.

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

Алгоритм:

1. Инициализировать массив размером 1000001 значениями -1

2. В случае попытки взять значение ключа key нужно вернуть значение массива с индексом key

3. При добавлении по ключу key значения необходимо переписать значение массива с индексом key

4. При удалении по ключу key достаточно присвоить -1 элементу массива с индексом key

Код:

python

class MyHashMap:
    def __init__(self):
        self.key_to_value = [-1] * (10**6 + 1)

    def put(self, key: int, value: int) -> None:
        self.key_to_value[key] = value

    def get(self, key: int) -> int:
        return self.key_to_value[key]

    def remove(self, key: int) -> None:
        self.key_to_value[key] = -1

C++

class MyHashMap {
public:
    MyHashMap() {
        key_to_value_ = vector<int>(1000001, -1);
    }
    
    void put(int key, int value) {
        key_to_value_[key] = value;
    }
    
    int get(int key) {
        return key_to_value_[key];
    }
    
    void remove(int key) {
        key_to_value_[key] = -1;
    }
private:
    vector<int> key_to_value_;
};

Сложность

Наша хеш-таблица удовлетворяет всем требованиям:

• сложность взятия значения по ключу - О(1)

• сложность обновления элемента по ключу - О(1)

• сложность удаления элемента по ключу - О(1)