redis分布式锁

转x33g5p2x  于2021-11-21 转载在 Redis  
字(21.9k)|赞(0)|评价(0)|浏览(390)

1.0

redis配置类

package com.xrh.config;

import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.connection.lettuce.LettuceConnectionFactory;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.serializer.GenericJackson2JsonRedisSerializer;
import org.springframework.data.redis.serializer.StringRedisSerializer;

import java.io.Serializable;

@Configuration
public class RedisConfig {

    @Bean
    public RedisTemplate<String, Serializable> redisTemplate(LettuceConnectionFactory connectionFactory){
        RedisTemplate<String, Serializable>redisTemplate=new RedisTemplate<>();
        redisTemplate.setConnectionFactory(connectionFactory);

        //java写进去就是什么防止乱码
        redisTemplate.setKeySerializer(new StringRedisSerializer());
        redisTemplate.setValueSerializer(new GenericJackson2JsonRedisSerializer());

        return redisTemplate;
    }
}

controller层

package com.xrh.controller;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

@RestController
public class GoodController {
    @Autowired
    private StringRedisTemplate stringRedisTemplate;

    @Value("${server.port}")
    private String serverPort;

    @GetMapping("/buyGoods")
    public String buyGoods(){
        String result = stringRedisTemplate.opsForValue().get("goods:001");
        int goodNumber=result==null?0:Integer.parseInt(result);
        if (goodNumber>0){
            int realNumber=goodNumber-1;
            stringRedisTemplate.opsForValue().set("goods:001",String.valueOf(realNumber));
            System.out.println("成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort);

            return "成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort;
        }else {
            System.out.println("购买失败，服务端口为:"+serverPort);
            return "购买失败，服务端口为:"+serverPort;
        }
    }
}

2.0

1.0单机版下，在多线程的情况下，会出现问题，单机版加锁synchronized ，当然还有lock，具体用哪个看业务，lock可以设置时间，过了多久就不等了，synchronized就要一直等，容易造成线程挤压

controller层

package com.xrh.controller;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

@RestController
public class GoodController {
    @Autowired
    private StringRedisTemplate stringRedisTemplate;

    @Value("${server.port}")
    private String serverPort;

    @GetMapping("/buyGoods")
    public String buyGoods(){

        synchronized (this){
            String result = stringRedisTemplate.opsForValue().get("goods:001");
            int goodNumber=result==null?0:Integer.parseInt(result);
            if (goodNumber>0){
                int realNumber=goodNumber-1;
                stringRedisTemplate.opsForValue().set("goods:001",String.valueOf(realNumber));
                System.out.println("成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort);

                return "成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort;
            }else {
                System.out.println("购买失败，服务端口为:"+serverPort);
                return "购买失败，服务端口为:"+serverPort;
            }
        }
    }
}

3.0

当服务部署到分布式后，通过访问nginx来轮询访问两个微服务，用jmeter压力测试，会出现超卖现象，一件物品卖多次，所以加分布式锁。

1.可以用setnx

1.stringRedisTemplate.opsForValue().setIfAbsent这个方法就相当于setnx
2.所谓加锁就是新建一个常量作为key，set方法的value可以是个字符串加线程名
3.setIfAbsent这个方法返回的是布尔类型，如果set成功了，就说明之前没有，代表这侧加锁成功
4.有加锁就要有释放锁，在业务完成的时候删掉这个键值对
package com.xrh.controller;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.UUID;

@RestController
public class GoodController {
    @Autowired
    private StringRedisTemplate stringRedisTemplate;

    public static final String REDIS_lOCK="LOCK";

    @Value("${server.port}")
    private String serverPort;

    @GetMapping("/buyGoods")
    public String buyGoods(){

        String value= UUID.randomUUID().toString()+Thread.currentThread().getName();
        //相当于redis中的setnx,因为是set所以也是set k v，key就是指的这把锁，value指的就是谁占用了这把锁
        //返回值是布尔类型的
        Boolean flag = stringRedisTemplate.opsForValue().setIfAbsent(REDIS_lOCK, value);
        if (!flag){
            return "抢锁失败";
        }

        String result = stringRedisTemplate.opsForValue().get("goods:001");
        int goodNumber=result==null?0:Integer.parseInt(result);
        if (goodNumber>0){
            int realNumber=goodNumber-1;
            stringRedisTemplate.opsForValue().set("goods:001",String.valueOf(realNumber));
            System.out.println("成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort);
            stringRedisTemplate.delete(REDIS_lOCK);//解锁

            return "成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort;
        }else {
            System.out.println("购买失败，服务端口为:"+serverPort);
            return "购买失败，服务端口为:"+serverPort;
        }
    }
}

4.0

3.0上有加锁也要由解锁，但是如果加锁执行还没有到解锁那一行代码的时候，有异常，所以一定要确保删锁完成，加上finally代码块

package com.xrh.controller;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.UUID;

@RestController
public class GoodController {
    @Autowired
    private StringRedisTemplate stringRedisTemplate;

    public static final String REDIS_lOCK="LOCK";

    @Value("${server.port}")
    private String serverPort;

    @GetMapping("/buyGoods")
    public String buyGoods(){

        String value= UUID.randomUUID().toString()+Thread.currentThread().getName();
        try {
            //相当于redis中的setnx,因为是set所以也是set k v，key就是指的这把锁，value指的就是谁占用了这把锁
            //返回值是布尔类型的
            Boolean flag = stringRedisTemplate.opsForValue().setIfAbsent(REDIS_lOCK, value);
            if (!flag){
                return "抢锁失败";
            }

            String result = stringRedisTemplate.opsForValue().get("goods:001");
            int goodNumber=result==null?0:Integer.parseInt(result);
            if (goodNumber>0){
                int realNumber=goodNumber-1;
                stringRedisTemplate.opsForValue().set("goods:001",String.valueOf(realNumber));
                System.out.println("成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort);

                return "成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort;
            }else {
                System.out.println("购买失败，服务端口为:"+serverPort);
                return "购买失败，服务端口为:"+serverPort;
            }
        } finally {
            stringRedisTemplate.delete(REDIS_lOCK);//解锁
        }
    }
}

5.0

4.0正常异常情况都会释放锁，但是极端情况，还没走到finally，后台服务器宕机了。解决方法setnx的时候加个时间，限定key的有效时间

package com.xrh.controller;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.UUID;
import java.util.concurrent.TimeUnit;

@RestController
public class GoodController {
    @Autowired
    private StringRedisTemplate stringRedisTemplate;

    public static final String REDIS_lOCK="LOCK";

    @Value("${server.port}")
    private String serverPort;

    @GetMapping("/buyGoods")
    public String buyGoods(){

        String value= UUID.randomUUID().toString()+Thread.currentThread().getName();
        try {
            //相当于redis中的setnx,因为是set所以也是set k v，key就是指的这把锁，value指的就是谁占用了这把锁
            //返回值是布尔类型的
            Boolean flag = stringRedisTemplate.opsForValue().setIfAbsent(REDIS_lOCK, value);
            stringRedisTemplate.expire(REDIS_lOCK,10L, TimeUnit.SECONDS);//给key加个过期时间

            if (!flag){
                return "抢锁失败";
            }

            String result = stringRedisTemplate.opsForValue().get("goods:001");
            int goodNumber=result==null?0:Integer.parseInt(result);
            if (goodNumber>0){
                int realNumber=goodNumber-1;
                stringRedisTemplate.opsForValue().set("goods:001",String.valueOf(realNumber));
                System.out.println("成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort);

                return "成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort;
            }else {
                System.out.println("购买失败，服务端口为:"+serverPort);
                return "购买失败，服务端口为:"+serverPort;
            }
        } finally {
            stringRedisTemplate.delete(REDIS_lOCK);//解锁
        }
    }
}

6.0

5.0加锁也加时间了，但是没有原子性，这两行代码不在一行，有可能上面执行了，下面没执行，所以用另一个setnx重载方法

package com.xrh.controller;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.UUID;
import java.util.concurrent.TimeUnit;

@RestController
public class GoodController {
    @Autowired
    private StringRedisTemplate stringRedisTemplate;

    public static final String REDIS_lOCK="LOCK";

    @Value("${server.port}")
    private String serverPort;

    @GetMapping("/buyGoods")
    public String buyGoods(){

        String value= UUID.randomUUID().toString()+Thread.currentThread().getName();
        try {
            //相当于redis中的setnx,因为是set所以也是set k v，key就是指的这把锁，value指的就是谁占用了这把锁
            //返回值是布尔类型的
            Boolean flag = stringRedisTemplate.opsForValue().setIfAbsent(REDIS_lOCK, value,10L,TimeUnit.SECONDS);

            if (!flag){
                return "抢锁失败";
            }

            String result = stringRedisTemplate.opsForValue().get("goods:001");
            int goodNumber=result==null?0:Integer.parseInt(result);
            if (goodNumber>0){
                int realNumber=goodNumber-1;
                stringRedisTemplate.opsForValue().set("goods:001",String.valueOf(realNumber));
                System.out.println("成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort);

                return "成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort;
            }else {
                System.out.println("购买失败，服务端口为:"+serverPort);
                return "购买失败，服务端口为:"+serverPort;
            }
        } finally {
            stringRedisTemplate.delete(REDIS_lOCK);//解锁
        }
    }
}

7.0

6.0下顺利情况没问题，正常业务逻辑5s，有个10s保底。但是如果A线程中的业务突然需要等待，超过10s的保底了，但是redis10s过后就删掉这个锁了。B线程这时候过来了，没有锁，然后抢到了，开始业务。但A线程不卡了，执行下去，把不是自己的锁删了。（张冠李戴，删除了别人的锁）
解决方法，在finally中加层判断，就那个uuid

package com.xrh.controller;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.UUID;
import java.util.concurrent.TimeUnit;

@RestController
public class GoodController {
    @Autowired
    private StringRedisTemplate stringRedisTemplate;

    public static final String REDIS_lOCK="LOCK";

    @Value("${server.port}")
    private String serverPort;

    @GetMapping("/buyGoods")
    public String buyGoods(){

        String value= UUID.randomUUID().toString()+Thread.currentThread().getName();
        try {
            //相当于redis中的setnx,因为是set所以也是set k v，key就是指的这把锁，value指的就是谁占用了这把锁
            //返回值是布尔类型的
            Boolean flag = stringRedisTemplate.opsForValue().setIfAbsent(REDIS_lOCK, value,10L,TimeUnit.SECONDS);

            if (!flag){
                return "抢锁失败";
            }

            String result = stringRedisTemplate.opsForValue().get("goods:001");
            int goodNumber=result==null?0:Integer.parseInt(result);
            if (goodNumber>0){
                int realNumber=goodNumber-1;
                stringRedisTemplate.opsForValue().set("goods:001",String.valueOf(realNumber));
                System.out.println("成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort);

                return "成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort;
            }else {
                System.out.println("购买失败，服务端口为:"+serverPort);
                return "购买失败，服务端口为:"+serverPort;
            }
        } finally {
            if (stringRedisTemplate.opsForValue().get(REDIS_lOCK).equalsIgnoreCase(value)){
                stringRedisTemplate.delete(REDIS_lOCK);//解锁
            }
        }
    }
}

8.0

7.0下的最后finally的判断和解锁不是原子的，解决方法，官网上有个lua脚本粘贴到finally语块中
如果不用lua脚本的话，考虑redis事务

package com.xrh.controller;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.List;
import java.util.UUID;
import java.util.concurrent.TimeUnit;

@RestController
public class GoodController {
    @Autowired
    private StringRedisTemplate stringRedisTemplate;

    public static final String REDIS_lOCK="LOCK";

    @Value("${server.port}")
    private String serverPort;

    @GetMapping("/buyGoods")
    public String buyGoods(){

        String value= UUID.randomUUID().toString()+Thread.currentThread().getName();
        try {
            //相当于redis中的setnx,因为是set所以也是set k v，key就是指的这把锁，value指的就是谁占用了这把锁
            //返回值是布尔类型的
            Boolean flag = stringRedisTemplate.opsForValue().setIfAbsent(REDIS_lOCK, value,10L,TimeUnit.SECONDS);

            if (!flag){
                return "抢锁失败";
            }

            String result = stringRedisTemplate.opsForValue().get("goods:001");
            int goodNumber=result==null?0:Integer.parseInt(result);
            if (goodNumber>0){
                int realNumber=goodNumber-1;
                stringRedisTemplate.opsForValue().set("goods:001",String.valueOf(realNumber));
                System.out.println("成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort);

                return "成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort;
            }else {
                System.out.println("购买失败，服务端口为:"+serverPort);
                return "购买失败，服务端口为:"+serverPort;
            }
        } finally {
            while (true){
                stringRedisTemplate.watch(REDIS_lOCK);
                if (stringRedisTemplate.opsForValue().get(REDIS_lOCK).equalsIgnoreCase(value)){//乐观锁
                    stringRedisTemplate.setEnableTransactionSupport(true);//支持事务
                    stringRedisTemplate.multi();
                    stringRedisTemplate.delete(REDIS_lOCK);
                    List<Object> queued = stringRedisTemplate.exec();
                    if (queued==null){//说明在删之前改了
                        continue;
                    }
                }
                stringRedisTemplate.unwatch();
                break;
            }
        }
    }
}

用lua脚本

先写一个Jredis工具类,Jredis跟stringRedisTemplate都是java连接redis的

package com.xrh.utils;

import redis.clients.jedis.JedisPool;
import redis.clients.jedis.JedisPoolConfig;

public class RedisUtil {
    private  static JedisPool pool;

    //创建JedisPool对象
    public static JedisPool open(){
        if (pool==null){
            //创建JedisPool
            //创建JedisPoolConfig，给config设置连接池的参数，使用config创建JedisPool
            JedisPoolConfig config=new JedisPoolConfig();

            //给config设置连接池的参数
            config.setMaxTotal(20);//最大线程数
            config.setMaxIdle(2);//设置最大空闲数
            config.setTestOnBorrow(true);//表示从线程池中获取的对象一定是经过检查可用的，是已经获取的

            pool=new JedisPool(config,"192.168.72.129",6379,6000,"666");
        }
        return pool;
    }

    //关闭Pool对象
    public static void close(){
        if (pool!=null){
            pool.close();
        }
    }
}

然后

package com.xrh.controller;

import com.xrh.utils.RedisUtil;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;

import java.util.Collections;
import java.util.UUID;
import java.util.concurrent.TimeUnit;

@RestController
public class GoodController {
    @Autowired
    private StringRedisTemplate stringRedisTemplate;

    public static final String REDIS_lOCK="LOCK";

    @Value("${server.port}")
    private String serverPort;

    @GetMapping("/buyGoods")
    public String buyGoods(){

        String value= UUID.randomUUID().toString()+Thread.currentThread().getName();
        try {
            //相当于redis中的setnx,因为是set所以也是set k v，key就是指的这把锁，value指的就是谁占用了这把锁
            //返回值是布尔类型的
            Boolean flag = stringRedisTemplate.opsForValue().setIfAbsent(REDIS_lOCK, value,10L,TimeUnit.SECONDS);

            if (!flag){
                return "抢锁失败";
            }

            String result = stringRedisTemplate.opsForValue().get("goods:001");
            int goodNumber=result==null?0:Integer.parseInt(result);
            if (goodNumber>0){
                int realNumber=goodNumber-1;
                stringRedisTemplate.opsForValue().set("goods:001",String.valueOf(realNumber));
                System.out.println("成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort);

                return "成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort;
            }else {
                System.out.println("购买失败，服务端口为:"+serverPort);
                return "购买失败，服务端口为:"+serverPort;
            }
        } finally {
            JedisPool jedisPool = RedisUtil.open();
            Jedis jedis = jedisPool.getResource();

            //lua脚本
            String script="if redis.call(\"get\",KEYS[1]) == ARGV[1]\n" +
                    "then\n" +
                    " return redis.call(\"del\",KEYS[1])\n" +
                    "else\n" +
                    " return 0\n" +
                    "end";

            try {
                Object o = jedis.eval(script, Collections.singletonList(REDIS_lOCK), Collections.singletonList(value));//利用lua脚本判断俩值是否一样
                if ("1".equals(o.toString())){//代表相等
                    System.out.println("---del redis lock ok");
                }else {
                    System.out.println("---del redis lock error");
                }
            }finally {
                if (null!=jedis){
                    jedis.close();
                }
            }
        }
    }
}

9.0

如何确保redis缓存时间大于业务逻辑时间，就是redis分布锁续期。还有就是集群模式下，redis只保证cp（高可用），zookeeper保证ap（一致性），所以redis可能出现数据丢失什么的，这个时候就是Redisson出场的时候，Redlock（redis分布式锁），Redisson就是java写的

配置类加上

@Bean
    public Redisson redisson(){
        Config config=new Config();
        config.useSingleServer().setAddress("redis://192.168.72.129:6379").setDatabase(0);
        return (Redisson) Redisson.create(config);
    }

controller层

package com.xrh.controller;

import com.xrh.utils.RedisUtil;
import org.redisson.Redisson;
import org.redisson.api.RLock;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;

import java.util.Collections;
import java.util.UUID;
import java.util.concurrent.TimeUnit;

@RestController
public class GoodController {
    @Autowired
    private StringRedisTemplate stringRedisTemplate;

    public static final String REDIS_lOCK="LOCK";

    @Value("${server.port}")
    private String serverPort;
    
    @Autowired
    private Redisson redisson;

    @GetMapping("/buyGoods")
    public String buyGoods(){

        String value= UUID.randomUUID().toString()+Thread.currentThread().getName();

        RLock lock = redisson.getLock(REDIS_lOCK);//!!!!!!!!!跟juc中的lock一样，只不过变成分布式版本的
        lock.lock();
        
        try {
            //相当于redis中的setnx,因为是set所以也是set k v，key就是指的这把锁，value指的就是谁占用了这把锁
            //返回值是布尔类型的
            Boolean flag = stringRedisTemplate.opsForValue().setIfAbsent(REDIS_lOCK, value,10L,TimeUnit.SECONDS);

            if (!flag){
                return "抢锁失败";
            }

            String result = stringRedisTemplate.opsForValue().get("goods:001");
            int goodNumber=result==null?0:Integer.parseInt(result);
            if (goodNumber>0){
                int realNumber=goodNumber-1;
                stringRedisTemplate.opsForValue().set("goods:001",String.valueOf(realNumber));
                System.out.println("成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort);

                return "成功买到商品，库存还剩 "+realNumber+"件，服务端口为:"+serverPort;
            }else {
                System.out.println("购买失败，服务端口为:"+serverPort);
                return "购买失败，服务端口为:"+serverPort;
            }
        } finally {
            lock.unlock();
        }
    }
}

在超高并发下可能会报一个异常，就是当前线程不能解锁（当前的线程和解锁的线程不是同一个），在解锁的时候加两层判断

finally {
            if (lock.isLocked()){
                if (lock.isHeldByCurrentThread()){
                    lock.unlock();
                }
            }
        }

LRU

利用LinkedHashMap

package com.xrh;

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkHashMapLRUCache<k,v> extends LinkedHashMap<k,v>{

    private int capacity;//缓存坑位

    public LinkHashMapLRUCache(int capacity) {
        super(capacity, (float) 0.75,false);//第三个参数是访问顺序，true的话
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<k, v> eldest) {
        return super.size()>capacity;
    }

    public static void main(String[] args) {
        LinkHashMapLRUCache lruCache=new LinkHashMapLRUCache(3);

        lruCache.put(1,"a");
        lruCache.put(2,"b");
        lruCache.put(3,"c");
        System.out.println(lruCache.keySet());

        lruCache.put(4,"d");
        System.out.println(lruCache.keySet());

        lruCache.put(3,"c");
        System.out.println(lruCache.keySet());
        lruCache.put(3,"c");
        System.out.println(lruCache.keySet());
        lruCache.put(3,"c");
        System.out.println(lruCache.keySet());
        lruCache.put(5,"x");
        System.out.println(lruCache.keySet());

    }
}
//true
//[1, 2, 3]
//[2, 3, 4]
//[2, 4, 3]
//[2, 4, 3]
//[2, 4, 3]
//[4, 3, 5]

//false
//[1, 2, 3]
//[2, 3, 4]
//[2, 3, 4]
//[2, 3, 4]
//[2, 3, 4]
//[3, 4, 5]

纯手写

package com.xrh;

import java.util.HashMap;
import java.util.Map;

/** * map负责查找，里面封装node,类似AQS * 步骤： * 1.构造一个内部类Node * 2.构造一个双向队列里面装node，相当于AQS */
public class LRUCache {

    class Node<k,v>{
        k key;
        v value;
        Node<k,v> pre;
        Node<k,v> next;

        public Node() {
            this.pre=this.next=null;
        }

        public Node(k key, v value) {
            this.key = key;
            this.value = value;
            this.pre=this.next=null;
        }
    }

    //2.
    class DoubleLinkedList<k,v>{
        Node<k,v>head;
        Node<k,v>tail;

        //2.1构造方法
        public DoubleLinkedList() {
            this.head=new Node<>();
            this.tail=new Node<>();
            head.next=tail;
            tail.pre=head;
        }
        //2.2添加到头
        public void addHead(Node<k,v> node){
            node.next=head.next;
            node.pre=head;
            //下面不能用tail表示是因为两个的时候加可以但是多节点的时候就不是尾了，得用head.next.pre表示
            head.next.pre=node;
            head.next=node;
        }
        //2.3删除节点
        public void removeNode(Node<k,v> node){
            node.pre.next=node.next;
            node.next.pre=node.pre;
            node.next=null;
            node.pre=null;
        }
        //2.4获得最后一个节点
        public Node getLast(){
            return tail.pre;
        }
    }

    //上面两个内部类写完了
    //下面写LRUCache的属性，方法

    private int cacheSize;
    Map<Integer,Node<Integer,Integer>> map;
    DoubleLinkedList<Integer,Integer>doubleLinkedList;

    public LRUCache(int cacheSize) {
        this.cacheSize = cacheSize;
        map=new HashMap<>();
        doubleLinkedList=new DoubleLinkedList<>();
    }

    public int get(int key){
        if (!map.containsKey(key)){
            return -1;
        }
        Node<Integer,Integer>node=map.get(key);
        doubleLinkedList.removeNode(node);
        doubleLinkedList.addHead(node);  //妙啊，如果查这个key说明又用到了，删掉原来的，放在头上，表示常用的

        return node.value;
    }

    //更新或者新加
    public void put(int key,int value){
        if (map.containsKey(key)){
            Node<Integer,Integer>node=map.get(key);
            node.value=value;
            map.put(key,node);

            doubleLinkedList.removeNode(node);
            doubleLinkedList.addHead(node);
        }else {//如果这个map中没有这个值，有两种情况，如果坑位满了，就要删除最后一个，不满就加入
            if (map.size()==cacheSize){
                Node<Integer,Integer> lastNode=doubleLinkedList.getLast();
                map.remove(lastNode.key);//map也要删
                doubleLinkedList.removeNode(lastNode);
            }
            //才是新增
            Node<Integer,Integer>newNode=new Node<>(key,value);
            map.put(key,newNode);
            doubleLinkedList.addHead(newNode);
        }
    }

    public static void main(String[] args) {
        LRUCache lruCache=new LRUCache(3);

        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        System.out.println(lruCache.map.keySet());

        lruCache.put(4,4);
        System.out.println(lruCache.map.keySet());

        lruCache.put(3,3);
        System.out.println(lruCache.map.keySet());
        lruCache.put(3,3);
        System.out.println(lruCache.map.keySet());
        lruCache.put(3,3);
        System.out.println(lruCache.map.keySet());

        lruCache.put(5,5);
        System.out.println(lruCache.map.keySet());
    }
}

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/weixin_47160763/article/details/111885120

内容来源于网络，如有侵权，请联系作者删除！

java进阶

相关文章

    查看更多
    微信公众号

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com