Необходимо имплементировать классы HashSet и HashMap, реализующие множество и ассоциативный массив на основе хеш-таблицы. Хеш-таблица должна представлять собой массив с адресацией по хешу ключа (который может быть хешируемым неизменяемым объектом), для разрешения коллизий должны использоваться связные списки.
Хеш-таблица представляет собой массив (статический или расширяемый - ArrayList), адресация в котором выполняется не с помощью индекса, а с помощью ключа. Фактически, индексом в массиве является целое число, определяемое следующим образом:
index = хеш_ключа % длина_массива
Коллизией называется ситуация, при которой производится перезапись ячейки массива при обращении по другому ключу. Такое происходит, когда нормализованный хеш ключа добавляемого элемента совпадает с таковым у другого ключа. Существует несколько способов разрешения коллизий. Один из таких, рассматриваемый в задании, основан на хранении в ячейках массива связных списков, в которые добавляются элементы (также метод известен как separate chaining). Таким образом, в мы можем хранить в узлах списка пары ключ:значение (в случае с множествами только значения).
- set(key, value) - устанавливает значение в ассоциативном массиве по ключу
- get(key) - получает значение по ключу
- del(key) - удаляет значение по ключу
- has(key) - проверяет, установлено ли какое-либо значение по данному ключу Средняя сложность всех методов O(1) при небольшом коэффициенте заполнения таблицы (то есть когда большинство ячеек массива ссылаются на пустой список).
Все методы HashMap также применимы и для HashSet, с учетом того, что значение одновременно является и самим ключем. Кроме того, должны быть реализованы базовые операции над множествами, как то
- union(setB) - получает объединение двух множеств
- difference(setB) - получает разность двух множеств
- intersection(setB) - получает пересечение множеств
Если считать, что операции над хеш-таблицами выполняются за константное время, время выполнения вышеописанных операций будет линейным.
При переходе по ссылке преподавателя выполняется форк шаблонного репозитория, содержащего шаблон кода с заготовкой классов, а также этот файл. Вам необходимо сделать локальный клон репозитория, внести свои изменения и закомитить их. Не забудьте выполнить push в ваш GitHub репозиторий. Для работы вы можете использовать утилиту git или любой Git-клиент, включая встроенные в IDE. Неплохим вариантом будет также использовать GitHub Desktop.
Вам отредактировать в репозитории файл student.md, содержащий информацию о студенте, его группе и предпочтительном способе обратной связи от преподавателя.
Запрещено использовать внешние библиотеки и встроенные структуры данных языка, помимо использованных в шаблоне.
Хеширование в Python выполняется с использованием встроенной функции hash(). Захешировать можно большинство неизменяемых объектов (наиболее распространенные - int, float, str, tuple). Структуры, аналогичные ассоциативному массиву и множеству в Python - hash и set. Например:
- hash(1.27005) = 622692904638157825
- hash("cdv") = 8409661036739369760