On: Cache Eviction: When Are Randomized Algorithms Better Than LRU?

In my experience maintaining LRU queue has significant overhead. Random (hash based) displacement has almost zero overhead.

A fully-associative LRU cache can have significant overhead, yes. An 8-way set-associative LRU cache, not so much.