LRU Cache без HashMap?
Мне нужно реализовать систему кеширования LRU в Java, в которой все операции выполняются в O (1), а все пример в сети используют HashMap, и мы можем использовать только очереди, стеки, списки и массивы. Может кто-нибудь объяснить теорию реализации? Я тоже не совсем понял ...
Я не понимаю, как вы можете реализовать кеш LRU с доступом O (1) без использования HashMap или другой структуры данных, которая дает вам доступ O (1) по ключу. Какие ключи вы используете для поиска элементов в кэше?
Я уже реализовал кеш-память fifo, массив (страниц), массив целых чисел, который содержит ключ для каждого индекса в массиве или -1 в противном случае, и очередь ключей
Могу ли я обойти использование хэш-карты с очередями массивов или списками?
Каковы ключи, структура ключей и ожидаемый диапазон ключей?
HashMap - это, по сути, внутренний массив списков.