全网首发：12306抢票算法大曝光？（十张图搞定）
共 2387字，需浏览 5分钟
·
2020-08-12 22:40
关注公众号“彤哥读源码”，解锁更多源码、基础、架构知识！
前言
本文收录于专辑：http://dwz.win/HjK，点击解锁更多数据结构与算法的知识。
你好，我是彤哥，一个每天爬二十六层楼还不忘读源码的硬核男人。
相信大家都有过抢票、刷票的经验，每年年底，这都是一场盛宴。
然而，你有没有想过12306的抢票算法是怎么实现的呢？
没有吧，想过，还是没有头绪？
今天，我们就来曝光让人又爱又恨的12306是如何实现抢票的。
位运算回顾
我们知道计算机只能识别0和1，要操作这些0和1，只能通过位运算来进行，那么，一共有几种位运算呢？
让我们来回顾一下：
| 运算 | 符号 | 举例 | 结果 |
|---|---|---|---|
| 与 | & | 1101 & 0110 | 0100 |
| 或 | | | 1101 & 0110 | 1111 |
| 异或 | ^ | 1101 ^ 0110 | 1011 |
| 取反 | ~ | 1101 | 0010 |
| 左移 | << | 1101 << 1 | 11010 |
| 带符号右移 | >> | 1101 >> 1 | 1110 |
| 不带符号右移 | >>> | 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，就得到了他的活跃度。
OK，这只是位图的一个很简单的用法，位图还有很多高级的用法，比如统计活跃用户数、限流、权限控制等，当然，还有我们今天要曝光的12306抢票算法。
12306抢票算法
我们知道，一列火车，有很多个座位，可以到很多站，以北京到广州的一列火车G67为例：
G67次列车一共有18个站，有的人可能到武汉就下车了，有的人可能到长沙下车，还有的人可能从武汉上车从衡山西下车，甚至还有的人从北京一直坐到广州，我们假设这趟列车一共有200个座位。
那么，如何实现合理的抢票策略，才能保证这趟列车能够坐最多的人？（没有站票）
什么叫做“坐最多的人”呢？假设针对10号位置，一个人从北京到武汉，另一个人从武汉到长沙，再一个人从长沙到广州，那针对这个位置全程可以坐3个人；针对另一个位置，一个人从北京到广州，那这个位置全程只能坐一个人。简单点说，就是针对一个特定的位置，两个人之间不能有交集，比如一个人从北京到长沙，另一个人从武汉到广州，那这两个人不能安排到同一个位置上。
OK，先给你一分钟时间思考一下，先别急着往下看哦。
好了，一分钟时间已到，让我们继续。
首先，让我们回顾下G67这趟列车的信息：一共18个站，一共200个座位。
为了方便讲解和画图，我们假设它只有 北京、信阳、武汉、岳阳、长沙、广州 6个站，一共有8个座位。
针对这样的信息，我们可以这样来实现抢票策略：
创建5个位图，每个位图的大小为8位，初始时，每个位的值都是0。
为什么是5个位图呢？因为到站就下车了，而广州站是终点站，到站全部人都得下车。比如，一个人从北京到武汉，他到武汉就下车了，所以，它不会占用武汉的位置。
把抢票逻辑放在单线程中来处理，单线程的好处是不用考虑并发问题，没有CPU上下文切换的问题等，而且整个操作都是CPU操作，速度很快，使用单线程效率更高。
当然，我们还有更好的选择——Redis，Redis本身就是单线程处理的，而且它天然支持BitMap，速度又快又好，有兴趣的同学可以了解一下Redis中的BitMap。
假设第一个人的请求过来了，他要抢从北京到武汉的票，此时，我们只需要把北京和信阳两个位图做“与”运算，结果中，所有0的位置都表示可抢的位置，在这些位置中随机返回一个即可，并把此位置在北京和信阳这两个位图中标记为1，表示此位置在北京和信阳有人占用了。（武汉为什么不参与运算了，前面讲过了，这个人到武汉就下车了。）
假设，此人最后的座位是2号，那么运算之后，各位图的情况如下：
接着，第二个人的请求过来了，假设他要从信阳到长沙，此时，需要把信阳、武汉和岳阳三个位图做“与”运算：
假设，此人最后的座位是4号，那么，运算之后，各位图的情况如下：
然后，第三个人的请求来了，假设他要从北京到广州，此时，把所有5个位图做“与”运算：
假设，此人最后的座位是1号位，那么，运算之后，各位图的情况如下：
OK，经过了多个人的请求之后，假设位图的情况变成了下面这样：
请思考，此时，还能抢到从北京到广州的票吗？
能？不能？回答能的同学，请从头再看一遍
好了，关于抢票算法我们就介绍到这里，你有没有Get到呢？或者你有没有更好的实现方法呢？
后记
本节，我们一起重温了位运算的操作，并学习了如何使用位图实现12306的抢票算法，关于位图，其实还有很多用途，比如，各种统计、限流、权限控制等。
彤哥收到最新情报：所有的递归都可以改写成非递归，怎么实现呢？有没有什么套路呢？下一节，我们一起来聊下这个话题。
关注公号主“彤哥读源码”，解锁更多源码、基础、架构知识。