看到一个面试题目:
设计一个 Map, 主线程高速插入和删除, 另一个线程定时删除 5 秒内没删除的数据
如果自旋 Map, 效率太低
引入 ConcurrentHashMap 和一个 Queue, 自旋遍历 Queue, 从头部开始移除
不知是否有更好的方法
/*** 设计一个 Map, 主线程高速插入和删除, 另一个线程定时删除 5 秒内没删除的数据* 高速: 想到 ConcurrentHashMap* 定时删除: 按时间顺序排列 -> 需要一个队列, 自旋遍历获取 key, 然后从 map remove, * 直到队列里面值 插入时间 + 5秒 > 当前时间, 说明整个队列的值都还未过期*/
public class QueueMap<K> {private volatile static QueueMap queueMap;/*** 双重锁单例*/public static QueueMap instanceDouble() {if (queueMap == null) {synchronized (QueueMap.class) {if (queueMap == null) {queueMap = new QueueMap();}}}return queueMap;}/*** 静态内部类单例*/public static QueueMap staticInner() {return QueueMapHolder.INSTANCE;}public static class QueueMapHolder {private static final QueueMap INSTANCE = new QueueMap();}private QueueMap() {}public static class SomeValue {private String key;private long millTime;public SomeValue(String key, long millTime) {this.key = key;this.millTime = millTime;}public String getKey() {return key;}public void setKey(String key) {this.key = key;}public long getMillTime() {return millTime;}public void setMillTime(long millTime) {this.millTime = millTime;}}/*** 实际操作的 get put remove*/private Map<K, SomeValue> map = new ConcurrentHashMap<>();/*** 队列存数据, V 里面需要有时间戳信息*/private Queue<SomeValue> queue = new ConcurrentLinkedQueue<>();private static final int EXPIRE_MILL = 5000;public void init() {System.out.println("子线程外面");new Thread(() -> {while (true) {SomeValue head = queue.peek();// 头的没过期, 后面的更不会过期if (head == null || head.getMillTime() + EXPIRE_MILL > System.currentTimeMillis()) {continue;}map.remove(head.getKey());SomeValue poll = queue.poll();System.out.println("线程" + Thread.currentThread().getName() + "删除 key " + poll.getKey());}}).start();}public void put(K k, SomeValue someValue) {SomeValue oldValue = map.put(k, someValue);// 从队列里面移除旧的数据if (oldValue != null) {queue.remove(oldValue);}queue.add(someValue);}public SomeValue get(K k) {SomeValue someValue = map.get(k);// 判断是否过期if (someValue != null && someValue.getMillTime() + EXPIRE_MILL >= System.currentTimeMillis()) {return someValue;}return null;}public void remove(K k) {map.remove(k);}public static void main(String[] args) throws InterruptedException {QueueMap doubleInstance = QueueMap.instanceDouble();doubleInstance.init();TimeUnit.SECONDS.sleep(3);QueueMap staticInnerInstance = QueueMap.staticInner();for (int i = 0; i < 10; i++) {if (i % 5 == 0) {doubleInstance.remove("key" + (i - 1));}doubleInstance.put("key" + i, new QueueMap.SomeValue("key=" + i, System.currentTimeMillis()));}System.out.println(111);}
}