共计 2252 个字符，预计需要花费 6 分钟才能阅读完成。
前言
本文收录于专辑：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，就失去了他的活跃度。
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 的抢票算法，对于位图，其实还有很多用处，比方，各种统计、限流、权限管制等。
彤哥收到最新情报：所有的递归都能够改写成非递归，怎么实现呢？有没有什么套路呢？下一节，咱们一起来聊下这个话题。
关注公号主“彤哥读源码”，解锁更多源码、根底、架构常识。
