常见算法 #

package com.example.demo.util;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
/**
 * @author dehua.xiang
 * @date 2023/3/24-10:20
 */
public class LFUCache<T> {

    /**
     * 内部类Node用于存储key和value以及对应的访问次数和最后访问的时间戳
     * @param <T>
     */
    private static class Node<T> implements Comparable<Node<T>> {
        String key;
        T value;
        int frequency;
        long timestamp;

        public Node(String key, T value) {
            this.key = key;
            this.value = value;
            this.frequency = 0;
            this.timestamp = System.nanoTime();
        }

        // compareTo方法用于PriorityQueue的排序，优先级低的先被移除
        @Override
        public int compareTo(Node other) {
            if (this.frequency == other.frequency) {
                return (int)(this.timestamp - other.timestamp);
            }
            return this.frequency - other.frequency;
        }
    }

    /**
     * 缓存的最大容量
     * 当缓存中的元素数量达到了capacity时，需要进行淘汰策略，即移除访问频次最低的元素，给新元素腾出空间。
     */
    private final int capacity;
    /**
     * 缓存
     */
    private final Map<String, Node<T>> cache;

    /**
     * 优先级队列
     */
    private final PriorityQueue<Node<T>> queue;

    /**
     * 记录节点最后一次被访问的时间戳
     */
    private long timestamp;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
        queue = new PriorityQueue<>(capacity);
        timestamp = 0;
    }

    public T get(String key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        this.timestamp = System.nanoTime();

        Node<T> node = cache.get(key);
        queue.remove(node);
        node.frequency++;
        node.timestamp = System.nanoTime();
        queue.offer(node);

        return node.value;
    }

    public void put(String key, T value) {
        if (capacity == 0) {
            return;
        }
        Node<T> node = cache.get(key);
        if (node != null) {
            node.value = value;
            node.frequency++;
            node.timestamp = System.nanoTime();
        } else {
            if (cache.size() >= capacity) {
                // 获取队首元素
                Node<T> removeNode = queue.peek();
                if (removeNode != null) {
                    cache.remove(removeNode.key);
                    // 移除队首元素
                    queue.poll();
                }
            }
            node = new Node<>(key, value);
            cache.put(key, node);
            queue.offer(node);
        }
    }
}

package com.example.demo.util;

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

/**
 * @author dehua.xiang
 * @date 2023/3/24-10:48
 */
public class LRUCache<K, V> {


    private final int capacity;
    private final Map<K, Node<K, V>> cacheMap;
    private Node<K, V> head;
    private Node<K, V> tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cacheMap = new HashMap<>(capacity);
    }

    public V get(K key) {
        Node<K, V> node = cacheMap.get(key);
        if (node == null) {
            return null;
        }
        updateNode(node);
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> node = cacheMap.get(key);
        if (node != null) {
            node.value = value;
            updateNode(node);
        } else {
            if (cacheMap.size() >= capacity) {
                removeHead();
            }
            Node<K, V> newNode = new Node<>(key, value);
            cacheMap.put(key, newNode);
            addToTail(newNode);
        }
    }

    private void updateNode(Node<K, V> node) {
        if (node == tail) {
            return;
        }
        // 头结点的后驱结点设置为队列头结点
        if (node == head) {
            head = head.next;
        } else {
            // 当前的前驱的后继结点指向 队列的后驱结点
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        // 头结点直接移动到队尾
        addToTail(node);
    }

    private void removeHead() {
        cacheMap.remove(head.key);
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
    }

    private void addToTail(Node<K, V> node) {
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
            node.prev = tail;
            node.next = null;
        }
        tail = node;
    }

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

package com.example.demo.util;

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

/**
 * @author dehua.xiang
 * @date 2023/3/24-11:06
 */
public class TimedCache<K, V> {

    // 用 HashMap 存储缓存项
    private final Map<K, CacheItem<V>> cacheMap;

    public TimedCache() {
        this.cacheMap = new HashMap<>();
    }

    public void put(K key, V value){
        put(key,value,-1);
    }


    public synchronized void put(K key, V value, long expireTime) {
        long expireTimestamp = (expireTime > 0) ? (System.currentTimeMillis() + expireTime) : Long.MAX_VALUE;
        cacheMap.put(key, new CacheItem<>(value, expireTimestamp));
    }

    public V get(K key) {
        CacheItem<V> item = cacheMap.get(key);
        if (item == null || item.isExpired()) {
            cacheMap.remove(key);
            return null;
        }
        return item.getValue();
    }

    public synchronized void clear() {
        cacheMap.clear();
    }

    private static class CacheItem<V> {

        private final V value;
        private final long expireTimestamp;

        public CacheItem(V value, long expireTimestamp) {
            this.value = value;
            this.expireTimestamp = expireTimestamp;
        }

        public V getValue() {
            return value;
        }

        public boolean isExpired() {
            return System.currentTimeMillis() >= expireTimestamp;
        }
    }
}

public interface Limiter {

    boolean allow();
}

public class CounterRateLimiter implements Limiter {
    /**
     * 限制的请求数量
     */
    private final int limit;
    /**
     * 限制的时间间隔，单位为毫秒
     */
    private final long interval;
    /**
     * 计数器，用于记录当前时间窗口内已经处理的请求数量
     */
    private final AtomicInteger count = new AtomicInteger(0);
    /**
     * 上一次计数器重置的时间
     */
    private volatile long lastResetTime;

    public CounterRateLimiter(int limit, long interval) {
        this.limit = limit;
        this.interval = interval;
        this.lastResetTime = System.currentTimeMillis();
    }

    @Override
    public synchronized boolean allow() {
        long now = System.currentTimeMillis();
        // 超过时间间隔，需要重置计数器
        if (now - lastResetTime >= interval) {
            count.set(0);
            lastResetTime = now;
        }
        int currentCount = count.incrementAndGet();
        // 超过限制的请求数量，拒绝处理请求
        return currentCount <= limit;
    }
}

public class LeakyBucketRateLimiter implements Limiter {
    /**
     * 桶的容量
     */
    private final int capacity;
    /**
     * 流出速率，单位为请求数/秒
     */
    private final int rate;
    /**
     * 桶中当前的水量
     */
    private int water;
    /**
     * 上一次漏水的时间
     */
    private long lastLeakTime;

    public LeakyBucketRateLimiter(int capacity, int rate) {
        this.capacity = capacity;
        this.rate = rate;
        this.water = 0;
        this.lastLeakTime = System.currentTimeMillis();
    }

    @Override
    public synchronized boolean allow() {
        long currentTime = System.currentTimeMillis();
        long timeElapsed = currentTime - lastLeakTime;
        //漏水的数量
        int leakedWater = (int) (timeElapsed * rate / 1000);
        //更新桶中的水量
        water = Math.max(0, water - leakedWater);
        lastLeakTime = currentTime;
        //桶未满，可以处理请求
        if (water < capacity) {
            water++;
            return true;
        }
        //桶已满，拒绝处理请求
        return false;
    }
}

public class TokenBucketLimiter implements Limiter {
    /**
     * 令牌桶的容量
     */
    private final int capacity;
    /**
     * 令牌产生速率
     */
    private final double rate;
    /**
     * 当前令牌数量
     */
    private double tokens;
    /**
     * 上一次令牌发放的时间戳
     */
    private long timestamp;

    public TokenBucketLimiter(int capacity, double rate) {
        this.capacity = capacity;
        this.rate = rate;
        // 初始化时，令牌桶满
        this.tokens = capacity;
        this.timestamp = System.currentTimeMillis();
    }


    @Override
    public boolean allow() {
        return tryAcquire(1);
    }

    /**
     * 尝试获取指定数量的令牌
     *
     * @param count 要获取的令牌数量
     * @return 是否获取成功
     */
    public synchronized boolean tryAcquire(int count) {
        // 先更新令牌数量
        refill();
        // 如果令牌数量足够
        if (tokens >= count) {
            // 则减去相应数量的令牌
            tokens -= count;
            // 返回获取成功
            return true;
        } else {
            // 否则返回获取失败
            return false;
        }
    }

    /**
     * 更新令牌桶中的令牌数量
     */
    private void refill() {
        long now = System.currentTimeMillis();
        // 计算时间间隔，单位为秒
        double elapsedTime = (now - timestamp) / 1000.0;
        // 计算新增的令牌数量
        double newTokens = elapsedTime * rate;
        // 更新令牌桶中的令牌数量
        tokens = Math.min(tokens + newTokens, capacity);
        // 更新时间戳
        timestamp = now;
    }
}

public class SlidingWindowRateLimiter implements Limiter {

    /**
     * 窗口大小
     */
    private final Integer windowSize;
    /**
     * 窗口内最多允许的请求数量
     */
    private final Integer limit;
    /**
     * 窗口计数器
     */
    private final Integer[] counter;
    /**
     * 窗口当前的位置
     */
    private Integer index;
    /**
     * 窗口的起始时间
     */
    private Long startTime;

    public SlidingWindowRateLimiter(Integer windowSize, Integer limit) {
        this.windowSize = windowSize;
        this.limit = limit;
        this.counter = new Integer[windowSize];
        this.index = 0;
        this.startTime = System.currentTimeMillis() / 1000;
    }

    /**
     * 尝试执行一个请求
     * @return 是否允许执行该请求
     */
    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis() / 1000;
        int offset = (int) (now - startTime) % windowSize;
        // 如果窗口已经滑动，则重置计数器
        if (offset != index) {
            counter[index] = 0;
            index = offset;
            startTime = now;
        }
        // 如果窗口内的请求数量超过了限制，则拒绝该请求
        if (counter[index] >= limit) {
            return false;
        }
        // 计数器加1，并允许执行该请求
        counter[index]++;
        return true;
    }
    
    @Override
    public boolean allow() {
        return tryAcquire();
    }
    
}