Cache Data Structure

Описание

Структура данных, хранящая в себе объекты типа Record

Record {
    long account;
    String name;
    double value;
}

Позвоялет производить поиск по любому из ключей с асимптотической сложностью O(logN)

Обоснование

Задание было поставленно следующим образом:

ВОПРОС: Необходимо организовать хранение этих записей в памяти с
соблюдением требований:
1. предоставить возможность добавлять новые записи;
2. предоставить возможность удалять более не нужные записи;
3. предоставить возможность изменять запись;
4. получать полный набор записи по любому из полей с одинаковой
алгоритмической сложностью (не медленнее log(n));
5. выбрать наиболее экономный способ хранения данных в памяти.

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

Структура данных изнутри представляет из себя набор из трех TreeMap вида <ключ, референс на Record>.

TreeMap был выбран, потому что:

• Обеспечивает допустимую асимптотическую сложность поиска в O(logN)
  • Минимальный набор стандартных структур данных, чтобы это было возможно (3 Map'ы)
• Чуть более эффективно использует память
  • HashMap по дефолту может быть заполнена максимум на 75% до выделения новой памяти, в отличие от TreeMap
  • Однако самой памяти HashMap и TreeMap занимают примерно одинаково (~40 байт/элемент, включая overhead и alignment)

В связи с упомянутой абстрактностью, более экстремальные меры не рассматривались:

• Нет более экстремальной оптимизации памяти (есть библиотеки (ChronicleMap, LongHashMap - из того что нашел), которые реализовывают Map с меньшим memory footprint к примеру)
• Можно изобрести велосипед и придумать что-то еще более оптимизированное, не основываясь на существующих конейтнерах
• В зависимости от задачи можно вообще использовать in-memory СУБД (например H2), но там сложнее с поиском за O(logN)
• Не поддерживается многопоточность (синхронизация между тремя мапами при добавлении элемента?)
• Можно немного пожертвовать памятью взамен поиска элементов за О(1) (HashMap)
• Функционал кэша не был реализован (удаление ключей, если они не используются, к примеру как в WeakHashMap или в Google's Guava библиотеке)

Методы

• insertRecord(long account, String name, double value): Добавляет новую запись в кэш.
• insertRecord(Record record): Добавляет новый Record в кэш.
• deleteRecord(Record record): Удаляет указанную запись из кэша.
• updateRecord(Record oldRecord, Record newRecord): Обновляет существующую запись новой.
• Record getRecordFromAccount(long account): Извлекает Record, связанный с указанным аккаунтом.
• Record getRecordFromName(String name): Извлекает Record, связанный с указанным именем.
• Record getRecordFromValue(double value): Извлекает Record, связанный с указанным значением.
• int size(): Возвращает общее количество записей в кэше.

Ткаченко Никита, 2024 год