Tag Archives: 缓存算法

上一节中我们实现了随机缓存算法和FIFO缓存算法。现在，我们会继续实现另外两个著名的缓存算法：LFU和LRU。再一次说明，这些代码只是作为演示使用，如果你想在应用程序中使用，你还需要加上额外的工作。 看看LFU缓存算法的实现 public synchronized Object getElement(Object key) { Object obj; obj = table.get(key); if (obj != null) { CacheElement element = (CacheElement) obj; element.setHitCount(element.getHitCount() + 1); return element.getObjectValue(); } return null; } public final synchronized void addElement(Object key, Object value) … Continue reading →

在这一部分中，我们来看看如何实现这些著名的缓存算法。以下的代码只是示例用的，如果你想自己实现缓存算法，可能自己还得加上一些额外的工作。 LeftOver机制 在 programmer one 阅读了文章之后，他接着看了文章的评论，其中有一篇评论提到了leftover机制——random cache。 Random Cache： 我是随机缓存，我随意的替换缓存实体，没人敢抱怨。你可以说那个被替换的实体很倒霉。通过这些行为，我随意的去处缓存实体。我比FIFO机制好，在某些情况下，我甚至比 LRU 好，但是，通常LRU都会比我好。 现在是评论时间 当programmer one 继续阅读评论的时候，他发现有个评论非常有趣，这个评论实现了一些缓存算法，应该说这个评论做了一个链向评论者网站的链接，programmer one顺着链接到了那个网站，接着阅读。 看看缓存元素（缓存实体） public class CacheElement { private Object objectValue; private Object objectKey; private int index; private int hitCount; // getters and setters } 这个缓存实体拥有缓存的key和value，这个实体的数据结构会被以下所有缓存算法用到。 … Continue reading →

接着之前的 part 2：http://www.zavakid.com/26 在programmer one 醒来之后，他又开始阅读文章了。 缓存算法 没有人能说清哪种缓存算法由于其他的缓存算法。（以下的几种缓存算法，有的我也理解不好，如果感兴趣，你可以Google一下 ） Least Frequently Used（LFU）： 大家好，我是 LFU，我会计算为每个缓存对象计算他们被使用的频率。我会把最不常用的缓存对象踢走。 Least Recently User（LRU）： 我是LRU缓存算法，我把最近最少使用的缓存对象给踢走。 我总是需要去了解在什么时候，用了哪个缓存对象。如果有人想要了解我为什么总能把最近最少使用的对象踢掉，是非常困难的。 浏览器就是使用了我（LRU）作为缓存算法。新的对象会被放在缓存的顶部，当缓存达到了容量极限，我会把底部的对象踢走，而技巧就是：我会把最新被访问的缓存对象，放到缓存池的顶部。 所以，经常被读取的缓存对象就会一直呆在缓存池中。有两种方法可以实现我，array 或者是 linked list。 我的速度很快，我也可以被数据访问模式适配。我有一个大家庭，他们都可以完善我，甚至做的比我更好（我确实有时会嫉妒，但是没关系）。我家庭的一些成员包括LRU2 和 2Q，他们就是为了完善 LRU 而存在的。 Least Recently Used 2（LRU2）： 我是 Least Recently Used 2，有人叫我最近最少使用twice，我更喜欢这个叫法。我会把被两次访问过的对象放入缓存池，当缓存池满了之后，我会把有两次最少使用的缓存对象踢走。因为需要跟踪对象2次，访问负载就会随着缓存池的增加而增加。如果把我用在大容量的缓存池中，就会有问题。另外，我还需要跟踪那么不在缓存的对象，因为他们还没有被第二次读取。我比LRU好，而且是 adoptive to … Continue reading →