面试题答案
一键面试命中率
- LRU（最近最少使用）：理论上能较好适应局部性原理，如果数据访问存在时间局部性，即最近访问过的数据很可能再次被访问，LRU命中率较高。例如在Web浏览器缓存中，用户近期访问的网页更可能再次访问，LRU能有效缓存这些页面。
- LFU（最不经常使用）：对于访问频率相对稳定的数据，LFU能根据访问频率淘汰最不经常使用的数据，命中率可能较高。但如果数据访问模式突然改变，LFU可能需要一定时间适应，导致命中率下降。例如在文件系统缓存中，如果文件访问频率相对稳定，LFU可以有效缓存常用文件。
- FIFO（先进先出）：不考虑数据访问的频率和时间，只按照进入缓存的先后顺序淘汰数据，对于存在时间局部性的数据场景，命中率通常较低。比如在数据库查询缓存中，若采用FIFO，刚查询过的新数据可能很快因缓存满被淘汰，即使后续可能再次查询。
内存使用效率
- LRU：能较好利用内存，优先淘汰长时间未使用的数据，使内存中尽量保留近期可能使用的数据。但在某些情况下，可能会误淘汰虽不常使用但未来可能会用的数据。
- LFU：根据访问频率分配内存，理论上能将内存更多分配给高频数据。然而，LFU需要记录每个数据的访问次数，这增加了额外的内存开销。
- FIFO：简单按顺序淘汰，可能会保留一些长时间未使用但近期可能需要的数据，导致内存空间浪费，内存使用效率相对较低。
实现复杂度
- LRU：可以使用哈希表和双向链表实现。哈希表用于快速定位数据，双向链表用于记录数据的访问顺序，实现复杂度适中。
- LFU：除了需要类似LRU的结构外，还需额外记录每个数据的访问频率，实现较为复杂。例如需要维护一个频率表，记录不同频率的数据链表等。
- FIFO：只需使用队列结构即可实现，新数据入队，缓存满时队首数据出队，实现复杂度最低。
业务场景及选择原因
- LRU：适用于Web应用缓存、操作系统页面置换等场景。如Web应用中，用户行为常表现出时间局部性，最近访问的页面可能再次访问，LRU能有效缓存这些页面，提高命中率。
- LFU：适用于数据访问频率相对稳定的场景，如CDN（内容分发网络）缓存。在CDN中，某些热门内容的访问频率相对稳定，LFU可根据访问频率缓存这些内容，提高缓存效率。
- FIFO：适用于对数据新鲜度要求不高，且希望实现简单的场景，如日志缓存。日志记录通常只需要保留一定时间内的最新记录，FIFO能满足这种需求且实现简单。