面试问题：HashSet - 如何获取最少使用的对象？
天哪，我现在经历了一场糟糕的采访。无论你做了多少准备，你一进去就会忘记一切。 :)
我想我应该趁这个问题还新鲜的时候来分享它。
1) 您有 1000 个对象作为缓存。您应该以有效的方式创建缓存，以便搜索时间非常短。
显然他们正在寻找提供恒定访问时间的 HashSet。
2) 如何获取缓存中最少（不是最旧而是最少）使用的对象？使用什么作为哈希码来实现这一点，以及如何在不进行任何昂贵的搜索的情况下获取这个存储桶？
我正在考虑使用对象的时间戳作为哈希码。但是我如何在不进行任何搜索的情况下获得最少使用的对象呢？
Gosh I had right now a hell of an interview. No matter how much you prepare you go in and forget everything. :)
I thought I would share the question while it's fresh in my mind.
1) You have 1000 objects hold as a cache. You are supposed to create the cache in an efficient manner so that the search time is very short.
Obviously they were looking for a HashSet that provides constant access time.
2) How to get the object within the cache that was least (not oldest but least) used? What to use as hashcode to achieve this, and how to get this bucket without doing any expensive searching?
I was thinking to use the timestamp of the objects as a hashcode. But how would I get the least used object without doing any search?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我的解决方案（我最近实现了类似的方法）是同时拥有
Dictionary（哈希集）和有序的LinkedList。LinkedList将包含访问的项目和计数器。当您想要获取项目时，您可以查看字典来获取 LinkedList 的节点，然后递增计数器并将节点向前推以保持列表排序。当您想要获取最不常用的项目时，您可以选择列表的头部（或尾部）。这使得在最坏（非常罕见）情况下检索
O(1)和插入O(n)以及在最好情况下O(1)。My solution (I recently implemented something like this) is to have both
Dictionary(Hashset) and orderedLinkedList.LinkedListwill contain item and counter of access. When you want to get your item, you look intoDictionaryto get node of LinkedList, then you increment counter and push node forward to keep list sorted. When you want to get least frequently used item you take head (or tail) of list.This makes retrieval
O(1)and insertionO(n)in worst (very rare) case andO(1)best case.我认为他们的方法是使用最近最少使用的缓存算法。维基百科上的更多信息： 缓存算法
此 StackOverflow 问题。
I think the way that they were going is to use something like a Least Recently Used cache algo. More info here on wikipedia: Cache Algorithms
There is also an LRU cache at this StackOverflow question.