常见算法 | 艾AA

发布日期: 2023-03-20

更新日期: 2023-09-15

文章字数: 1.4k

阅读时长: 6 分

阅读次数:

数据库连接池

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.List;

public class ConnectionPool {
    private static final String URL = "jdbc:mysql://localhost:3306/mydatabase";
    private static final String USERNAME = "username";
    private static final String PASSWORD = "password";
    private static final int MAX_POOL_SIZE = 10;

    private List<Connection> connectionPool;

    public ConnectionPool() {
        initializeConnectionPool();
    }

    /**
     * 初始化连接池，创建初始数量的连接
     */
    private void initializeConnectionPool() {
        connectionPool = new ArrayList<>();

        try {
            for (int i = 0; i < MAX_POOL_SIZE; i++) {
                Connection connection = DriverManager.getConnection(URL, USERNAME, PASSWORD);
                connectionPool.add(connection);
            }
        } catch (SQLException e) {
            e.printStackTrace();
        }
    }

    /**
     * 从连接池中获取一个可用的连接
     *
     * @return 可用的连接
     */
    public synchronized Connection getConnection() throws SQLException {
        while (connectionPool.isEmpty()) {
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        Connection connection = connectionPool.remove(connectionPool.size() - 1);
        return connection;
    }

    /**
     * 将连接释放回连接池
     *
     * @param connection 要释放的连接
     */
    public synchronized void releaseConnection(Connection connection) {
        connectionPool.add(connection);
        notifyAll();
    }
}

LRU缓存

双向链表：按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
哈希表：即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在O(1) 的时间内完成 get 或者 put 操作。

对于 get 操作，首先判断 key 是否存在：

如果 key 不存在，则返回 −1-1−1；
如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。

对于 put 操作，首先判断 key 是否存在：

如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

public class LRUCache {  
    private Map<Integer,DLinkedNode> cache = new HashMap<>();  
    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;  
        }  
        //移到头部  
        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);  
        }  
    }  
  
    //定义双向链表  
    class DLinkedNode{  
        int key;  
        int value;  
        DLinkedNode prev;  
        DLinkedNode next;  
        public DLinkedNode(){}  
        public DLinkedNode(int key,int value){  
            this.key = key;  
            this.value = value;  
        }  
    }  
  
    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;  
    }  
  
}

使用内置数据结构LinkedHashMap

class LRUCache2 extends LinkedHashMap<Integer, Integer> {  
    private int capacity;  
  
    public LRUCache2(int capacity) {  
        //容量，负载因子，是否顺序访问（默认false插序访问）  
        super(capacity, 0.75F, true);  
        this.capacity = capacity;  
    }  
  
    public int get(int key) {  
        return super.getOrDefault(key, -1);  
    }  
  
    public void put(int key, int value) {  
        super.put(key, value);  
    }  
  
    @Override  
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {  
        return size() > capacity;  
    }  
}

单例模式

单例模式是一种创建型设计模式，它确保一个类只有一个实例，并提供了一个全局访问点来访问该实例。

懒汉式，线程不安全

用private声明了构造方法，这样做其他类就不能直接通过new实例化了

public class Singleton {  
    private static Singleton instance;  
    private Singleton (){}  
  
    public static Singleton getInstance() {  
        if (instance == null) {  
            instance = new Singleton();  
        }  
        return instance;  
    }  
}

懒汉式，线程安全

synchronized修饰get()方法

public class Singleton {  
    private static Singleton instance;  
    private Singleton (){}  
    public static synchronized Singleton getInstance() {  
        if (instance == null) {  
            instance = new Singleton();  
        }  
        return instance;  
    }  
}

饿汉式

用private声明了构造方法，这样做其他类就不能直接通过new实例化了
（类加载时就初始化）这样就会浪费了内存空间。

public class Singleton {  
    private static Singleton instance = new Singleton();  
    private Singleton (){}  
    public static Singleton getInstance() {  
	    return instance;  
    }  
}

双重校验锁

public class Singleton {  
    private volatile static Singleton singleton;  
    private Singleton (){}  
    public static Singleton getSingleton() {  
	    if (singleton == null) {  
	        synchronized (Singleton.class) {  
	            if (singleton == null) {  
	                singleton = new Singleton();  
	            }  
	        }  
	    }  
	    return singleton;  
	}  
}

多线程交替输出ABC

import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 交替输出ABC字母
 */
public class AlternateABC {
    static volatile Integer count = 1;

    // volatile + synchronized
    public static void solution1(){
        new Thread(() -> {
            for (int i = 0; i < 10; ) {
                while (count % 3 != 1) {

                }
                synchronized (count) {
                    if (count % 3 == 1) {
                        System.out.print("A");
                        count++;
                        i++;
                    }
                }
            }
        }, "A").start();


        new Thread(()->{
            for (int i = 0; i < 10;) {
                while (count % 3 != 2){

                }
                synchronized (count){
                    if (count % 3 == 2){
                        System.out.print("B");
                        count++;
                        i++;
                    }
                }
            }
        },"B").start();

        new Thread(()->{
            for (int i = 0; i < 10;) {
                while (count % 3 != 0){

                }
                synchronized (count){
                    if (count % 3 == 0){
                        System.out.print("C");
                        count++;
                        i++;
                    }
                }
            }

        },"C").start();
    }
}

死锁

public class DeadLockDemo {
    private static Object resource1 = new Object();//资源 1
    private static Object resource2 = new Object();//资源 2

    public static void main(String[] args) {
        new Thread(() -> {
            synchronized (resource1) {
                System.out.println(Thread.currentThread() + "get resource1");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread() + "waiting get resource2");
                synchronized (resource2) {
                    System.out.println(Thread.currentThread() + "get resource2");
                }
            }
        }, "线程 1").start();

        new Thread(() -> {
            synchronized (resource2) {
                System.out.println(Thread.currentThread() + "get resource2");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread() + "waiting get resource1");
                synchronized (resource1) {
                    System.out.println(Thread.currentThread() + "get resource1");
                }
            }
        }, "线程 2").start();
    }
}

Aiaa

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Aiaa !

算法

Redis(补档)

2023-03-22 Aiaa

数据库 NoSQL redis

Kafka

2023-03-15 Aiaa

Kafka 消息队列