Я новичок в программировании вообще и в Java в частности. Я хочу реализовать кеш LRU и хотел бы иметь сложность O (1).LRU без отметки времени и HashMap - Java
Я видел некоторые реализации в Интернете, используя вручную реализованный дважды связанный список для кеша (два массива, класс Node, предыдущий, следующий и т. Д.) И HashMap, где Key - это элемент, который нужно кэшировать, а значение - отметка времени.
Я действительно не вижу причины использовать временные метки: вставленный элемент отправляется в голову реализованного вручную LinkedList, выведенный элемент - это кешированный элемент, расположенный в хвосте, и при каждой вставке ранее кэшированные элементы сдвинуты на одну позицию по направлению к хвосту.
Единственные проблемы, которые я вижу в следующем:
Для поиска тайника (найти, если у нас есть кэш хит или пропустить запрошенный пункт), мы должны «сканировать» кэш список, который подразумевает цикл for некоторого типа (обычный, для каждого и т. д., на данный момент меня это не очень устраивает). Очевидно, мы этого не хотим. Я считаю, что эту проблему можно легко решить, используя массив логических переменных, чтобы указать, находится ли элемент в кеше или нет (1: in, 0: out) - назовем его lookupArray - следующим образом: предположим, что элементы отличающийся некоторым числовым идентификатором, т. е. целое число от 1 до N. Тогда этот lookupArray из булевых будет иметь размер N + 1 (поскольку индексирование массива начинается с нуля), и оно будет инициализировано при всех нулевых значениях. Когда элемент с числовым идентификатором k, где 1 < = k < = N, входит в кеш, мы устанавливаем логическое значение в индексе k lookupArray равным 1. Таким образом, поиск кэша не нуждается в поиске в кеше: по порядку чтобы проверить, находится ли элемент с числовым идентификатором k в кеше или нет, мы просто проверяем, является ли значение lookupArray по индексу k равно 1 или 0 соответственно. (У нас уже есть индекс, т. Е. Мы знаем, где искать, поэтому нет необходимости использовать цикл for.)
Вторая проблема, однако, не разрешима. Допустим, что у нас есть кеш для элемента. Затем, если этот элемент не находится в голове (т. Е. Если он не является последним используемым элементом), мы должны найти его в списке кеша, а затем поместить его в начало. Насколько я понимаю, это подразумевает поиск в списке кеша, т. Е. Цикл for. Тогда мы не сможем достичь цели O (1).
Имею ли я право (2)? Есть ли способ сделать это без использования HashMap и временных меток?
В связи с тем, что я относительно новичок в программировании, о котором я говорил в начале сообщения, я был бы очень признателен за использование, если возможно, любых фрагментов кода, демонстрирующих реализацию с вручную реализованным дважды связанным списком.
Извините за длинное сообщение, надеюсь, что оно не только детализировано, но и понятно.
Спасибо!
Читать исходный код [LinkedHashMap] (http://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html), и вы увидите, как O (1). –