快捷導(dǎo)航

java實現(xiàn)LFU算法的示例代碼

更新時間：2023年11月21日 08:10:17 作者：技術(shù)驛站

LFU（Least Frequently Used）算法根據(jù)數(shù)據(jù)的歷史訪問頻率來淘汰數(shù)據(jù),其核心思想是“如果數(shù)據(jù)過去被訪問多次,那么將來被訪問的頻率也更高”,本文為大家整理了Java實現(xiàn)LFU算法的示例代碼,需要的可以參考下

使用JAVA語言實現(xiàn)常用的LFU（Least Frequently Used）算法

定義一個LFUNode類來表示LFU緩存中的節(jié)點

private static class LFUNode<K, V> {
    K key;
    V value;
    int frequency;

    public LFUNode(K k, V v) {
        key = k;
        value = v;
        frequency = 1;
    }
}

接下來，我們創(chuàng)建一個LFUCache類來實現(xiàn)LFU緩存。在初始化函數(shù)中，我們需要指定緩存的最大容量。

public class LFUCache1<K, V> {
    private int capacity;
    private Map<K, LFUNode<K, V>> cacheMap;
    private Map<Integer, LinkedHashSet<LFUNode<K, V>>> frequencyMap;
    private int minFrequency;

    public void init(int size) {
        this.capacity = size;
        cacheMap = new HashMap<>();
        frequencyMap = new HashMap<>();
        minFrequency = 0;
    }
    ...

接下來，我們實現(xiàn)兩個輔助方法：

addToFrequencyMap：將節(jié)點添加到對應(yīng)頻率的鏈表中。
removeFromFrequencyMap：從對應(yīng)頻率的鏈表中移除節(jié)點。

private void addToFrequencyMap(LFUNode<K, V> node) {
    int frequency = node.frequency;
    frequencyMap.putIfAbsent(frequency, new LinkedHashSet<>());
    frequencyMap.get(frequency).add(node);

    if (frequency == 1) {
        minFrequency = 1;
    }
}

private void removeFromFrequencyMap(LFUNode<K, V> node) {
    int frequency = node.frequency;
    frequencyMap.get(frequency).remove(node);

    if (frequency == minFrequency && frequencyMap.get(frequency).size() == 0) {
        minFrequency++;
    }
}

最后實現(xiàn)核心方法：get和put

public V get(K key) {
    if (cacheMap.containsKey(key)) {
        LFUNode<K, V> node = cacheMap.get(key);
        removeFromFrequencyMap(node);
        node.frequency++;
        addToFrequencyMap(node);
        return node.value;
    }
    return null;
}

public void put(K key, V value) {
    if (capacity <= 0) {
        return;
    }

    if (cacheMap.containsKey(key)) {
        LFUNode<K, V> node = cacheMap.get(key);
        removeFromFrequencyMap(node);
        node.value = value;
        node.frequency++;
        addToFrequencyMap(node);
    } else {
        if (cacheMap.size() >= capacity) {
            LinkedHashSet<LFUNode<K, V>> minFrequencySet = frequencyMap.get(minFrequency);
            LFUNode<K, V> evictNode = minFrequencySet.iterator().next();
            minFrequencySet.remove(evictNode);
            cacheMap.remove(evictNode.key);
        }

        LFUNode<K, V> newNode = new LFUNode<>(key, value);
        cacheMap.put(key, newNode);
        addToFrequencyMap(newNode);
        minFrequency = 1;
    }
}

最終驗證結(jié)果如下：

@Test
public void testCase() {
    LFUCache1<Integer, String> cache = new LFUCache1<>();
    cache.init(2);
    cache.put(1, "Hello");
    cache.put(2, "World");
    System.out.println(cache.get(1));  // Output: Hello
    cache.put(3, "Foo");
    System.out.println(cache.get(2));  // Output: null (evicted)
    System.out.println(cache.get(3));  // Output: Foo
}

到此這篇關(guān)于java實現(xiàn)LFU算法的示例代碼的文章就介紹到這了,更多相關(guān)java LFU算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: