Определить и найти. Разработка алгоритма поиска изменений с Мap-ами и хешами04.07.2023 00:32

Что-то изменилось?

Вступление, постановка задачи

Во время учёбы в университете, был сайт с расписанием занятий. Он упрощал информирование, но нужно было постоянное подключение к сети. Если интернета нет или он медленный, ты не узнаешь какие у тебя пары, если не успел сохранить. Также требовалось постоянно проверять информацию на свежесть. Исходя из этого, была поставлена задача реализовать мобильное приложение. Примерный концепт был озвучен и переведен в техническое задание, которое периодически дополнялось.

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

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

Первое решение

Для начала, стоило реализовать простое обновление. Загрузил, преобразовал, сохранил. Приложение делало запрос на сервер и получала данные. Принятый JSON быстро разбирала библиотека GSON. Алгоритм проходил по сущностям, попутно собирая главное расписание в массив по дням. Информация преобразовывалась в строку и сохранялась в SharedPreferences, доставалась она оттуда уже при входе.

SharedPreferences — это

класс хранилища на платформе Android, используемый для хранения различной информации о конфигурации приложения. В нём данные сохраняются в XML-файл, в виде пар «ключ-значение».

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

Я изначально стал хранить обработанный JSON расписания пользователя в памяти телефона. Поэтому, берём новый с сервера и достаем локальный. Обрабатываем и ищем различия по сущностям. Алгоритм, брал занятия пользователя, искал группу. Проходясь по ней, сравнивал информацию о паре. Нашли несоответствия. Данные сохраняем, пользователя уведомляем. Сложность всех действий была O (n) по размеру массива сохраненных занятий и работала довольно быстро, не учитывая сортировку по дням недели и времени.

Изначальный алгоритм

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

Хорошо. Расширяем алгоритм, применяя логику к вспомогательным, а это уже становится довольно проблемно, выгрузи — найди — сравни. Хранятся они обособленно друг от друга. Расписания постоянно достаются из внутреннего хранилища, когда пользователь его ищет в сохраненных. А при обновлении — постоянно, по нескольку раз. И так с каждым. Добавление новых всё усложняло.

Читатель может сказать, можно вообще не смотреть на них и не проверять. Просто замени. Увы. Вернемся к техническому заданию и увидим «нужно применить функциональность главного». Об изменениях можно было не писать, но указать пользователю на них нужно. Идём дальше.

Добавление структуры данных HashMap

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

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

Алгоритм после добавления Hash

Алгоритм после добавления HashMap

Окончательная версия, хеш-функция

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

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

Коллизией хеш-функции называются

два разных набора сообщений a, b после преобразования которых получается одинаковый хеш-код hash (a) = hash (b).

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

Я использовал MD5. Он имеет низкий шанс коллизии у случайно взятых данных и высокую скорость работы. Хеш-функция ставит в соответствие входной строке 128 битную, разделенную на 32 символа в 16-ричном формате. Производим вычисления и получаем, что вероятность совпадения хеш-кодов у двух последовательных разных сообщений равна $1/2^{128}$ или $1/10^{38}$ .

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

Окончательная версия алгоритма

Заключение

Добавление структур данных и хеш-функций к изначальному алгоритму сравнений ускорило его. Контрольная сумма расписаний даёт нам заметную, но непостоянную оптимизацию в виде формального определителя изменений. Она сыграла роль предварительной проверки. Применение HashMap позволило ускорить поиск, как для доп. расписаний, так и в условиях нашей задачи.

На этом можно считать задачу решенной, а рассказ завершенным. Благодарю за внимание!

Код функции генерации хеша

public static String generateHash(String data) throws NoSuchAlgorithmException {

  //объявляем переменную которая будет хранить хеш-код
  String hashCode;

  // читаем строку как массив байт 
  byte[] byteArray = data.getBytes();

  // выбираем алгоритм шифрования,
  // передаем на вход массив байт исходной строки
  byte[] byteHash = MessageDigest.getInstance("SHA-256").digest(byteArray);

  // полученный хеш - код в виде массива байт,
  // переводим в строку длинной 32 знака в шестнадцатеричном формате.
  hashCode = HashMethods.bytesToHexString(byteHash);

  // возвращаем
  return hashCode;
 }

Вспомогательный метод перевода байтового представления в строчное