BridgeLi's Blog

记得 12306 刚上线的时候，就在想 12306 是如何卖票，一趟车从北京到上海，中间经过了 N 个站，大家可以买其中的任意两站，而因为卖出了一个一张票，从北京到上海很多站的车票都会变动，当时就感觉这个算法太复杂了，一般人还真写不出来，由此虽然很多人都在吐槽 12306，但是我却一直任务 12306 特别牛，很多人吐槽的大学生水平肯定是做不出来的，前一段时间，听马士兵教育的周志磊老师讲课，提出 redis 中的位图解决，设计的很巧妙，突然感觉豁然开朗，如果你也有这个问题，不妨参考一下。至于什么是位图，就不多说了，如果不知道，可以简单搜索。

首先说问题，我们假设一趟车是从 A 站到 B 站，中间有 C、D、E、F、G 站，这趟车有 1、2、3、5、6 个座位，任何一个人从可以买任意一趟车的任一个座，当然被别人买过了就不行，我们都坐过车，所以规则就不多说了，直接上算法。

我们设置一个 key，例如 keyA 就代表，这趟车在 A 站的情况，所以默认情况下 keyA = 000000；同理其他站也是这个情况。假设此时有一个人甲买了从 A 站到 E 站的票 2 号靠，也就是 A、C、D 三站他是在 2 号座位上的，E 站就下车了，座位空出来了，所以此时 keyA、keyC、keyD 应该是 010000，其余还都是 000000，于此同时又来了一个人乙，他要买从 C 站到 F 站的票，那么他可以买哪些票呢？很明显除了 2 都可以买（被甲从 A 站到 E 站占了），我们怎么得到的这个结果呢？我们可以让 keyC、keyD、keyE，也就是乙要做的这三站的 key，按位做或运算，我们就可以得出结果：010000，第二位是 1，就代表座上有人我们不能买，其余的都可以买，假设他买了 4 号票，那么此时 keyA 是 010000，keyC、keyD 是 010100，keyE 是 000100，keyF、keyG、keyB 以为是 000000，所以假设此时来了一个人丙要买从 D 站到 B 站的票，我们只需要 keyD、keyE、keyF、keyG 按位或即可，得出的结果是 010100，也就是只有 2 号位（被甲在 D 到 E 的时候占了）和 4 号位（被乙从 D 站到 E 站的时候占了）不能买，其余的座位是可以随便买的，然后把相应的座位从出发站到终到站前面的一站标记成 1 即可，这样我们可以发现，我们只需要一个按位或运算，即可实现动态管理这趟车的车票，非常简单。而且位图八位才一个字节，一趟车一个车厢 118 座，按 16 个车厢算才 1888 位，236 个字节，占用内存非常少。而且 redis 原生支持位图或运算，速度也非常快。

最后我们会发现，这个算法设计很巧妙，占用内存很少，速度很快，使用简单，这就是算法的力量。