<返回更多

一文读懂常见的缓存策略

2023-11-21  微信公众号  沐雨花飞蝶
加入收藏

缓存策略介绍

缓存是一种用于临时存储数据的技术,旨在提高数据访问速度和性能。通过将常用的数据存储在缓存中,可以减少对原始数据存储位置的访问次数,从而加快数据的读取速度。缓存通常用于加速计算机系统、网络和Web应用程序的性能。

常见的缓存策略包括:

  1. 「FIFO(First In, First Out)」:先进先出,最先进入缓存的数据最先被淘汰。
  2. 「LRU(Least Recently Used)」:最近最少使用,根据数据最近被访问的时间来淘汰缓存中的数据。
  3. 「LFU(Least Frequently Used)」:最不经常使用,根据数据被访问的频率来淘汰缓存中的数据。
  4. 「随机替换」:随机选择要淘汰的数据。

FIFO缓存策略

FIFO(First In, First Out)是一种缓存替换策略,它按照数据进入缓存的顺序来进行替换。当缓存已满并且需要替换新的数据时,FIFO策略会选择最早进入缓存的数据进行替换。

在FIFO策略中,新数据被加入到缓存的末尾,而替换时会选择缓存中最早进入的数据进行替换。这种策略简单直观,但可能会导致缓存中的热数据被频繁替换,影响缓存的命中率。

数学公式表示FIFO缓存替换策略如下:

假设缓存大小为N,缓存中已有n个数据,新数据为x,则替换时选择的数据为缓存中最早进入的数据,即第一个进入缓存的数据。

FIFO缓存策略实现(JAVA)

FIFO缓存适用于以下使用场景:

在Java中,可以使用LinkedHashMap来实现FIFO缓存策略。LinkedHashMap继承自HashMap,它保留了插入顺序,因此非常适合用来实现FIFO缓存。

import java.util.LinkedHashMap;
import java.util.Map;

public class FIFOCache<K, V> extends LinkedHashMap<K, V> {
    private int capacity;

    public FIFOCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void mAIn(String[] args) {
        FIFOCache<String, Integer> cache = new FIFOCache<>(3);
        cache.put("A", 1);
        cache.put("B", 2);
        cache.put("C", 3);
        System.out.println(cache); // 输出:{A=1, B=2, C=3}
        cache.put("D", 4);
        System.out.println(cache); // 输出:{B=2, C=3, D=4}
    }
}

在上面的示例中,我们创建了一个FIFOCache类,继承自LinkedHashMap,并重写了removeEldestEntry方法来控制缓存的大小和淘汰策略。

LRU缓存策略

LRU(Least Recently Used)缓存策略是一种常见的缓存淘汰策略,它根据数据的访问时间来淘汰最近最少使用的数据。当缓存空间不足时,会淘汰最近最少被访问的数据,以便为新数据腾出空间。

LRU缓存策略通常通过双向链表和哈希表来实现。双向链表用于记录数据的访问顺序,哈希表用于快速查找数据在链表中的位置。当数据被访问时,如果数据已经在缓存中,则将其移动到链表头部;如果数据不在缓存中,则将其添加到链表头部,并在哈希表中记录其位置。当需要淘汰数据时,可以直接从链表尾部淘汰最近最少被访问的数据。

LRU缓存策略的优点是能够有效地利用缓存空间,将最常用的数据保留在缓存中,提高访问速度。但是实现起来相对复杂,需要维护链表和哈希表的一致性,并且在高并发场景下可能存在性能瓶颈。

数学公式表示LRU缓存策略的淘汰规则可以用如下的方式表示:

设  为缓存的大小, 表示第  个数据被访问的时间,则淘汰规则可以表示为:

淘汰规则:

LRU缓存策略实现(Java)

LRU缓存适用于需要频繁访问数据的场景,例如:

以下是一个简单的Java使用LinkedHashMap来实现LRU缓存:

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int MAX_ENTRIES;

    public LRUCache(int maxEntries) {
        super(maxEntries, 0.75f, true);
        MAX_ENTRIES = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > MAX_ENTRIES;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "One");
        cache.put(2, "Two");
        cache.put(3, "Three");
        System.out.println(cache); // 输出: {1=One, 2=Two, 3=Three}
        cache.put(4, "Four");
        System.out.println(cache); // 输出: {2=Two, 3=Three, 4=Four}
    }
}

在这个示例中,LRUCache继承自LinkedHashMap,并重写了removeEldestEntry方法来控制缓存的大小。当缓存超过指定大小时,最近最少使用的条目将被移除。

LFU缓存策略

LFU(Least Frequently Used)缓存策略是一种常见的缓存替换策略,它根据缓存中数据项被访问的频率来进行替换。具体来说,当缓存空间不足时,LFU算法会淘汰访问频率最低的数据项。

LFU缓存策略的实现通常需要维护一个访问频率的计数器,以及一个数据项和其对应访问频率的映射。当数据项被访问时,其对应的访问频率会增加,当需要替换数据项时,会选择访问频率最低的数据项进行淘汰。

在LFU缓存策略中,如果有多个数据项的访问频率相同,那么通常会选择最早被访问的数据项进行淘汰。

LFU缓存策略的优点是能够有效地淘汰访问频率低的数据项,但缺点是需要维护额外的访问频率计数器,增加了实现的复杂度。

在实际应用中,LFU缓存策略通常用于需要频繁访问的数据项,以便保持缓存中的数据项是最常被访问的。

LFU缓存策略实现(Java)

LFU缓存策略适用于需要根据数据访问频率来淘汰缓存的场景。在这种策略下,会优先淘汰访问频率最低的数据,以便为访问频率高的数据腾出空间,从而提高缓存命中率。

LFU缓存策略常用于以下场景:

在Java中,可以通过使用LinkedHashMap来实现LFU缓存策略。LinkedHashMap可以按照访问顺序或插入顺序来维护键值对,通过重写removeEldestEntry方法和自定义数据结构来实现LFU缓存策略。

以下是一个简单的Java实现LFU缓存策略的示例代码:

import java.util.*;

public class LFUCache<K, V> extends LinkedHashMap<K, V> {
    private Map<K, Integer> freqMap;

    public LFUCache(int capacity) {
        super(capacity, 0.75f, true);
        freqMap = new HashMap<>();
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity();
    }

    public V get(K key) {
        if (super.containsKey(key)) {
            freqMap.put(key, freqMap.get(key) + 1);
        }
        return super.get(key);
    }

    public void put(K key, V value) {
        if (!super.containsKey(key)) {
            freqMap.put(key, 1);
        }
        super.put(key, value);
    }

    public static void main(String[] args) {
        LFUCache<Integer, String> cache = new LFUCache<>(2);
        cache.put(1, "a");
        cache.put(2, "b");
        System.out.println(cache.get(1)); // 输出: a
        cache.put(3, "c");
        System.out.println(cache.get(2)); // 输出: null
    }
}

在上述示例中,通过继承LinkedHashMap并重写removeEldestEntry方法,以及使用freqMap来记录访问频率,实现了LFU缓存策略的简单Java实现。

随机替换缓存策略

随机替换缓存策略是指在需要替换缓存中的数据时,随机选择一个数据进行替换。这种策略不考虑数据的访问频率或者其他因素,只是简单地随机选择一个数据进行替换。

数学表示为:选择要替换的数据的概率是相等的,即每个数据被替换的概率都是1/n,其中n为缓存中数据的数量。

这种策略的优点是实现简单,但缺点是不能充分利用数据的访问模式,可能导致缓存命中率降低。

随机替换缓存策略实现(Java)

随机替换缓存策略是一种简单的缓存替换策略,它随机选择一个缓存条目进行替换,适用于对缓存命中率要求不高的场景。

 
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class RandomReplacementCache<K, V> {
    private Map<K, V> cache;
    private Random random;

    public RandomReplacementCache() {
        this.cache = new HashMap<>();
        this.random = new Random();
    }

    public void put(K key, V value) {
        // 添加缓存条目
        cache.put(key, value);
    }

    public V get(K key) {
        // 获取缓存条目
        return cache.get(key);
    }

    public void evictRandom() {
        // 随机替换缓存条目
        if (!cache.isEmpty()) {
            int randomIndex = random.nextInt(cache.size());
            K keyToRemove = (K) cache.keySet().toArray()[randomIndex];
            cache.remove(keyToRemove);
        }
    }
}

在上面的示例中,我们使用了HashMap来实现缓存,通过Random类来实现随机替换缓存条目的功能。

关键词:缓存      点击(15)
声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多缓存相关>>>