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

客官°小女子只卖身不卖艺 2023-01-01 09:57 383阅读 0赞

![3dac5de8bc86acdcfc96807e820bb1e9.png][]

## 前言 ##

> 本文收录于专辑： http:// dwz.win/HjK ，点击解锁更多数据结构与算法的知识。

你好，我是彤哥，一个每天爬二十六层楼还不忘读源码的硬核男人。

相信大家都有过抢票、刷票的经验，每年年底，这都是一场盛宴。

然而，你有没有想过12306的抢票算法是怎么实现的呢？

没有吧，想过，还是没有头绪？

今天，我们就来曝光让人又爱又恨的12306是如何实现抢票的。

## 位运算回顾 ##

我们知道计算机只能识别0和1，要操作这些0和1，只能通过位运算来进行，那么，一共有几种位运算呢？

让我们来回顾一下：

运算

符号

举例

结果

与

1101 & 0110

0100

或

1101 & 0110

1111

异或

1101 ^ 0110

1011

取反

1101

0010

左移

1101 << 1

11010

带符号右移（高位补1）

1101 >> 1

1110

不带符号右移（高位补0）

>>>

1101 >>> 1

0110

> 以上位运算以Java为例，其他语言中可能没有 >>> 操作。

OK，位运算的简单回顾就到这里，还有不懂的同学可以自行百度一下。

## 位图 ##

虽然大部分语言都有提供位运算，但是，并没有提供一种类似于位数组的类型，要使用这些位运算，我们只能通过数字类型来实现，比如Java中的int/long等类型。

而这些数字类型的数组，我们一般可以称之为“位图”（BitMap）。

比如，我们需要使用128位的内存，可以申请包含两个long类型的数组`long[] bitmap = new long[2];`。

不过，位图有什么用呢？

有大用处哦，比如，我们要统计某个用户一年的活跃度，就可以使用位图来实现。

一年有365天，一个long类型可以表示64位，365/64=6，只需要6个long类型就可以记录一个用户一年的活跃情况，怎么记录呢？

很简单，初始时，位图中所有位都是0，当这个用户某天登录了，就在位图中找到这天，把其位变成1，一年下来，这张位图就记录了这个用户哪些天登录了，统计这个位图中1的数量，除以365，就得到了他的活跃度。

![a998e6913fd6dd770cd5d8708f433b2d.png][]

OK，这只是位图的一个很简单的用法，位图还有很多高级的用法，比如统计活跃用户数、限流、权限控制等，当然，还有我们今天要曝光的12306抢票算法。

## 12306抢票算法 ##

我们知道，一列火车，有很多个座位，可以到很多站，以北京到广州的一列火车G67为例：

![45080112ecce750c71c303cb5fdfb67c.png][]

G67次列车一共有18个站，有的人可能到武汉就下车了，有的人可能到长沙下车，还有的人可能从武汉上车从衡山西下车，甚至还有的人从北京一直坐到广州，我们假设这趟列车一共有200个座位。

那么，如何实现合理的抢票策略，才能保证这趟列车能够坐最多的人？（没有站票）

什么叫做“坐最多的人”呢？假设针对10号位置，一个人从北京到武汉，另一个人从武汉到长沙，再一个人从长沙到广州，那针对这个位置全程可以坐3个人；针对另一个位置，一个人从北京到广州，那这个位置全程只能坐一个人。简单点说，就是针对一个特定的位置，两个人之间不能有交集，比如一个人从北京到长沙，另一个人从武汉到广州，那这两个人不能安排到同一个位置上。

![674295c87b4729628522231f1610cbfa.png][]

OK，先给你一分钟时间思考一下，先别急着往下看哦。

--------------------

好了，一分钟时间已到，让我们继续。

首先，让我们回顾下G67这趟列车的信息：一共18个站，一共200个座位。

为了方便讲解和画图，我们假设它只有 北京、信阳、武汉、岳阳、长沙、广州 6个站，一共有8个座位。

针对这样的信息，我们可以这样来实现抢票策略：

1.  创建5个位图，每个位图的大小为8位，初始时，每个位的值都是0。  
    为什么是5个位图呢？因为到站就下车了，而广州站是终点站，到站全部人都得下车。比如，一个人从北京到武汉，他到武汉就下车了，所以，它不会占用武汉的位置。

![0adc03cc4e081504a38d1fa28a8ae41f.png][]

1.  把抢票逻辑放在单线程中来处理，单线程的好处是不用考虑并发问题，没有CPU上下文切换的问题等，而且整个操作都是CPU操作，速度很快，使用单线程效率更高。  
    当然，我们还有更好的选择——Redis，Redis本身就是单线程处理的，而且它天然支持BitMap，速度又快又好，有兴趣的同学可以了解一下Redis中的BitMap。

1.  假设第一个人的请求过来了，他要抢从北京到武汉的票，此时，我们只需要把北京和信阳两个位图做“或”运算，结果中，所有0的位置都表示可抢的位置，在这些位置中随机返回一个即可，并把此位置在北京和信阳这两个位图中标记为1，表示此位置在北京和信阳有人占用了。（武汉为什么不参与运算了，前面讲过了，这个人到武汉就下车了。）

![71bc13db968f5ab536f450dd0f86c592.png][]

假设，此人最后的座位是2号，那么运算之后，各位图的情况如下：

![9d9fd3af00299104ad9cca694cb38edd.png][]

1.  接着，第二个人的请求过来了，假设他要从信阳到长沙，此时，需要把信阳、武汉和岳阳三个位图做“或”运算：

![863c966ace644a291076a9c81d9dec16.png][]

假设，此人最后的座位是4号，那么，运算之后，各位图的情况如下：

![f428e4b8024ff0a0fccc145eab1b98ef.png][]

1.  然后，第三个人的请求来了，假设他要从北京到广州，此时，把所有5个位图做“或”运算：

![ef0e83e51e39551c0040c0e09494eabc.png][]

假设，此人最后的座位是1号位，那么，运算之后，各位图的情况如下：

![4f3890d5d67066e21f75ad978891afbc.png][]

1.  OK，经过了多个人的请求之后，假设位图的情况变成了下面这样：

![23bb1ba51c93f9fe8da0d70dc0fe2c49.png][]

请思考，此时，还能抢到从北京到广州的票吗？  
能？不能？回答能的同学，请从头再看一遍^^

好了，关于抢票算法我们就介绍到这里，你有没有Get到呢？或者你有没有更好的实现方法呢？

## 后记 ##

本节，我们一起重温了位运算的操作，并学习了如何使用位图实现12306的抢票算法，关于位图，其实还有很多用途，比如，各种统计、限流、权限控制等。

彤哥收到最新情报：所有的递归都可以改写成非递归，怎么实现呢？有没有什么套路呢？下一节，我们一起来聊下这个话题。

> 关注公号主“彤哥读源码”，解锁更多源码、基础、架构知识。

[3dac5de8bc86acdcfc96807e820bb1e9.png]: /images/20221120/e05ab0aa691442cbbcf01860341db3f0.png
[a998e6913fd6dd770cd5d8708f433b2d.png]: /images/20221120/a8b1194a34504edfab743d00658be45b.png
[45080112ecce750c71c303cb5fdfb67c.png]: /images/20221120/1411fcba207843c0b83d548f912116cf.png
[674295c87b4729628522231f1610cbfa.png]: /images/20221120/357cd389e5b64a108905c76762415c9a.png
[0adc03cc4e081504a38d1fa28a8ae41f.png]: /images/20221120/3e99695b76fc4a5e9347fe1a3e9ed982.png
[71bc13db968f5ab536f450dd0f86c592.png]: /images/20221120/f3e69cb2cc634ebab1a6caf08f19a0e2.png
[9d9fd3af00299104ad9cca694cb38edd.png]: /images/20221120/022f51afa3c943c88907642e8b658458.png
[863c966ace644a291076a9c81d9dec16.png]: /images/20221120/a724a45dd90e49d39b73965a89a74338.png
[f428e4b8024ff0a0fccc145eab1b98ef.png]: /images/20221120/d7cf0f1d538c422d8aec8039a10efbc7.png
[ef0e83e51e39551c0040c0e09494eabc.png]: https://img-blog.csdnimg.cn/img_convert/ef0e83e51e39551c0040c0e09494eabc.png
[4f3890d5d67066e21f75ad978891afbc.png]: https://img-blog.csdnimg.cn/img_convert/4f3890d5d67066e21f75ad978891afbc.png
[23bb1ba51c93f9fe8da0d70dc0fe2c49.png]: https://img-blog.csdnimg.cn/img_convert/23bb1ba51c93f9fe8da0d70dc0fe2c49.png