什么数据结构通常用于LRU缓存和快速查找对象？ [英] What data structures are commonly used for LRU caches and quickly locating objects?

问题描述

我打算实现一个HashTable来快速找到对我的应用程序很重要的对象。

I intended to implement a HashTable to locate objects quickly which is important for my application.

但是，我不喜欢扫描的想法，锁定整个表以便定位上次访问的对象。表格可能非常大。

However, I don't like the idea of scanning and potentially having to lock the entire table in order to locate which object was last accessed. Tables could be quite large.

通常使用哪些数据结构来克服？

What data structures are commonly used to overcome that?

我想我可以把对象放入FIFO以及缓存，以便知道有多大的东西。但是这不支持LRU算法。

e.g. I thought I could throw objects into a FIFO as well as the cache in order to know how old something is. But that's not going to support an LRU algorithm.

任何想法？ squid如何做呢？

Any ideas? how does squid do it?

推荐答案

链接列表适用于LRU缓存。对于链接列表内的索引查找（将条目移动到链接列表的最近使用的末尾），请使用HashTable。最近最少使用的条目将始终是链接列表中的最后一个。

Linked lists are good for LRU caches. For indexed lookups inside the linked list (to move the entry to the most recently used end of the linked list), use a HashTable. The least recently used entry will always be last in the linked list.

这篇关于什么数据结构通常用于LRU缓存和快速查找对象？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！