Тестовое задание для Java-разработчика
Данная реализация использует LinkedHashMap для хранения информации о ключах
и соответствующих им значениях в порядке добавления.
Это предоставляет информацию о самом давно используемом ключе, находящемся в начале списка карты,
и возможность его удаления в случае переполнения кеша.
Перемещение ключа в конец списка карты происходит путём его удаления и последующего добавления.
Ключ перемещается в конец списка карты в случае его добавления или обращения к нему.
Всё это позволяет производить операции по добавлению / чтению / удалению элементов за константное O(1) время.
Данная реализация использует следующие структуры данных:
- двусвязный список, состоящий из узлов типа
Node, хранящих информацию о ключе, значении и частоте. - указатель на головной узел двусвязного списка.
HashMap<KEY, Node>- для хранения информации о ключах и соответствующих им узлах.HashMap<FREQUENCY, Node>- для хранения информации о самом недавно используемом узле для каждой существующей частоты.
Постоянное отслеживание головного узла и самого давно используемого узла для каждой частоты позволяет проводить все необходимые операции по перемещению узлов между частотными подпоследовательностями. Ранее не существующий узел при добавлении примет нулевую частоту. Частота узла инкрементируется при его чтении или изменении связанного с ним значения. При инкрементировании частоты узел изымается из подпоследовательности, относящейся к старой частоте, и вставляется в конец подпоследовательности, относящейся к новой частоте. При отсутствии информации о самом давно используемом узле следующей подпоследовательности вставка узла происходит в конец текущей подпоследовательности, тем самым не нарушая целостность последовательности.
Всё это позволяет производить операции по добавлению / чтению / удалению элементов за константное O(1) время.