【总结】面试高频知识点相关的代码题
【持续更新中-面试高频知识点相关的代码题】
一、同步问题：
互斥与同步:
- 临界资源（临界区）：指一次只能允许一个进程使用的共享资源称为临界资源；
- 同步：指为完成某种任务而建立的两个和多个进程，这些进程在合作的过程中需要协调工作次序进行有序的访问而出现等待所产生的制约关系。
- 互斥：指两个或多个进程访问临界资源时只能一个进程访问，其他进程等待的一种相互制约的关系。
信号量与互斥量：
- 信号量：本身是一个计数器，使用P，V两个操作来实现计数的减与加，当计数不大于0时，则进程进入睡眠状态，它用于为多个进程提供共享数据对象的访问。
- 互斥量：如果信号量只存在两个状态，那就不需要计数了，可以简化为加锁与解锁两个功能，这就是互斥量。
1.生产者消费者问题
问题描述：一组生产者进程和一组消费者进程共享一块初始为空，大小确定的缓冲区，只有当缓冲区为满时，生产者进程才可以把信息放入缓冲区，否则就要等待；只有缓存区不为空时，消费者进程才能从中取出消息，否则就要等待。缓冲区一次只能一个进程访问（临界资源）。
问题分析：生产者与消费者进程对缓冲区的访问是互斥关系，而生产者与消费者本身又存在同步关系，即必须生成之后才能消费。因而对于缓冲区的访问设置一个互斥量，再设置两个信号量一个记录空闲缓冲区单元，一个记录满缓冲区单元来实现生产者与消费者的同步。
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
public class BolckingQueue {
//定义一个阻塞队列
static BlockingQueue queue = new ArrayBlockingQueue<>(10);
static AtomicInteger producerNumber = new AtomicInteger(0);
static AtomicInteger consumerNumber = new AtomicInteger(0);
//定义一个标志位
static boolean flag = true;
//生产者线程
static class Producer implements Runnable {
@Override
public void run() {
while (flag) {
try {
//生产消息
queue.put(new Object());
System.out.println(Thread.currentThread().getName() + "生产了第" + (producerNumber.incrementAndGet()) + "件商品");
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
//消费者线程
static class Consumer implements Runnable {
@Override
public void run() {
while (flag) {
try {
//消费者消费
queue.take();
TimeUnit.SECONDS.sleep(1);
System.out.println(Thread.currentThread().getName() + "消费了第" + (consumerNumber.incrementAndGet()) + "件商品");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
public static void main(String[] args) {
Thread producerThread = new Thread(new Producer(), "生存者线程");
Thread consumerThread = new Thread(new Consumer(), "消费者线程");
producerThread.start();
consumerThread.start();
//生产消费的行为只做5秒
try {
TimeUnit.SECONDS.sleep(5);
} catch (InterruptedException e) {
e.printStackTrace();
}
flag = false;
}
}
2.实现一个阻塞队列
public class MyBlockingQueueForLock<T> {
private Queue<T> queue=new LinkedList<>();
private final int MAX;
private ReentrantLock lock=new ReentrantLock();
private Condition producer=lock.newCondition();
private Condition consumer=lock.newCondition();
public MyBlockingQueueForLock(int limit){
this.MAX=limit;
}
public void put(T t) throws InterruptedException {
final ReentrantLock lock=this.lock;
lock.lockInterruptibly();
try {
while(queue.size()==MAX){
producer.await();//响应中断
}
queue.offer(t);
consumer.signalAll();
}finally {
lock.unlock();
}
}
public T get() throws InterruptedException {
final ReentrantLock lock=this.lock;
lock.lockInterruptibly();
T t;
try {
while (queue.size()==0){
consumer.await();//响应中断
}
t=queue.poll();
producer.signalAll();
}finally {
lock.unlock();
}
return t;
}
}
二、多线程打印问题：
常见多线程通信方式：
- Synchronized + wait() + notify()
- Lock + await() + signal()
- semaphore
- 基于semaphore的变体
1.Synchronized + wait() + notify()
await()与signal()方法有点类似wait(),notify()。不过await()与signal()是Condition工具类下的方法，Condition在内部维护了一个队列，简言之，
信号量提供操作计数的方式来同步控制线程
通过上述实现方法，我们可以得知，多线程间通信的思路是由符合条件的线程获取CPU资源并执行，若不符合条件的线程获取到的CPU信息，则进行阻塞。
wait()与notify()作为Object类中的方法，作用如下
- wait() 持有锁的线程，释放锁，一直阻塞，直到有别的线程调用notify()将其唤醒
- notify() 通知一个等待线程，唤醒任意一个wait线程
await()与signal()方法有点类似wait(),notify()。不过await()与signal()是Condition工具类下的方法，Condition在内部维护了一个队列，简言之，
- await() 将线程包装成节点并放入队列中，阻塞当前线程
- signal() 从同步队列中重新获取线程信息。
信号量提供操作计数的方式来同步控制线程
- acquire() 信号量减1，若信号量为0，则阻塞
- release() 信号量加1
通过上述实现方法，我们可以得知，多线程间通信的思路是由符合条件的线程获取CPU资源并执行，若不符合条件的线程获取到的CPU信息，则进行阻塞。
1.交替打印1-100
思路：进行进程间的通信，奇线程打印完阻塞自己，偶线程打印完唤醒被阻塞的线程，并将自己阻塞
public class print1to100 {
private static Object lock = new Object();
private static int i = 1;
public static void main(String[] args) {
Thread t1 = new Thread(() -> {
for (; i <= 100;) {
synchronized (lock) {
System.out.println(i ++ + "：我是偶数");
try {
lock.notify();
if (i <= 100) {
lock.wait();
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
});
Thread t2 = new Thread(() -> {
for (; i <= 100;) {
synchronized (lock) {
System.out.println(i ++ + "：我是奇数");
try {
if (i <= 100) {
lock.wait();
}
lock.notify();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
});
t2.start();
t1.start();
}
} public class print1to100 {
public synchronized void print(String str){
notify();
System.out.println(str);
try {
wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
//定义打印奇数的线程类
class A implements Runnable{
@Override
public void run() {
for(int i=1;i<100;i+=2){
print("A"+": "+i);
}
}
}
//定义打印偶数的线程类
class B implements Runnable{
@Override
public void run() {
for(int i=2;i<=100;i+=2){
print("B"+": "+i);
}
}
}
public static void main(String[] args) {
print1to100 p = new print1to100();
A a = p.new A();
B b = p.new B();
new Thread(a).start();
new Thread(b).start();
}
} 2.三个线程交替打印ABC
三个线程打印10遍ABC，形如ABCABCABCABC
方法1：Synchronized + wait() + notify()
- wait()与notify()作为Object类中的方法，作用如下
- wait() 持有锁的线程，释放锁，一直阻塞，直到有别的线程调用notify()将其唤醒
- notify() 通知一个等待线程，唤醒任意一个wait线程
public class printABC {
private static int count = 30;
static class ThreadA extends Thread {
Thread c;
public void setC(Thread c) {
this.c = c;
}
@Override
public void run() {
while (count-- > 0) {
synchronized (c) {
synchronized (this) {
System.out.print("A");
this.notify();
}
try {
c.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
static class ThreadB extends Thread {
Thread a;
public void setA(Thread a) {
this.a = a;
}
@Override
public void run() {
while (count-- > 0) {
synchronized (a) {
synchronized (this) {
System.out.print("B");
this.notify();
}
try {
a.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
static class ThreadC extends Thread {
Thread b;
public void setB(Thread b) {
this.b = b;
}
@Override
public void run() {
while (count-- > 0) {
synchronized (b) {
synchronized (this) {
System.out.print("C");
this.notify();
}
try {
b.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
public static void main(String[] args) throws InterruptedException {
ThreadA a = new ThreadA();
ThreadB b = new ThreadB();
ThreadC c = new ThreadC();
a.setC(c);
b.setA(a);
c.setB(b);
a.start();
Thread.sleep(100);
b.start();
Thread.sleep(100);
c.start();
}
} 3.交替打印字母abcd和数字1234
- 两个线程，打印结果为：a1b2c3d4
方法1：使用LockSupport类
LockSupport继承自Object类，类路径为：java.util.concurrent.locks.LockSupport。
作用：用来创建锁和其他同步类的基本线程阻塞原语。
LockSupport提供了park()和unpark()方法实现阻塞线程和解除线程阻塞。
import java.util.concurrent.locks.LockSupport;
public class print {
static Thread thread1 = null, thread2 = null;
public static void main(String[] args) {
char[] number = "abcd".toCharArray();
char[] alpha = "1234".toCharArray();
thread1 = new Thread(new Runnable() {
@Override
public void run() {
for(int i=0;i<2;i++){
for (char c : number) {
System.out.print(c);
LockSupport.unpark(thread2);
LockSupport.park();
}
}
}
});
thread2 = new Thread(() ->{
for (int i=0;i<2;i++){
for (char c : alpha) {
LockSupport.park();
System.out.print(c);
LockSupport.unpark(thread1);
}
}
});
thread1.start();
thread2.start();
}
} 方法2：使用synchronized同步锁
使用synchronized锁时需要用到Object类的wait() 和 notify() 方法，值得注意的是：
(1) wait() 和 notify() 方法都是Object类里面的，两者均需要在同步方法或同步代码块之中才能使用；
(2) wait() 和 notify() 方法的调用者，如果是同步代码块，则是synchronized锁定的对象来调用；如果是同步方法，则this来调用；
(3) 在同步环境中调用了wait()方法后，该线程释放锁，并等待在当前代码行处，直到其他线程调用了notify() 或 notifyAll() 方法，该线程才继续执行wait()方法的下一句代码。
public class print {
public static void main(String[] args) {
final Object lockObj = new Object();
Thread thread1 = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 1; i <= 4; i++) {
synchronized (lockObj) {
System.out.print(i);
lockObj.notify();
try {
lockObj.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
});
Thread thread2 = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 4; i++) {
char c = (char) ('a' + i);
synchronized (lockObj) {
System.out.print(c);
lockObj.notify();
try {
lockObj.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
synchronized (lockObj) {
lockObj.notify();
}
}
});
thread1.start();
thread2.start();
}
} Atomic是指一个操作是不可中断的。即使是在多个线程一起执行的时候，一个操作一旦开始，就不会被其他线程干扰。所以，Atomic原子类指的是具有原子/原子操作特征的类。而AtomicInteger则是操作int数据类型的原子类。AtomicInteger 类主要利用 CAS (compare and swap) + volatile 和 native 方法来保证原子操作，从而避免 synchronized 的高开销，执行效率大为提升。
import java.util.concurrent.atomic.AtomicInteger;
public class print {
static Thread thread1 = null, thread2 = null;
static AtomicInteger state= new AtomicInteger(0);
public static void main(String[] args) {
char[] number = "1234".toCharArray();
char[] alpha = "abcd".toCharArray();
thread1 = new Thread(new Runnable() {
@Override
public void run() {
for (char c : number) {
while (state.get() != 0) { // 用于阻塞线程thread1
}
System.out.print(c);
state.set(1);
}
}
});
thread2 = new Thread(){
public void run(){
for (char c : alpha) {
while (state.get() != 1) { // 用于阻塞线程thread2
}
System.out.print(c);
state.set(0);
}
}
};
thread1.start();
thread2.start();
}
}
4.三个窗口同时卖票
public class TicketDemo {
public static void main(String[] args) {
Ticket ticket = new Ticket();
SaleWindows windows1 = new SaleWindows("窗口1", ticket);
SaleWindows windows2 = new SaleWindows("窗口2", ticket);
SaleWindows windows3 = new SaleWindows("窗口3", ticket);
windows1.start();
windows2.start();
windows3.start();
}
}
/**
* 票
*/
class Ticket {
private int count = 1;
public void sale() {
while (true) {
synchronized (this) {
if (count > 200) {
System.out.println("票已经卖完啦");
break;
} else {
System.out.println(Thread.currentThread().getName() + "卖的第 " + count++ + " 张票");
}
try {
Thread.sleep(200);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
/**
* 售票窗口
*/
class SaleWindows extends Thread {
private Ticket ticket;
public SaleWindows(String name, Ticket ticket) {
super(name);
this.ticket = ticket;
}
@Override
public void run() {
super.run();
ticket.sale();
}
} 5.10个线程计算1~100的和
编写10个线程，第一个线程从1加到10，第二个线程从11加20…第十个线程从91加到100，最后再把10个线程结果相加。
public class TenThreadSum {
public static class SumThread extends Thread{
int forct = 0; int sum = 0;
SumThread(int forct){
this.forct = forct;
}
@Override
public void run() {
for(int i = 1; i <= 10; i++){
sum += i + forct * 10;
}
System.out.println(getName() + " " + sum);
}
}
public static void main(String[] args) {
int result = 0;
for(int i = 0; i < 10; i++){
SumThread sumThread = new SumThread(i);
sumThread.start();
try {
sumThread.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
result = result + sumThread.sum;
}
System.out.println("result " + result);
}
} 6.两个线程，一个线程打印1~52，另一个线程打印A~Z，打印顺序是12A34B…5152Z
public class TurnsPrint {
private boolean flag;
private int count;
public synchronized void printNum() {
for (int i = 0; i < 26; i++) {
while (flag) {
try {
wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
flag = !flag;
System.out.print(++count);
System.out.print(++count);
notify();
}
}
public synchronized void printLetter() {
for (int i = 0; i < 26; i++) {
while (!flag) {
try {
wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
flag = !flag;
System.out.print((char) (65 + i));
notify();
}
}
public static void main(String[] args) {
TurnsPrint turnsPrint = new TurnsPrint();
new Thread(new Runnable() {
@Override
public void run() {
turnsPrint.printNum();
}
}).start();
new Thread(new Runnable() {
@Override
public void run() {
turnsPrint.printLetter();
}
}).start();
}
} 三、锁
1.Java代码模拟死锁
死锁的概念：
- 在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲，就是两个或多个进程无限期的阻塞、相互等待的一种状态。
- 死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
死锁条件：
- 互斥使用：一个资源只能分配给一个线程
- 不可剥夺：资源只能由占有者释放，申请者不能强制剥夺
- 请求保持：线程申请资源时，保持对原有资源的占有
- 循环等待：存在一个进程等待队列：{P1 , P2 , … , Pn}, 其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路
死锁处理方法：
- 鸵鸟策略
- 死锁检测与死锁恢复
- 死锁预防
- 死锁避免
方法1：鸵鸟策略：
- 把头埋在沙子里，假装根本没发生问题。
- 因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。
- 当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。
- 大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。
方法2：死锁的检测和解除
在死锁产生前不采取任何措施，只检测当前系统有没有发生死锁，若有，则采取一些措施解除死锁。
死锁的检测：
根据死锁定理：S 为死锁的条件是当且仅当 S 状态的资源分配图是不可完全简化的，该条件称为死锁定理。
死锁的解除：
1、资源剥夺：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他死锁进程。（但应该防止被挂起的进程长时间得不到资源）；
2、撤销进程：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。（撤销的原则可以按进程优先级和撤销进程代价的高低进行）；
3、进程回退：让一个或多个进程回退到足以避免死锁的地步。【进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点】
- 利用抢占恢复
- 利用回滚恢复
- 通过杀死进程恢复
方法3：死锁预防
破坏四个必要条件之一
- 破坏互斥条件：改造独占性资源为虚拟资源，大部分资源已无法改造。即允许进程同时访问某些资源。但是，有的资源是不允许被同时访问的，像打印机等等。所以，这种办法并无实用价值。
- 破坏不可剥夺条件:当一进程占有一独占性资源后又申请一独占性资源而无法满足，则退出原占有的资源。当一个进程已占有了某些资源，它又申请新的资源，但不能立即被满足时，它必须释放所占有的全部资源，以后再重新申请。这就相当于该进程占有的资源被隐蔽地强占了。这种预防死锁的方法实现起来困难，会降低系统性能。
- 破坏请求与保持条件:采用资源预先分配策略，即进程运行前申请全部资源，满足则运行，不然就等待，这样就不会占有且申请。可以实行资源预先分配策略。即进程在运行前，一次性地向系统申请它所需要的全部资源。如果某个进程所需的全部资源得不到满足，则不分配任何资源，此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时，才一次性地将所申请的资源全部分配给该进程。由于运行的进程已占有了它所需的全部资源，所以不会发生占有资源又申请资源的现象，因此不会发生死锁。
- 破坏循环等待条件：实行顺序资源分配法；实现资源有序分配策略，对所有设备实现分类编号，所有进程只能采用按序号递增的形式申请资源。首先给系统中的资源编号，规定每个进程，必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中，只能申请编号大于Ri的资源。
方法4：避免死锁
银行家算法【在动态分配资源的过程中，银行家算法防止系统进入不安全状态，从而避免死锁】
- 银行家算法：当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源。若没超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若满足则按当前的申请量分配资源，否则也要推迟分配。
- 安全序列：是指系统能按某种进程推进顺序（P1, P2, P3, …, Pn），为每个进程 Pi 分配其所需要的资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺序地完成。这种推进顺序就叫安全序列【银行家算法的核心就是找到一个安全序列】。
- 系统安全状态 ：如果系统能找到一个安全序列，就称系统处于安全状态，否则，就称系统处于不安全状态
本题思路：
- 定义两个资源o1，o2
- 对象deadLock1占有资源o1，需要资源o2
- 对象deadLock2占有资源o2，需要资源o1
- 死锁产生
代码：
public class DeadLock implements Runnable {
// flag=1，占有对象o1，等待对象o2
// flag=0，占有对象o2，等待对象o1
public int flag = 1;
// 定义两个Object对象，模拟两个线程占有的资源
public static Object o1 = new Object();
public static Object o2 = new Object();
public static void main(String[] args) {
DeadLock deadLock1 = new DeadLock();
DeadLock deadLock2 = new DeadLock();
deadLock1.flag = 0;
deadLock2.flag = 1;
Thread thread1 = new Thread(deadLock1);
Thread thread2 = new Thread(deadLock2);
thread1.start();
thread2.start();
}
public void run() {
System.out.println("flag: " + flag);
// deadLock2占用资源o1，准备获取资源o2
if (flag == 1) {
synchronized (o1) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized (o2) {
System.out.println("1");
}
}
}
// deadLock1占用资源o2，准备获取资源o1
else if (flag == 0) {
synchronized (o2) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized (o1) {
System.out.println("0");
}
}
}
}
}
2.信号量实现读写锁
public class readWriteLock {
private volatile int readers = 0;
private volatile int writers = 0;
private volatile int writeRequests = 0;
public synchronized void lockRead() throws InterruptedException{
while(writers > 0 || writeRequests > 0){
this.wait();
}
++readers;
}
public synchronized void unlockRead(){
--readers;
this.notifyAll();
}
public synchronized void lockWrite() throws InterruptedException{
++writeRequests;
while(readers > 0 || writers > 0){
wait();
}
--writeRequests;
++writers;
}
public synchronized void unlockWrite(){
--writers;
notifyAll();
}
} 四、页面置换算法
- 最佳置换算法 OPT
- 先进先出置换算法
- 最近最久为使用置换算法 LRU
- 时钟置换算法 Clock
- 最少使用置换算法
- 新数据插入到链表头部；
- 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
- 当链表满的时候，将链表尾部的数据丢弃。
【命中率】：当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。
【复杂度】：实现简单。
【代价】：命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部；
像浏览器的缓存策略、memcached的缓存策略都是使用LRU这个算法，LRU算***将近期最不会访问的数据淘汰掉。LRU如此流行的原因是实现比较简单，而且对于实际问题也很实用，良好的运行时性能，命中率较高。
- 如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。
- 因此，当空间满时，最小频率访问的数据最先被淘汰。但是呢，有的数据的访问次数可能是相同的。怎么处理呢？如果访问次数相同，那么再考虑数据在缓存里面待的时间长短这个维度。
- 也就是说 LFU 算法，先看访问次数，如果次数一致，再看缓存时间。
一般会维护两个数据结构：
- 哈希：用来提供对外部的访问，查询效率更高；
- 双向链表或队列：维护了对元素访问次数的排序
缓存操作导致的链表变化：
- 添加新元素：新元素访问次数为1，放到队尾；
- 缓存淘汰：从队尾开始淘汰，因为队尾元素的访问次数最少；
- 访问缓存：访问缓存会增加元素的访问次数，所以元素在队列或双向链表中的位置会重新排序
缺点：
1. 最新加入的数据常常会被踢除，因为其起始方法次数少。
2. 如果频率时间度量是1小时，则平均一天每个小时内的访问频率1000的热点数据可能会被2个小时的一段时间内的访问频率是1001的数据剔除掉
区别：
LFU是基于访问频次的模式，而LRU是基于访问时间的模式。
优势：
在数据访问符合正态分布时，相比于LRU算法，LFU算法的缓存命中率会高一些。
劣势：
- LFU的复杂度要比LRU更高一些。
- 需要维护数据的访问频次，每次访问都需要更新。
- 早期的数据相比于后期的数据更容易被缓存下来，导致后期的数据很难被缓存。
- 新加入缓存的数据很容易被剔除，像是缓存的末端发生“抖动”。
1.LRU缓存
LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
- 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
- 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args){
LRUCache lru = new LRUCache(3);
lru.put(1,1);
System.out.println(lru.get(1));
lru.put(2,2);
lru.put(3,3);
lru.put(4,4);
System.out.println(lru.get(1));
System.out.println(lru.get(2));
System.out.println(lru.get(3));
System.out.println(lru.get(4));
}
}
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;
}
} 复杂度分析
- 时间复杂度：对于 put 和 get 都是 O(1)。
- 空间复杂度：O(capacity)，因为哈希表和双向链表最多存储capacity + 1个元素。
改成线程安全：
public static synchronized get(int key) public static synchronized put(int key，int val)
2.LFU缓存
import java.util.Map;
import java.util.HashMap;
import java.util.TreeSet;
public class lfu {
public static void main(String[] args){
LFUCache lru = new LFUCache(3);
lru.put(1,1);
System.out.println(lru.get(1));
lru.put(2,2);
lru.put(3,3);
lru.put(4,4);
System.out.println(lru.get(1));
System.out.println(lru.get(2));
System.out.println(lru.get(3));
System.out.println(lru.get(4));
}
}
class LFUCache {
// 缓存容量，时间戳
int capacity, time;
Map<Integer, Node> key_table;
TreeSet<Node> S;
public LFUCache(int capacity) {
this.capacity = capacity;
this.time = 0;
key_table = new HashMap<Integer, Node>();
S = new TreeSet<Node>();
}
public int get(int key) {
if (capacity == 0) {
return -1;
}
// 如果哈希表中没有键 key，返回 -1
if (!key_table.containsKey(key)) {
return -1;
}
// 从哈希表中得到旧的缓存
Node cache = key_table.get(key);
// 从平衡二叉树中删除旧的缓存
S.remove(cache);
// 将旧缓存更新
cache.cnt += 1;
cache.time = ++time;
// 将新缓存重新放入哈希表和平衡二叉树中
S.add(cache);
key_table.put(key, cache);
return cache.value;
}
public void put(int key, int value) {
if (capacity == 0) {
return;
}
if (!key_table.containsKey(key)) {
// 如果到达缓存容量上限
if (key_table.size() == capacity) {
// 从哈希表和平衡二叉树中删除最近最少使用的缓存
key_table.remove(S.first().key);
S.remove(S.first());
}
// 创建新的缓存
Node cache = new Node(1, ++time, key, value);
// 将新缓存放入哈希表和平衡二叉树中
key_table.put(key, cache);
S.add(cache);
} else {
// 这里和 get() 函数类似
Node cache = key_table.get(key);
S.remove(cache);
cache.cnt += 1;
cache.time = ++time;
cache.value = value;
S.add(cache);
key_table.put(key, cache);
}
}
}
class Node implements Comparable<Node> {
int cnt, time, key, value;
Node(int cnt, int time, int key, int value) {
this.cnt = cnt;
this.time = time;
this.key = key;
this.value = value;
}
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof Node) {
Node rhs = (Node) anObject;
return this.cnt == rhs.cnt && this.time == rhs.time;
}
return false;
}
public int compareTo(Node rhs) {
return cnt == rhs.cnt ? time - rhs.time : cnt - rhs.cnt;
}
public int hashCode() {
return cnt * 10***07 + time;
}
} 五、库函数
1.实现split()方法
Java自己实现split()方法---按照给定的目标字符串分割原始字符串
方法一：
先利用字符串的contains()方法判断原始字符串是否包含目标字符串，然后根据下标分割，将前面一段字符串加入list列表，然后删除给定目标字符串，继续while循环；最后再将剩余的最后一段字符串加入列表。
public static String[] split(String array, String target) {
List<String> list = new ArrayList<>();
while (array.contains(target)) {
int index = array.indexOf(target);
String temp = array.substring(0, index);
list.add(temp);
array = array.substring(index + target.length()); //substring(endIndex)删除endIndex之前的字符串
}
list.add(array);
String[] arr = new String[list.size()];
for (int i = 0; i < list.size(); i++) {
arr[i] = list.get(i);
}
return arr;
} 方法二：
将两个字符串转化为字符数组，利用StringBuffer或者StringBuilder类，对原始字符串字符数组遍历，每遍历一次就判断一下是否与目标字符串字符数组的每一位相等，若不相等，将遍历到的字符append到buffer中，若每一位都相等，则将buffer中的数据存入list，再将buffer清空，最后跳过目标字符串字符数组的相应字符，继续对原始数组循环操作。
public static List<String> split1(String array, String target){
List<String> result = new ArrayList<>();
char[] arrayChar = array.toCharArray();
char[] targetChar = target.toCharArray();
StringBuffer sb = new StringBuffer();
for(int i = 0; i < arrayChar.length;){
if(!isContains(arrayChar,targetChar,i)){
sb.append(arrayChar[i]);
i++;
}else {
result.add(sb.toString());
sb = new StringBuffer();
i += targetChar.length;
}
}
if(sb.length() != 0){
result.add(sb.toString());
}
return result;
}
public static boolean isContains(char[] srcArray, char[] targetArray, int tmp){
for(int i = 0; i<targetArray.length; i++){
if(tmp + i >= srcArray.length)
return false;
if(srcArray[i + tmp] != targetArray[i])
return false;
}
return true;
} 完整代码：
import java.util.ArrayList;
import java.util.List;
public class SplitString {
public static String[] split1(String array, String target) {
List<String> list = new ArrayList<>();
while (array.contains(target)) {
int index = array.indexOf(target);
String temp = array.substring(0, index);
list.add(temp);
array = array.substring(index + target.length()); //substring(endIndex)删除endIndex之前的字符串
}
list.add(array);
String[] arr = new String[list.size()];
for (int i = 0; i < list.size(); i++) {
arr[i] = list.get(i);
}
return arr;
}
public static List<String> split2(String array, String target){
List<String> result = new ArrayList<>();
char[] arrayChar = array.toCharArray();
char[] targetChar = target.toCharArray();
StringBuffer sb = new StringBuffer();
for(int i = 0; i < arrayChar.length;){
if(!isContains(arrayChar,targetChar,i)){
sb.append(arrayChar[i]);
i++;
}else {
result.add(sb.toString());
sb = new StringBuffer();
i += targetChar.length;
}
}
if(sb.length() != 0){
result.add(sb.toString());
}
return result;
}
public static boolean isContains(char[] srcArray, char[] targetArray, int tmp){
for(int i = 0; i<targetArray.length; i++){
if(tmp + i >= srcArray.length)
return false;
if(srcArray[i + tmp] != targetArray[i])
return false;
}
return true;
}
public static void main(String[] args) {
String array = "31***89";
String target = "12";
//String[] resList = split1(array, target);
List<String> resList = split2(array, target);
for (String s : resList) {
System.out.print(s + " ");
}
}
} 
