使用Redis位图实现12306分段购票

14101 理论 | 2023-3-24

很多编程语言都有位运算符，Java语言也不例外。在Java语言中，提供了7种位运算符，分别是按位与（&）、按位或（|）、按位异或（^）、取反(~)、左移(<<)、带符号右移(>>)和无符号右移(>>>)。

这些运算符当中，仅有~是单目运算符，其他运算符均为双目运算符。

在讲解这些运算符的使用之前，必须了解一个常识，那就是：位运算符是对long、int、short、byte和char这5种类型的数据进行运算的，我们不能对double、float和boolean进行位运算操作。

如果你要理解本文章的理论和逻辑，可以参考，有人写了我就不啰嗦了

全网首发：12306抢票算法大曝光？（十张图搞定）

https://segmentfault.com/a/1190000023534009 

如果你对Redis位图不理解，可以参考

使用Bitmaps位图实现Redis签到

https://www.javacui.com/DB/703.html 

其他知识内容可以参考

https://www.javacui.com/index.php?keyword=redis 

如果你已经了解运算符和Redis位图，那么按照上面文章说法，逻辑其实很简单，就是把所有座位初始化为位图，当你购买车站A到车站B的票时，把中间车站的位图进行计算，如果最终计算有票，则为有票。

当然这边只是在技术上对于这个逻辑进行了实现，12306实际的逻辑的话，大家都懂的，天花板。

相关逻辑的解释，都在注释里面了，直接运行一下即可理解，上代码：

package com.example.springboot;

import org.junit.jupiter.api.Test;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.data.redis.connection.BitFieldSubCommands;
import org.springframework.data.redis.core.RedisTemplate;

import java.util.ArrayList;
import java.util.List;

/**
 * 12306分段购票模拟
 */
@SpringBootTest
public class A12306 {
    @Autowired
    private RedisTemplate redisTemplate;
    private final static int cz = 5; // 几个站点
    private final static int zw = 5; // 几个坐位

    @Test
    public void test1() {
        init();

        // 购买 2 张 1-3的票，此时有票
        int from = 1, to = 3;
        for (int i = 0; i < 2; i++) {
            qp(from, to);
        }

        from = 2;
        to = 4;
        // 购买 2 张 2-4的票，此时有票
        for (int i = 0; i < 2; i++) {
            qp(from, to);
        }

        from = 1;
        to = 5;
        // 购买 2 张 1-5的票，此时有 1 张票
        for (int i = 0; i < 2; i++) {
            qp(from, to);
        }

        from = 1;
        to = 3;
        // 购买 1 张 1-3的票，此时 无票
        qp(from, to);
    }

    public void qp(int from, int to) {
        System.out.println("=========================== 购票开始 ===========================");
        // 这里是要购买的起始站到终点站中间所有站的坐位情况
        List<Long> czLong = new ArrayList<>();
        // 最后一站 不用取，因为最后一站下车，下车就可以继续从这站开始买
        for (int i = from; i < to; i++) {
            // 这里取的时候要多取一个，因为 0 位是默认的 1
            List<Long> list1 = redisTemplate.opsForValue().bitField(i + "",
                    BitFieldSubCommands.create().get(BitFieldSubCommands.BitFieldType.unsigned(zw + 1)).valueAt(0));
            long temp = list1.get(0);
            System.out.println("车站 " + i + " 购票前 坐位情况 " + Long.toBinaryString(temp));
            czLong.add(temp);
        }
        long v = 0;
        for (Long l : czLong) {
            // 两个都为 0 时，才为 0
            v = v | l;
        }
        // 转为 2 进制 01 的字符串
        String b = Long.toBinaryString(v);
        System.out.println("最终计算 坐位情况 " + b);
        // 如果最终结算里面包含 0 ，说明有坐位，可以购买
        if (b.indexOf("0") > -1) {
            // 1 代表无票，把无票的去掉，长度就是总票量
            b = b.replace("1", "");
            System.out.print(from + " 到 " + to + " 有票 总票量 " + b.length());
            // 坐位，这里从右边开始取，否则无法进行下面的运算
            A:
            for (int i = zw; i > 0; i--) {
                // 按位操作向右位移1，再移动回来，再移回来时是用0补位，如果补位后相等说明这个位本来就是0
                if (v >> 1 << 1 == v) {
                    System.out.println(" 您的坐位编号：" + i);
                    for (int j = from; j < to; j++) {
                        // j 站点编号 i 坐位号 ，这里要把区间的车站都标为占用
                        redisTemplate.opsForValue().setBit(j + "", i, true);
                    }
                    break A;
                }
                // 是右移后赋值，意思是向右移动一位出去，此时变量v的值将发生变化
                v >>= 1;
            }
            // 打印购票后所有站坐位情况，最后一站不打印
            for (int i = 1; i < cz; i++) {
                // 这里取的时候要多取一个，因为 0 位是默认的 1
                List<Long> list1 = redisTemplate.opsForValue().bitField(  i + "",
                        BitFieldSubCommands.create().get(BitFieldSubCommands.BitFieldType.unsigned(zw + 1)).valueAt(0));
                long temp = list1.get(0);
                System.out.println("车站 " + i + " 购票后 坐位情况 " + Long.toBinaryString(temp));
            }
        } else {
            System.out.println(from + " 到 " + to + " 无票");
        }
        System.out.println("=========================== 购票结束 ===========================");
    }

    /**
     * 初始化站点和坐位
     */
    @Test
    public void init() {
        for (int z = 1; z <= cz; z++) {
            redisTemplate.delete(z + "");
        }
        for (int z = 1; z <= cz; z++) {
            // 这里把 0 位设置为 1，这样出来的数据就是 1000，方便查看
            redisTemplate.opsForValue().setBit(z + "", 0, true);
            for (int i = 1; i <= zw; i++) {
                redisTemplate.opsForValue().setBit(z + "", i, false);
            }
        }

        System.out.println("数据初始化完毕");
    }
}

运行以后打印结果如下：

数据初始化完毕
=========================== 购票开始 ===========================
车站 1 购票前 坐位情况 100000
车站 2 购票前 坐位情况 100000
最终计算 坐位情况 100000
1 到 3 有票 总票量 5 您的坐位编号：5
车站 1 购票后 坐位情况 100001
车站 2 购票后 坐位情况 100001
车站 3 购票后 坐位情况 100000
车站 4 购票后 坐位情况 100000
=========================== 购票结束 ===========================
=========================== 购票开始 ===========================
车站 1 购票前 坐位情况 100001
车站 2 购票前 坐位情况 100001
最终计算 坐位情况 100001
1 到 3 有票 总票量 4 您的坐位编号：4
车站 1 购票后 坐位情况 100011
车站 2 购票后 坐位情况 100011
车站 3 购票后 坐位情况 100000
车站 4 购票后 坐位情况 100000
=========================== 购票结束 ===========================
=========================== 购票开始 ===========================
车站 2 购票前 坐位情况 100011
车站 3 购票前 坐位情况 100000
最终计算 坐位情况 100011
2 到 4 有票 总票量 3 您的坐位编号：3
车站 1 购票后 坐位情况 100011
车站 2 购票后 坐位情况 100111
车站 3 购票后 坐位情况 100100
车站 4 购票后 坐位情况 100000
=========================== 购票结束 ===========================
=========================== 购票开始 ===========================
车站 2 购票前 坐位情况 100111
车站 3 购票前 坐位情况 100100
最终计算 坐位情况 100111
2 到 4 有票 总票量 2 您的坐位编号：2
车站 1 购票后 坐位情况 100011
车站 2 购票后 坐位情况 101111
车站 3 购票后 坐位情况 101100
车站 4 购票后 坐位情况 100000
=========================== 购票结束 ===========================
=========================== 购票开始 ===========================
车站 1 购票前 坐位情况 100011
车站 2 购票前 坐位情况 101111
车站 3 购票前 坐位情况 101100
车站 4 购票前 坐位情况 100000
最终计算 坐位情况 101111
1 到 5 有票 总票量 1 您的坐位编号：1
车站 1 购票后 坐位情况 110011
车站 2 购票后 坐位情况 111111
车站 3 购票后 坐位情况 111100
车站 4 购票后 坐位情况 110000
=========================== 购票结束 ===========================
=========================== 购票开始 ===========================
车站 1 购票前 坐位情况 110011
车站 2 购票前 坐位情况 111111
车站 3 购票前 坐位情况 111100
车站 4 购票前 坐位情况 110000
最终计算 坐位情况 111111
1 到 5 无票
=========================== 购票结束 ===========================
=========================== 购票开始 ===========================
车站 1 购票前 坐位情况 110011
车站 2 购票前 坐位情况 111111
最终计算 坐位情况 111111
1 到 3 无票
=========================== 购票结束 ===========================

可以看到，如果你买了中间的站点，那么再买起始站到终点站时，就不能买了。

推荐您阅读更多有关于“ 12306 redis Bitmaps 位图 分段购票 ”的文章

上一篇：spring-boot-starter-validation 下一篇：SQL/日志监控框架log4jdbc

猜你喜欢

• 3-24HTTP POST数据和数据接收
• 3-24常用SpringJPA主键生成策略，UUID和自增
• 3-24Apache Commons Jar包下载
• 3-24IIS服务器返回Bad Request (Invalid Hostname)解决办法
• 3-24SpringJPA 慎重 findAll() 切记分页

评论：