今天不聊技术，发两道题.为什么？年底了，做完可能有惊喜哦

import java.util.concurrent.atomic.AtomicReference;
/**
 * 题目1：令牌桶
 * 要求：初始化最大容量和每秒生成数量。
 * tryAcquire(int tokens) 支持并发，不使用额外线程维护。
 * 
 * 改进：使用 CAS (AtomicReference) 替代 synchronized，实现无锁高并发。
 */
public class TokenBucket {
    private final long maxCapacity;
    private final double ratePerMillisecond;

    // 使用 AtomicReference 原子更新状态，避免锁竞争
    private final AtomicReference<BucketState> state;
    // 内部不可变状态类
    private static class BucketState {
        final double currentTokens;
        final long lastRefillTimestamp;
        BucketState(double currentTokens, long lastRefillTimestamp) {
            this.currentTokens = currentTokens;
            this.lastRefillTimestamp = lastRefillTimestamp;
        }
    }
    /**
     * @param maxCapacity 最大容量
     * @param tokensPerSecond 每秒生成的令牌数量
     */
    public TokenBucket(long maxCapacity, long tokensPerSecond) {
        if (maxCapacity <= 0 || tokensPerSecond <= 0) {
            throw new IllegalArgumentException("Capacity and rate must be positive");
        }
        this.maxCapacity = maxCapacity;
        // 将每秒的速率转换为每毫秒的速率
        this.ratePerMillisecond = (double) tokensPerSecond / 1000.0;

        // 初始化状态
        this.state = new AtomicReference<>(new BucketState(maxCapacity, System.currentTimeMillis()));
    }
    /**
     * 尝试获取令牌 (CAS 无锁实现)
     * @param tokens 需要获取的令牌数
     * @return 是否获取成功
     */
    public boolean tryAcquire(int tokens) {
        if (tokens <= 0) {
            return false;
        }
        while (true) {
            BucketState currentState = state.get();
            long now = System.currentTimeMillis();

            // 计算重填后的令牌数
            double newTokens = currentState.currentTokens;
            if (now > currentState.lastRefillTimestamp) {
                long timeElapsed = now - currentState.lastRefillTimestamp;
                double tokensToAdd = timeElapsed * ratePerMillisecond;
                newTokens = Math.min(maxCapacity, newTokens + tokensToAdd);
            } else {
                // 如果时间倒流或极短时间内调用，时间戳保持不变
                now = currentState.lastRefillTimestamp;
            }
            // 检查令牌是否足够
            if (newTokens < tokens) {
                return false;
            }
            // 构造新状态：扣减令牌，更新时间戳
            BucketState newState = new BucketState(newTokens - tokens, now);
            // CAS 更新，如果成功则返回 true，失败则循环重试
            if (state.compareAndSet(currentState, newState)) {
                return true;
            }
        }
    }

}

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;
/**
 * 题目2：LRU缓存
 * 要求：支持并发，不能使用ConcurrentHashMap、LinkedHashmap。
 * 
 * 实现：HashMap + 双向链表 + 全局锁 (ReentrantLock)
 * 这种实现简单清晰，完全满足线程安全要求。
 */
public class LRUCache<K, V> {

    // 双向链表节点
    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;
        }
    }
    private final int capacity;
    private final Map<K, Node<K, V>> map;

    // 伪头节点和伪尾节点，简化链表操作
    private final Node<K, V> head;
    private final Node<K, V> tail;

    // 全局锁，保证线程安全
    private final ReentrantLock lock = new ReentrantLock();
    public LRUCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("Capacity must be positive");
        }
        this.capacity = capacity;
        this.map = new HashMap<>(capacity);

        // 初始化双向链表
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }
    /**
     * 获取值
     * 1. 加锁
     * 2. 从 Map 获取节点
     * 3. 如果存在，移动到链表头部（表示最近使用）
     * 4. 解锁
     */
    public V get(K key) {
        lock.lock();
        try {
            Node<K, V> node = map.get(key);
            if (node == null) {
                throw new RuntimeException("Key not found: " + key);
            }
            moveToHead(node);
            return node.value;
        } finally {
            lock.unlock();
        }
    }
    /**
     * 插入或更新
     * 1. 加锁
     * 2. 检查 Key 是否存在
     * 3. 存在 -> 更新值，移动到头部
     * 4. 不存在 -> 创建新节点，加入 Map 和链表头部
     * 5. 检查容量 -> 超过则移除尾部节点（最近最少使用）
     * 6. 解锁
     */
    public void put(K key, V value) {
        lock.lock();
        try {
            Node<K, V> node = map.get(key);

            if (node != null) {
                // 更新值并移动到头部
                node.value = value;
                moveToHead(node);
            } else {
                // 新增节点
                Node<K, V> newNode = new Node<>(key, value);
                map.put(key, newNode);
                addToHead(newNode);
                // 超过容量，移除最近最少使用（尾部的前一个）
                if (map.size() > capacity) {
                    removeLRU();
                }
            }
        } finally {
            lock.unlock();
        }
    }

    // --- 链表辅助方法 (必须在锁内调用) ---
    private void moveToHead(Node<K, V> node) {
        removeNode(node);
        addToHead(node);
    }
    // 插入到头节点之后
    private void addToHead(Node<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    // 从链表中移除节点
    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    // 移除最近最少使用的节点（Tail 的前一个）
    private void removeLRU() {
        Node<K, V> lruNode = tail.prev;
        if (lruNode != head) {
            removeNode(lruNode);
            map.remove(lruNode.key);
        }
    }

}