Code-Kata: Cache-Klasse. Wer produziert den besten Code

[idefix2]

Uwe Raabe hat es richtig geschrieben. Es fehlt in deiner Vorgabe eine zeitliche Komponente, ohne die wird keine gute Performance herauskommen (und dein eigener Lösungsansatz ignoriert deine Vorgabe übrigens komplett, der implementiert NUR die zeitliche Komponente).
Das Problem dabei: Wenn ab irgendeinem Zeitpunkt ein anderes (ganz neues) Element als die bisher häufigsten öfter gebraucht wird, dauert es sehr lange, bis das Element im Cache gelassen wird. Zu Beginn ist die "Wahrscheinlichkeit" nahe 0, und das Element wird sehr oft hinausgeworfen (und verursacht dadurch viele cache misses), bis es aufgeholt hat und im Speicher bleiben darf. Deshalb gehört unbedingt auch der Zeitfaktor in irgendeiner Form ins Spiel, in der einfachsten Form z.B., dass ein Element, das neu in den Cache geholt wurde, bei den nächsten n (n deutlich kleiner als die Cachegrösse) Malen, die ein Element aus dem Cache fliegt, geschützt wird.

Elemente, die vor langer Zeit oft benötigt wurden, inzwischen aber längst nicht mehr, behalten nach deiner Vorgabe eine sehr hohe "Wahrscheinlichkeit". Auch dagegen gibt es ein einfaches Mittel:
Für den ganzen Cache wird eine Zugriffsnummer bei jedem Zugriff hochgezählt. Bei jedem Element, auf das zugegriffen wurde, wird zuzätzlich zur um 1 erhöhten Häufigkeit auch die Zugriffsnummer gespeichert. Dann ergibt die Zugriffsnummer des Cache minus Zugriffsnummer eines Elements sein Alter (= wie lange wurde das Element nicht gebraucht). Für die Berechnung, welches Element rausfliegt, wird dann nicht nur die Zugriffshäufigkeit hergenommen, sondern (Zugriffshäufigkeit*a-Alter*b), wobei man mit den Parametern a und b die Gewichtung der beiden Faktoren zueinander optimieren kann.

Und natürlich muss die Häufigkeit auch für die Elemente gespeichert bleiben, die schon aus dem Cache rausgeflogen sind.