参考LRU缓存设计
我有一个关于答案的问题。
假设我的哈希映射已满（面试官给了我一个最大尺寸）[我知道如果我需要获取映射中已经存在的一对，我会将列表条目移到前面以指示最近使用。]
但是，如果我有一个要添加的条目并且这个键散列到与不同键相同的位置怎么办。（碰撞）我该怎么办？
我做链接或探测吗？如果我进行链接，我应该增加地图大小吗？如果我删除最旧的条目，它会清空我的哈希图中的一个位置。但是一个新条目可能不会散列到这个位置？它可能会散列到另一个完整条目？（不同的键，值对）如何解决这个问题？
问问题
2436 次
2 回答
1
这种设计将不包括链接，因为我们在这里设计一个直接映射缓存，并且这种折衷是已知的，直接映射缓存只考虑条目在从缓存中删除之前的新近度，而不是被请求的频率。
最大大小限制将施加在链表大小上，并且每次我们在链表已满时尝试添加新条目时，都会删除最后使用的条目（链表）和相应的映射条目。要插入新条目的位置与删除的内容无关。
有关并发的更多详细信息，请查看此链接。
于 2013-01-29T17:16:16.230 回答
0
map 的大小是 Map 中存在的键值对的数量，因此它与键值对是否存在于相同的哈希桶中或不同的哈希桶中无关。
因此，如果您检查 hashmap 的数据结构，它的链表数组，那么当存在哈希冲突时，就会出现链接，并且映射的大小也会增加。
现在，如果您的新条目散列到不为空的位置，您需要像我们在链接列表中那样进行链接。
PS：对于 LRU Cache 你可以看到LinkedHashMap
于 2012-10-11T05:19:30.867 回答