实现 LRU
public class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {
}
public DLinkedNode(int _key, int _value) {
key = _key;
value = _value;
}
}
private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 如果 key 存在，先通过哈希表定位，再移到头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// 如果 key 不存在，创建一个新的节点
DLinkedNode newNode = new DLinkedNode(key, value);
// 添加进哈希表
cache.put(key, newNode);
// 添加至双向链表的头部
addToHead(newNode);
++size;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部节点
DLinkedNode tail = removeTail();
// 删除哈希表中对应的项
cache.remove(tail.key);
--size;
}
} else {
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node.value = value;
moveToHead(node);
}
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
实现 单例
循环打印 AB
一些知识
- wait() 方法被调用后，线程不会自动苏醒，需要别的线程调用同一个对象上的 notify() 或者 notifyAll() 方法。sleep() 方法执行完成后，线程会自动苏醒。或者可以使用 wait(long timeout) 超时后线程会自动苏醒。
- wait() 方法会释放对应的锁
使用 wait && notify
package com.tattoo.code;
import java.util.concurrent.Callable;
import java.util.concurrent.FutureTask;
/**
* @Date: 2022-03-09 20:43
* @Author: liushengxi
* @Description: 使用对象自身的监视锁 实现
*/
public class PrintAAndB01 {
public static Boolean flag = true;
// 控制循环次数
public static int i = 0;
public static Object lock = new Object();
public static void main(String[] args) {
FutureTask<Object> futureTaskA = new FutureTask<>(new PrintA());
FutureTask<Object> futureTaskB = new FutureTask<>(new PrintB());
new Thread(futureTaskA, "线程A").start();
new Thread(futureTaskB, "线程B").start();
}
static class PrintA implements Callable {
@Override
public Object call() throws Exception {
while (i < 10) {
synchronized (lock) {
if (flag) {
// 调用 wait后 释放 lock 的对象监视器锁,然后阻塞等待被 notify 唤醒
lock.wait();
} else {
System.out.println(Thread.currentThread().getName() + "------ A");
flag = !flag;
i++;
// 当调用obj.notify/notifyAll后，调用线程依旧持有obj锁，
// 因此，thread1，thread2，thread3虽被唤醒，但是仍无法获得obj锁。
// 直到调用线程退出synchronized块，释放obj锁后，
// thread1，thread2，thread3中的一个才有机会获得锁继续执行。
lock.notify();
}
}
}
return null;
}
}
static class PrintB implements Callable {
@Override
public Object call() throws Exception {
while (i < 10) {
synchronized (lock) {
if (!flag) {
lock.wait();
} else {
flag = !flag;
System.out.println(Thread.currentThread().getName() + "------ B");
i++;
lock.notify();
}
}
}
return null;
}
}
}
使用 condition
package com.tattoo.code;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
/**
* @Date: 2022-03-09 20:43
* @Author: liushengxi
* @Description: 使用 lock+Condition 实现
*/
public class PrintAAndB03 {
private int num = 0;
private ReentrantLock lock = new ReentrantLock();
Condition conditionA = lock.newCondition();
Condition conditionB = lock.newCondition();
private void printABC(int aim, Condition curThread, Condition nextThread) {
for (int i = 0; i < 3; ) {
lock.lock();
try {
while (num % 2 != aim) {
//阻塞当前线程
curThread.await();
}
System.out.println(Thread.currentThread().getName());
num++;
i++;
//唤醒下一个线程，而不是唤醒所有线程
nextThread.signal();
} catch (Exception e) {
e.printStackTrace();
} finally {
lock.unlock();
}
}
}
public static void main(String[] args) {
PrintAAndB03 printABC_lock = new PrintAAndB03();
new Thread(() -> {
printABC_lock.printABC(0, printABC_lock.conditionA, printABC_lock.conditionB);
}, "A").start();
new Thread(() -> {
printABC_lock.printABC(1, printABC_lock.conditionB, printABC_lock.conditionA);
}, "B").start();
}
}