Ok I see where the difference is now. You are clearing the hit bit for all items marked as hit on a single eviction. I mean yes I guess that means that during the following request you don't have to check all items in the queue but now you have a different problem: you evict items prematurely. With a cache of size 2 I can't show it but consider a cache of size 3 and the following pattern: a, a, b, b, c, b, d, e

When d arrives state changes c(0) b(1) a(1) -> d(0) c(0) b(0). When e arrives state changes d(1) c(0) b(0) -> e(0) d(0) c(0).

Note how b got evicted from the cache even though it was requested more recently and more frequently than c because d cleared out the hit bit for both b and c.

Now you traded off hitrate vs latency. But the worst case latency is still O(n) just can't happen multiple times in a row anymore.

Imagine you have a cache of 1 million items all marked as hit and you get a new request which would evict all 1 million items. You gained latency for some subsequent requests but increased it in the current one. Crucially you also just cleared out the hit marker of whole cache.