Следует иметь в виду, что когда речь идет о кэше, это избыточная структура данных, единственная цель которой - ускорить выборку данных.
Таким образом, когда часть данных извлекается из кэша, это не имеет никакого значения (кроме скорости выполнения) для программы, которая использует эти данные, потому что она будет затем извлечена из основной памяти. Таким образом, в любом случае ваш файл будет работать точно так же, независимо от того, какая его часть находится в кэше или нет.
Это очень важно, потому что это позволяет нам кодировать на языках высокого уровня, таких как Java, не заботясь о политике замены кэша, реализованной процессором. Если бы это было не так, это было бы кошмаром, потому что мы должны были бы принять во внимание всю существующую (и будущую?) Политику замены, реализованную в процессорах. Даже не упоминая, что эти политики не так просты, как LRU (есть наборы кеша, которые делят кеш на «строки», и их поведение также в значительной степени связано с их физической структурой), и что место, где будет располагаться фрагмент данных Нахождение в кеше зависит от его адреса в основной памяти, который не обязательно будет одинаковым для каждого выполнения кода.
Короче говоря, две вещи, о которых вы упомянули (три узла в java и политики кэширования LRU), находятся слишком далеко друг от друга (одно - очень, очень низкоуровневое программирование, другое - высокоуровневое). Вот почему мы редко, если вообще когда-либо, рассматриваем их взаимодействие.
Если вы реализуете Trie в java, ваша задача - убедиться, что он работает хорошо во всех ситуациях, что он хорошо спроектирован, чтобы обслуживание было легче (возможно), чтобы его можно было прочитать, чтобы другие программисты могли когда-нибудь поработать над ним. В конце концов, если он все еще работает слишком медленно, вы можете попытаться оптимизировать его (после определения узких мест, никогда прежде).
Но если вы хотите связать свой trie с хитом / промахом кэша и политиками замены, вам придется прочитать перевод вашей реализации в байт-код (выполненный JVM).
PS: в своем посте вы говорите о превышении имитации памяти. Нет такой вещи для программы. Когда кеш заполнен, мы заполняем основную память. Когда основная память заполнена, операционные системы обычно резервируют часть жесткого диска, чтобы играть роль основной памяти (мы называем это подкачкой, и когда это происходит, компьютер работает так же, как и завис). Когда своп полон, происходит сбой программ. Все они.
В «уме» программы операционная система предоставляет ей абсолютно гигантские объемы памяти (которая является виртуальной, но для программы она так же хороша, как и реальная), которая никогда не будет заполнена. Сама программа не «осознает» способ управления памятью и объем оставшейся памяти по многим веским причинам (безопасность, гарантия того, что все программы будут иметь значительную долю ресурсов ...)