采访问题: HashSet -如何获得最少使用的对象？

Question

天啊，我现在接受了一次很棒的面试。不管你做了多少准备，你都会忘记一切。:)

我想趁这个问题还没来得及回答的时候，我可以和大家分享一下这个问题。

1)有1000个对象作为缓存保存。您应该以高效的方式创建缓存，以便搜索时间非常短。

显然，他们正在寻找一个提供恒定访问时间的HashSet。

2)如何在缓存中获取使用最少的(不是最老的而是最少的)的对象？如何使用哈希代码来实现这一点，以及如何在不执行任何昂贵的搜索的情况下获得这个存储桶？。

我正在考虑使用对象的时间戳作为哈希码。但是，如果不进行任何搜索，我如何才能得到最少使用的对象呢？

Answer 1

我的解决方案(我最近实现了类似的东西)是同时拥有Dictionary (Hashset)和ordered LinkedList。LinkedList将包含访问项和计数器。当您想要得到您的项目时，您查看Dictionary以获取LinkedList的节点，然后递增计数器并向前推节点以保持列表排序。当你想得到最不经常使用的项目时，你会取列表的标题(或尾)。

这使得检索O(1)和插入O(n)在最坏的情况(非常罕见)和O(1)的最佳情况。

Answer 2

我认为他们使用的方式是使用最近使用最少的缓存algo。有关维基百科的更多信息：缓存算法

在这个StackOverflow问题上也有一个LRU缓存。