Тимофей, как хороший руководитель, хранит информацию о зарплатах своих сотрудников в базе данных и постоянно её обновляет. Он поручил вам написать реализацию хеш-таблицы, чтобы хранить в ней базу данных с зарплатами сотрудников.
Хеш-таблица должна поддерживать следующие операции:
put key value—– добавление пары ключ-значение. Если заданный ключ уже есть в таблице, то соответствующее ему значение обновляется.get key–— получение значения по ключу. Если ключа нет в таблице, то вывести «None». Иначе вывести найденное значение.delete key–— удаление ключа из таблицы. Если такого ключа нет, то вывести «None», иначе вывести хранимое по данному ключу значение и удалить ключ.
В таблице хранятся уникальные ключи.
Требования к реализации:
- Нельзя использовать имеющиеся в языках программирования реализации хеш-таблиц (std::unordered_map в С++, dict в Python, HashMap в Java, и т. д.)
- Число хранимых в таблице ключей не превосходит 105.
- Разрешать коллизии следует с помощью метода цепочек или с помощью открытой адресации.
- Все операции должны выполняться за O(1) в среднем.
- Поддерживать рехеширование и масштабирование хеш-таблицы не требуется.
- Ключи и значения, id сотрудников и их зарплата, —– целые числа. Поддерживать произвольные хешируемые типы не требуется.
В первой строке задано общее число запросов к таблице n (1≤ n≤ 106).
В следующих n строках записаны запросы, которые бывают трех видов –— get, put, delete —– как описано в условии.
Все ключи и значения –— целые неотрицательные числа, не превосходящие 109.
На каждый запрос вида get и delete выведите ответ на него в отдельной строке.
|
10 get 1 put 1 10 put 2 4 get 1 get 2 delete 2 get 2 put 1 5 get 1 delete 2 |
None 10 4 4 None 5 None |
|
8 get 9 delete 9 put 9 1 get 9 put 9 2 get 9 put 9 3 get 9 |
None None 1 2 3 |