Java非算法手撕实现
还没写完，慢慢更
1.多线程交替打印：打印内容为ABC循环或者交替打印一段话
import java.util.concurrent.Semaphore;
public class ThreadExample {
public static Semaphore semaphore1 = new Semaphore(1);
public static Semaphore semaphore2 = new Semaphore(0);
public static Semaphore semaphore3 = new Semaphore(0);
public static void main(String[] args) {
Thread threadA = new Thread(new Runnable() {
@Override
public void run() {
while (true) {
try {
semaphore1.acquire();
System.out.println("A");
semaphore2.release();
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
});
Thread threadB = new Thread(new Runnable() {
@Override
public void run() {
while (true) {
try {
semaphore2.acquire();
System.out.println("B");
semaphore3.release();
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
});
Thread threadC = new Thread(new Runnable() {
@Override
public void run() {
while (true) {
try {
semaphore3.acquire();
System.out.println("C");
semaphore1.release();
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
});
threadA.start();
threadB.start();
threadC.start();
}
}
2. 多线程场景题：有5个人，在那赛跑，请你设计一个多线程的裁判程序给出他们赛跑的结果顺序，5个人的速度随机处理
package org.example.countdownlatch;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.CyclicBarrier;
/**
* 5个线程模拟赛马，所有马就绪后才能开跑，所有马到达终点后裁判宣布赛马成绩
* CountDownLatch和CyclicBarrier
*/
public class HorseRace {
// 用于存储赛马成绩
private static List<String> results = Collections.synchronizedList(new ArrayList<>());
// 用于控制所有马同时开跑
private static CountDownLatch startLatch = new CountDownLatch(1);
// 用于确保所有马到达终点后再宣布成绩
private static CyclicBarrier finishBarrier = new CyclicBarrier(5, new Runnable() {
@Override
public void run() {
// 裁判宣布成绩
System.out.println("Race finished! Announcing results:");
for (String result : results) {
System.out.println(result);
}
}
});
public static void main(String[] args) {
for (int i = 1; i <= 5; i++) {
new Thread(new Horse("Horse " + i)).start();
}
// 所有马就绪后开跑
try {
System.out.println("All horses ready. Race starts now!");
startLatch.countDown(); // 马开跑
} catch (Exception e) {
e.printStackTrace();
}
}
static class Horse implements Runnable {
private String name;
public Horse(String name) {
this.name = name;
}
@Override
public void run() {
try {
// 马就绪，等待开跑信号
startLatch.await();
// 马开始跑
long raceTime = (long) (Math.random() * 10000); // 模拟跑的时间
Thread.sleep(raceTime);
// 马到达终点
results.add(name + " finished in " + raceTime + " ms");
// 等待其他马到达终点
finishBarrier.await();
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
3. 手写线程池（实现一个简易线程池）
实现简易线程池，首先定义接口，主要包括，线程池基本功能，拒绝策略，线程池工厂，等待的任务队列。以及自定义异常，然后实现线程池的基本功能。
线程池基本功能接口
public interface ThreadPool {
//提交任务到线程池
void execute(Runnable runnable);
//关闭
void shutdown();
//获取线程池初始化时的线程大小
int getInitSize();
//获取线程池最大线程数
int getMaxSize();
//获取线程池核心线程数量
int getCoreSize();
//获取活跃线程数量
int getActiveCount();
//获取线程池缓存队列大小
int getQueueSize();
//查看线程是否被销毁
boolean isShutdown();
}
拒绝策略接口
@FunctionalInterface
//这个类定义了当缓存队列达到上限的时候，将通过什么方式来通知提交者，实现了默认的三种方法
public interface DenyPolicy {
void reject(Runnable runnable, ThreadPool threadPool);
}
线程池工厂接口
@FunctionalInterface
//创建线程的工厂
public interface ThreadFactory {
Thread creatThread(Runnable runnable);
}
任务队列接口
//缓存提交到线程池的队列任务
public interface RunnableQueue {
//新线程进来时,提交任务到缓存队列
void offer(Runnable runnable);
//取出线程
Runnable take();
//获取队列中线程的数量
int size();
}
自定义异常
//自定义异常
public class RunnableDenyException extends RuntimeException {
public RunnableDenyException(String msg) {
super(msg);
}
}
拒绝策略实现。（三个拒绝策略）
//直接丢弃线程，什么都不做，不通知
class DiscardDenyPolicy implements DenyPolicy {
@Override
public void reject(Runnable runnable, ThreadPool threadPool) {
}
}
//抛出异常通知
class AbortDenyPolicy implements DenyPolicy {
@Override
public void reject(Runnable runnable, ThreadPool threadPool) {
throw new RunnableDenyException("这个线程:" + runnable + " 将会被丢弃");
}
}
//使线程在提交者所在的线程中运行
class RunnerDenyPolicy implements DenyPolicy {
@Override
public void reject(Runnable runnable, ThreadPool threadPool) {
if (!threadPool.isShutdown()) {
runnable.run();
}
}
}
任务队列实现
import java.util.LinkedList;
public class LinkedRunnableQueue implements RunnableQueue {
//任务队列的最大容量
private final int limit;
//容量最大时，需要使用的拒绝策略
private final DenyPolicy denyPolicy;
//存放任务的队列
private final LinkedList<Runnable> runnableLinkedList;
private final ThreadPool threadPool;
public LinkedRunnableQueue(int limit, DenyPolicy denyPolicy, ThreadPool threadPool) {
this.limit = limit;
this.denyPolicy = denyPolicy;
this.threadPool = threadPool;
runnableLinkedList = new LinkedList<>();
}
@Override
public void offer(Runnable runnable) {
synchronized (runnableLinkedList) {
//如果缓存数量超过最大值，则使用拒绝策略
if (runnableLinkedList.size() >= limit) {
denyPolicy.reject(runnable, threadPool);
} else {
//成功加入list的末尾，并唤醒阻塞中的线程
runnableLinkedList.addLast(runnable);
runnableLinkedList.notifyAll();
}
}
}
@Override
public Runnable take() {
synchronized (runnableLinkedList) {
//如果缓存队列为空，则挂起，等待新的任务进来唤醒
while (runnableLinkedList.isEmpty()) {
try {
runnableLinkedList.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
return runnableLinkedList.removeFirst();
}
@Override
public int size() {
synchronized (runnableLinkedList) {
//返回list中的个数
return runnableLinkedList.size();
}
}
}
线程工厂实现
import java.util.concurrent.atomic.AtomicInteger;
class DefaultThreadFactory implements ThreadFactory {
private static final AtomicInteger GROUP_COUNTER = new AtomicInteger(1);
private static final ThreadGroup group = new ThreadGroup("我的线程-" +
GROUP_COUNTER.getAndDecrement());
private static final AtomicInteger COUNTER = new AtomicInteger(0);
@Override
public Thread creatThread(Runnable runnable) {
return new Thread(group, runnable, "线程池-" + COUNTER.getAndDecrement());
}
}
线程池实现
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.concurrent.TimeUnit;
import java.util.stream.IntStream;
public class BasicThreadPool extends Thread implements ThreadPool {
//初始化线程池的数量
private final int initSize;
//线程池最大线程数
private final int maxSize;
//线程池核心线程数
private final int coreSize;
//当前活跃线程的数量
private int activeCount;
//创建线程的工厂
private final ThreadFactory threadFactory;
//任务队列
private final RunnableQueue runnableQueue;
//线程是否被摧毁
private volatile boolean isShutdown = false;
//工作队列
private final Queue<ThreadTask> internalTasks = new ArrayDeque<>();
//拒绝策略
private final static DenyPolicy DEFAULT_DENY_POLICY = new DiscardDenyPolicy();
//看下面，自定义线程工厂
private final static ThreadFactory DEFAULT_THREAD_FACTORY =
new DefaultThreadFactory();
private final long keepAliveTime;
private final TimeUnit timeUnit;
//构造默认线程池时需要传入的参数：初始线程池的数量，最大线程的数量，核心线程数量，任务队列的最大数
public BasicThreadPool(int initSize, int maxSize, int coreSize,
int queueSize) {
this(initSize, maxSize, coreSize, DEFAULT_THREAD_FACTORY,
queueSize, DEFAULT_DENY_POLICY, 2,
TimeUnit.SECONDS);
}
public BasicThreadPool(int initSize, int maxSize, int coreSize, ThreadFactory threadFactory, int queueSize,
DenyPolicy denyPolicy, long keepAliveTime, TimeUnit timeUnit) {
this.initSize = initSize;
this.maxSize = maxSize;
this.coreSize = coreSize;
this.threadFactory = threadFactory;
this.runnableQueue = new LinkedRunnableQueue(queueSize, denyPolicy, this);
this.keepAliveTime = keepAliveTime;
this.timeUnit = timeUnit;
this.init();
}
//初始化线程池并创建initSize个线程
private void init() {
//继承了Thread类，初始化时先启动自己
start();
IntStream.range(0, initSize).forEach(i -> newThread());
}
//创建新的任务线程并启动
private void newThread() {
InternalTask internalTask = new InternalTask(runnableQueue);
Thread thread = this.threadFactory.creatThread(internalTask);
ThreadTask threadTask = new ThreadTask(thread, internalTask);
internalTasks.offer(threadTask);
this.activeCount++;
thread.start();
}
private void removeThread() {
ThreadTask threadTask = internalTasks.remove();
threadTask.internalTask.stop();
this.activeCount--;
}
@Override
public void execute(Runnable runnable) {
if (this.isShutdown) {
throw new IllegalStateException("这个线程池已经被销毁了");
}
this.runnableQueue.offer(runnable);
}
@Override
public void run() {
//自动维护线程池
while (!isShutdown && !isInterrupted()) {
try {
timeUnit.sleep(keepAliveTime);
} catch (InterruptedException e) {
e.printStackTrace();
isShutdown = true;
break;
}
synchronized (this) {
if (isShutdown) {
break;
}
//当任务队列大于0，活跃线程小于核心线程的时候，扩容线程
if (runnableQueue.size() > 0 && activeCount < coreSize) {
IntStream.range(initSize, coreSize).forEach(i -> newThread());
continue;
}
if (runnableQueue.size() > 0 && activeCount < maxSize) {
IntStream.range(coreSize, maxSize).forEach(i -> newThread());
}
if (runnableQueue.size() == 0 && activeCount > coreSize) {
IntStream.range(coreSize, activeCount).forEach(i -> removeThread());
}
}
}
}
@Override
public void shutdown() {
}
//这一段方法不是特别重要，就有读者自己写
@Override
public int getInitSize() {
return 0;
}
@Override
public int getMaxSize() {
return 0;
}
@Override
public int getCoreSize() {
return 0;
}
@Override
public int getActiveCount() {
return 0;
}
@Override
public int getQueueSize() {
return 0;
}
@Override
public boolean isShutdown() {
return this.isShutdown;
}
//把线程和internalTask一个组合
private static class ThreadTask {
public ThreadTask(Thread thread, InternalTask internalTask) {
this.thread = thread;
this.internalTask = internalTask;
}
Thread thread;
InternalTask internalTask;
}
}
线程池内部使用
//实现Runnable,用于线程池内部，该类会用到RunnableQueue，会不断的从队列中拿出线程并运行
public class InternalTask implements Runnable {
private final RunnableQueue runnableQueue;
private volatile boolean running = true;
public InternalTask(RunnableQueue runnableQueue) {
this.runnableQueue = runnableQueue;
}
@Override
public void run() {
//如果当前线程在运行中切没有被中断，则不断从缓存队列中拿出线程运行
while (running && !Thread.currentThread().isInterrupted()) {
try {
Runnable task = runnableQueue.take();
task.run();
} catch (Exception e) {
running = false;
break;
}
}
}
//停止当前任务，会在shutdown中使用
public void stop() {
this.running = false;
}
}
测试类
import java.util.concurrent.TimeUnit;
public class Main {
public static void main(String[] args) {
final ThreadPool threadPool = new BasicThreadPool(2, 6, 4, 100);
for (int i = 0; i <= 20; i++) {
threadPool.execute(() -> {
try {
TimeUnit.SECONDS.sleep(1);
System.out.println(Thread.currentThread().getName() + "开始了");
} catch (InterruptedException e) {
e.printStackTrace();
}
});
}
}
}
4. 生产者-消费者模型：例如一个厨子4s生产一个，一个客人10s消费一个
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class NonBlockingProducerConsumer {
// 定义一个非阻塞队列作为共享缓冲区
private static final Queue<String> queue = new ConcurrentLinkedQueue<>();
private static final int MAX_CAPACITY = 5; // 队列的最大容量
// 定义锁和条件变量
private static final Lock lock = new ReentrantLock();
private static final Condition notFull = lock.newCondition(); // 队列未满
private static final Condition notEmpty = lock.newCondition(); // 队列非空
public static void main(String[] args) {
// 创建厨子线程（生产者）
Thread chefThread = new Thread(() -> {
try {
while (true) {
lock.lock(); // 获取锁
try {
// 如果队列已满，等待
while (queue.size() == MAX_CAPACITY) {
System.out.println("Queue is full, Chef is waiting...");
notFull.await();
}
// 生产菜品
String dish = "Dish-" + System.currentTimeMillis();
queue.add(dish);
System.out.println("Chef produced: " + dish);
// 唤醒消费者
notEmpty.signalAll();
} finally {
lock.unlock(); // 释放锁
}
// 模拟厨子生产时间
Thread.sleep(4000);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
});
// 创建客人线程（消费者）
Thread customerThread = new Thread(() -> {
try {
while (true) {
lock.lock(); // 获取锁
try {
// 如果队列为空，等待
while (queue.isEmpty()) {
System.out.println("Queue is empty, Customer is waiting...");
notEmpty.await();
}
// 消费菜品
String dish = queue.poll();
System.out.println("Customer consumed: " + dish);
// 唤醒生产者
notFull.signalAll();
} finally {
lock.unlock(); // 释放锁
}
// 模拟客人消费时间
Thread.sleep(10000);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
});
// 启动线程
chefThread.start();
customerThread.start();
}
}
5. 单例模式：懒汉，饿汉，双重校验锁
懒汉
public class Singleton {
//私有构造方法
private Singleton() {}
//在成员位置创建该类的对象
private static Singleton instance;
//对外提供静态方法获取该对象
public static Singleton getInstance() {
if(instance == null) {
instance = new Singleton();
}
return instance;
}
}
恶汉
public class Singleton {
//私有构造方法
private Singleton() {}
//在成员位置创建该类的对象
private static Singleton instance = new Singleton();
//对外提供静态方法获取该对象
public static Singleton getInstance() {
return instance;
}
}
双重校验锁
public class Singleton {
//私有构造方法
private Singleton() {}
private static volatile Singleton instance;
//对外提供静态方法获取该对象
public static Singleton getInstance() {
//第一次判断，如果instance不为null，不进入抢锁阶段，直接返回实际
if(instance == null) {
synchronized (Singleton.class) {
//抢到锁之后再次判断是否为空
if(instance == null) {
instance = new Singleton();
}
}
}
return instance;
}
}
6. 动态代理
jdk动态代理
//卖票接口
public interface SellTickets {
void sell();
}
//火车站 火车站具有卖票功能，所以需要实现SellTickets接口
public class TrainStation implements SellTickets {
public void sell() {
System.out.println("火车站卖票");
}
}
//代理工厂，用来创建代理对象
public class ProxyFactory {
private TrainStation station = new TrainStation();
public SellTickets getProxyObject() {
//使用Proxy获取代理对象
/*
newProxyInstance()方法参数说明：
ClassLoader loader ： 类加载器，用于加载代理类，使用真实对象的类加载器即可
Class<?>[] interfaces ： 真实对象所实现的接口，代理模式真实对象和代理对象实现相同的接口
InvocationHandler h ： 代理对象的调用处理程序
*/
SellTickets sellTickets = (SellTickets) Proxy.newProxyInstance(station.getClass().getClassLoader(),
station.getClass().getInterfaces(),
new InvocationHandler() {
/*
InvocationHandler中invoke方法参数说明：
proxy ： 代理对象
method ： 对应于在代理对象上调用的接口方法的 Method 实例
args ： 代理对象调用接口方法时传递的实际参数
*/
public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
System.out.println("代理点收取一些服务费用(JDK动态代理方式)");
//执行真实对象
Object result = method.invoke(station, args);
return result;
}
});
return sellTickets;
}
}
//测试类
public class Client {
public static void main(String[] args) {
//获取代理对象
ProxyFactory factory = new ProxyFactory();
SellTickets proxyObject = factory.getProxyObject();
proxyObject.sell();
}
}
7. 手写一个HashMap，HashSet
HashMap
import java.util.LinkedList;
public class MyHashMap<K, V> {
private static final int DEFAULT_CAPACITY = 16; // 默认容量
private static final double LOAD_FACTOR = 0.75; // 负载因子
private LinkedList<Node<K, V>>[] buckets;
private int size; // 当前元素数量
public MyHashMap() {
this(DEFAULT_CAPACITY);
}
@SuppressWarnings("unchecked")
public MyHashMap(int capacity) {
buckets = new LinkedList[capacity];
for (int i = 0; i < capacity; i++) {
buckets[i] = new LinkedList<>();
}
size = 0;
}
// 存储键值对
public void put(K key, V value) {
int index = getIndex(key); // 计算哈希值对应的桶索引
LinkedList<Node<K, V>> bucket = buckets[index];
// 检查是否已经存在该键
for (Node<K, V> node : bucket) {
if (node.key.equals(key)) {
node.value = value; // 更新值
return;
}
}
// 如果不存在该键，则新增节点
bucket.add(new Node<>(key, value));
size++;
// 检查是否需要扩容
if ((double) size / buckets.length > LOAD_FACTOR) {
resize();
}
}
// 获取值
public V get(K key) {
int index = getIndex(key);
LinkedList<Node<K, V>> bucket = buckets[index];
for (Node<K, V> node : bucket) {
if (node.key.equals(key)) {
return node.value;
}
}
return null; // 如果没有找到键，返回 null
}
// 删除键值对
public void remove(K key) {
int index = getIndex(key);
LinkedList<Node<K, V>> bucket = buckets[index];
for (Node<K, V> node : bucket) {
if (node.key.equals(key)) {
bucket.remove(node);
size--;
return;
}
}
}
// 获取当前元素数量
public int size() {
return size;
}
// 扩容方法
@SuppressWarnings("unchecked")
private void resize() {
LinkedList<Node<K, V>>[] oldBuckets = buckets;
buckets = new LinkedList[oldBuckets.length * 2];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new LinkedList<>();
}
size = 0;
// 将旧桶中的所有元素重新插入新桶
for (LinkedList<Node<K, V>> bucket : oldBuckets) {
for (Node<K, V> node : bucket) {
put(node.key, node.value);
}
}
}
// 计算桶索引
private int getIndex(K key) {
return Math.abs(key.hashCode()) % buckets.length;
}
// 内部类：存储键值对的节点
private static class Node<K, V> {
K key;
V value;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
}
HashSet（在HashMap基础上实现）
public class MyHashSet<E> {
private static final Object PRESENT = new Object(); // 占位对象
private final MyHashMap<E, Object> map;
public MyHashSet() {
map = new MyHashMap<>();
}
// 添加元素
public boolean add(E e) {
return map.put(e, PRESENT) == null; // 如果之前不存在该键，返回 true
}
// 删除元素
public boolean remove(E e) {
return map.get(e) != null && (map.remove(e) != null);
}
// 判断是否包含某个元素
public boolean contains(E e) {
return map.get(e) != null;
}
// 获取集合大小
public int size() {
return map.size();
}
// 清空集合
public void clear() {
map = new MyHashMap<>();
}
}
8. 有一个0-4的随机器rand4，如何实现0-6的随机器rand6，概率相同。拓展：rand X = func(rand Y)，实现func函数
rand4实现rand6
public class Rand6FromRand4 {
// 假设 rand4 是一个已有的函数，返回 [0, 4] 的随机数
public static int rand4() {
return (int) (Math.random() * 5); // 模拟 rand4
}
// 实现 rand6，返回 [0, 6] 的随机数
public static int rand6() {
while (true) {
// 调用两次 rand4，生成一个范围为 [0, 24] 的随机数
int num = rand4() * 5 + rand4(); // num ∈ [0, 24]
// 只使用前 21 个数（21 是 7 的倍数，可以均匀分配到 [0, 6]）
if (num < 21) {
return num % 7; // 将 [0, 20] 映射到 [0, 6]
}
// 如果 num ≥ 21，丢弃并重新生成
}
}
}
randx实现randy
public class RandXFromRandY {
// 假设 randY 是一个已有的函数，返回 [0, Y-1] 的随机数
public static int randY(int Y) {
return (int) (Math.random() * Y); // 模拟 randY
}
// 实现 randX，返回 [0, X-1] 的随机数
public static int randX(int X, int Y) {
int n = 1;
int range = Y;
// 找到最小的 n，使得 Y^n >= X
while (range < X) {
range *= Y;
n++;
}
while (true) {
// 调用 n 次 randY，生成一个范围为 [0, Y^n - 1] 的随机数
int num = 0;
int factor = 1;
for (int i = 0; i < n; i++) {
num += randY(Y) * factor;
factor *= Y;
}
// 只使用前 k 个数，k 是 X 的倍数
if (num < range / X * X) {
return num % X; // 将 [0, k-1] 映射到 [0, X-1]
}
// 如果超出范围，丢弃并重新生成
}
}
}
9. 及其逆天的一个阿里手撕，来自于@byebyeneu：写三个Spring接口，调用第一个接口的时候返回这个接口的累计调用次数，调用第二个接口的时候返回调用这个接口的累计p99，调用第三个接口的时候，如果这个接口这时的qps<10，返回success，如果这个接口这时qps>10，返回err
10.判断今天星期几
import java.time.LocalDate;
import java.time.DayOfWeek;
public class DayOfWeekExample {
public static void main(String[] args) {
// 获取当前日期
LocalDate today = LocalDate.now();
// 获取今天是星期几
DayOfWeek dayOfWeek = today.getDayOfWeek();
// 输出星期几（英文）
System.out.println("Today is: " + dayOfWeek);
// 如果需要输出中文的星期几
String[] chineseWeekdays = {"星期一", "星期二", "星期三", "星期四", "星期五", "星期六", "星期日"};
int dayValue = dayOfWeek.getValue(); // 1 表示星期一，7 表示星期日
System.out.println("今天是: " + chineseWeekdays[dayValue - 1]);
}
}
11.求YYYY-MM-DD的上一天
public static String getPreviousDay(String dateStr) throws Exception {
// 定义日期格式
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
// 将字符串解析为 Date 对象
Date date = sdf.parse(dateStr);
// 使用 Calendar 计算上一天
Calendar calendar = Calendar.getInstance();
calendar.setTime(date);
calendar.add(Calendar.DAY_OF_MONTH, -1);
// 将结果格式化为字符串并返回
return sdf.format(calendar.getTime());
}
查看10道真题和解析
美团一面2235人在聊