concept LFU in category algorithms

This is an excerpt from Manning's book Algorithms and Data Structures in Action MEAP V14. Login to get full access to this book.

The algorithm used to decide what data stays in the cache determines the behavior of the cache and the rate of cache hit (when the data searched for are already in the cache) and miss. Some of the most used algorithms are LRU (Least Recently Used), MRU (Most Recently Used) and LFU (Least Frequently Used). Chapter 6 gets into the details of these algorithms, but for now it is enough to mention that they, as well as many other cache replacement policies, all suffer "one-hit-wonders". In other words, they struggle with objects, memory locations or web pages requested just once, and never again (in the average lifetime of the cache). This is particularly common for routers and Content Delivery Networks (CDNs), were an average of 75% of the requests for a node are one-hit-wonders.

#1 Check that the cache is not empty.