Реализация консистентного хеширования

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

Постановка задачи

В файле ConsistentHash.java находится описание интерфейса, который вам предстоит реализовать. Свой код вы должны писать на языке Java в файле ConsistentHashImpl.java.

Для решения на Kotlin откройте Java решения и нажмите Ctrl+Alt+Shift+K (Cmd+Alt+Shift+K на MacOS) в IntelliJ IDEA для конвертации соответствующего фала из XXX.java в XXX.kt. На вопрос "Some code in the rest of your project may require corrections after performing this conversion. Do you want to find such code and correct it too?" отвечайте "No". Пишите код в соответствующем kt файле, который получится после конвертации.

Вспомогательные классы

Вспомогательные классы описаны в файлах Shard.kt и HashRange.kt.

Класс Shard описывает узел системы и задаётся своим именем. Класс HashRange описывает отрезок хешей, перемещаемых с существующего узла на новый узел (или с удаляемого узла на существующий узел), и задаётся своими левой и правой границами (обе границы включены в диапазон).

Описание операций

В этом задании вам предстоит реализовать три операции:

• Shard getShardByKey(K key) — возвращается по ключу узел системы, отвечающий за этот ключ. Гарантируется, что в момент этого вызова в системе существует хотя бы один узел. K - тип ключей, хранящихся в системе. Для получения хеша по ключу необходимо пользоваться методом hashCode.
• Map<Shard, Set<HashRange>> addShard(Shard newShard, Set<Int> vnodeHashes) — добавляет новый узел в систему. Метод возвращает отображение, в котором для каждого существующего узла, который должен передать новому узлу хотя бы один отрезок хешей, сопоставлено множество отрезков хешей, которые он должен передать новому узлу.
• Map<Shard, Set<HashRange>> removeShard(Shard shard) — удаляет существующий узел. Гарантируется, что удаляемый узел существует в системе, и что, помимо удаляемого узла, в системе существует ещё хотя бы один неудаляемый узел. Метод возвращает отображение, в котором для каждого неудаляемого узла, которому удаляемый узел должен передать хотя бы один отрезок хешей, сопоставлено множество отрезков хешей, которые ему должен передать удаляемый узел.

Тестирование

Тестирования реализации происходит путем запуска тестов UnitTest и StressTest. Из командной строки: ./gradlew test.

• unit-тест проверяет несколько базовых сценариев корректности вашего решения
• stress-тест выполняет набор случайных тестов из папки resources

Формат сдачи

Выполняйте задание в этом репозитории. Код процесса должен быть реализован в одном файле ConsistentHashImpl.kt.