基于数组实现的LRU缓存

package com.itstudy.linkedlist;

import java.util.HashMap;
import java.util.Map;
/**
 * Created by Xuzhu in 2018/12/7 2:00 PM.
 *
 * 基于数组实现的LRU缓存
 * 1. 空间复杂度为O(n)
 * 2. 时间复杂度为O(n)
 * 3. 不支持null的缓存
 */
public class LRUBasedArray<T> { private static final int DEFAULT_CAPACITY = (1 << 3); private int capacity; private int count; private T[] value; private Map<T, Integer> holder; public LRUBasedArray() { this(DEFAULT_CAPACITY); } public LRUBasedArray(int capacity) { this.capacity = capacity; value = (T[]) new Object[capacity]; count = 0; holder = new HashMap<T, Integer>(capacity); } /** * 模拟访问某个值 * @param object */ public void offer(T object) { if (object == null) { throw new IllegalArgumentException("该缓存容器不支持null!"); } Integer index = holder.get(object); if (index == null) { if (isFull()) { removeAndCache(object); } else { cache(object, count); } } else { update(index); } } /** * 若缓存中有指定的值，则更新位置 * @param end */ public void update(int end) { T target = value[end]; rightShift(end); value[0] = target; holder.put(target, 0); } /** * 缓存数据到头部，但要先右移 * @param object * @param end 数组右移的边界 */ public void cache(T object, int end) { rightShift(end); value[0] = object; holder.put(object, 0); count++; } /** * 缓存满的情况，踢出后，再缓存到数组头部 * @param object */ public void removeAndCache(T object) { T key = value[--count]; holder.remove(key); cache(object, count); } /** * end左边的数据统一右移一位 * @param end */ private void rightShift(int end) { for (int i = end - 1; i >= 0; i--) { value[i + 1] = value[i]; holder.put(value[i], i + 1); } } public boolean isContain(T object) { return holder.containsKey(object); } public boolean isEmpty() { return count == 0; } public boolean isFull() { return count == capacity; } @Override public String toString() { StringBuilder sb = new StringBuilder(); for (int i = 0; i < count; i++) { sb.append(value[i]); sb.append(" "); } return sb.toString(); } static class TestLRUBasedArray { public static void main(String[] args) { testDefaultConstructor(); testSpecifiedConstructor(4);
// testWithException(); } private static void testWithException() { LRUBasedArray<Integer> lru = new LRUBasedArray<Integer>(); lru.offer(null); } public static void testDefaultConstructor() { System.out.println("======无参测试========"); LRUBasedArray<Integer> lru = new LRUBasedArray<Integer>(); lru.offer(1); lru.offer(2); lru.offer(3); lru.offer(4); lru.offer(5); System.out.println(lru); lru.offer(6); lru.offer(7); lru.offer(8); lru.offer(9); System.out.println(lru); } public static void testSpecifiedConstructor(int capacity) { System.out.println("======有参测试========"); LRUBasedArray<Integer> lru = new LRUBasedArray<Integer>(capacity); lru.offer(1); System.out.println(lru); lru.offer(2); System.out.println(lru); lru.offer(3); System.out.println(lru); lru.offer(4); System.out.println(lru); lru.offer(2); System.out.println(lru); lru.offer(4); System.out.println(lru); lru.offer(7); System.out.println(lru); lru.offer(1); System.out.println(lru); lru.offer(2); System.out.println(lru); } }
}